18 décembre 2017 à 12h - C110 Haris Aziz - "Achieving Proportional Representation via Voting" Proportional representation (PR) is often discussed in voting settings as a major desideratum. For the past century or so, it is common both in practice and in the academic literature to jump to STV (Single Transferable Vote) as the solution for achieving PR. Some of the most prominent electoral reform movements around the globe are pushing for the adoption of STV. It has been termed a major open problem to design a voting rule that satisfies the same PR properties as STV and better monotonicity properties. We present a rule called EAR (Expanding Approvals Rule) that satisfies properties stronger than the central PR axiom satisfied by STV, can handle indifferences in a convenient and computationally efficient manner, and also satisfies better candidate monotonicity properties. In view of this, our proposed rule seems to be a compelling solution for achieving proportional representation in voting settings. (Based on joint work with Barton Lee)
14 décembre 2017 de 14h00 à 15h - D102 Reshef Meir - "Contract Design for Energy Demand Response" Power companies such as Southern California Edison (SCE) uses independent Demand Response (DR) contracts to incentivize consumers to reduce their power consumption during periods when demand forecast exceeds supply. We introduce DR-VCG, a new DR mechanism that offers a flexible set of contracts (which may include the standard SCE contracts) and uses VCG pricing. We show that DR-VCG is truthful, can be efficiently computed, and bounds the failure probability of the network. Extensive simulations show that compared to the current mechanism deployed by SCE, the DR-VCG mechanism achieves higher participation, increased reliability, and significantly reduced total expenses. Time permits, I will mention how contingent payments that underlie this work, also lead to a strong impossibility theorem in social choice with money. Joint work with Hongyao Ma and Valentin Robu.
13 décembre 2017 de 11h00 à 12h - C131 Rasmus Ibsen-Jensen - "Values and strategies in stochastic games" Stochastic games is a type of two-player zero-sum games with many applications in economics and computer science. Each such game consists of a finite set of matrices and is played over rounds. In each round, some matrix is played as a matrix game (a matrix game is a simple generalization of the rock-paper-scissors game) and the players choices together in that round determines the outcome (=some number) of that round of the game and which matrix is played in the next round. One player then tries to maximize the long-run average outcome of the rounds and the other player tries to minimize it. These games have a value in the sense that there is a number v for each matrix such that if the game starts there the maximizer can, for any c>0, guarantee at least v - c against any strategy of the minimizer (the minimizer can similarly guarantee v+c).In general however, to achieve anything non-trivial one needs memory of the other players past choices. In the talk I will describe my recent results about these games. Specifically, I will first describe a polynomial time algorithm for finding the set of matrices that have value M, where M is the largest possible outcome, and where the maximizer has a finite-memory strategy for ensuring M - c for all c>0. Next, all classic strategies for these games in general requires memory of size O(log T) bits for the first T rounds. The second part will give a randomized strategy that does so using only memory of size O(log log T) bits for the first T rounds with high probability. Finally, a long standing open problem from ’79 asks if one can play a specific stochastic game with finite memory if one does not count space used to store the round number. I will show how to do so using only a single additional bit.
10 octobre 2017 de 14h à 15h - C110 Ayumi Igarashi - "Hedonic Games with Graph-restricted Communication" We study hedonic coalition formation games in which cooperation among the players is restricted by a graph structure : a subset of players can form a coalition if and only if they are connected in the given graph. We investigate the complexity of finding stable outcomes in such games, for several notions of stability. In particular, we provide an efficient algorithm that finds an individually stable partition for an arbitrary hedonic game on an acyclic graph. We also introduce a new stability concept—in-neighbor stability—which is tailored for our setting. We show that the problem of finding an in- neighbor stable outcome admits a polynomial-time algorithm if the underlying graph is a path, but is NP-hard for arbitrary trees even for additively separable hedonic games ; for symmetric additively separable games we obtain a PLS-hardness result.
28 septembre 2017 de 15h à16h - A711 Hervé Moulin "Fair Mixture of Public Outcomes" We revisit probabilistic voting under dichotomous preferences, when a design constraint is to offer welfare guarantees to individual and group participants. Minorities should not be crushed by the disagreeing majority, but the size of the support for a given outcome should nevertheless increase its weight. Given that we cannot combine Efficiency, Incentive Compatibility and Individual Fair Shares, we discuss second best mechanisms achieving two of these three design goals. We find that a simple Borda-like rule and the familiar Random Priority rule are IC and ensure good guarantees to homogenous groups. Borda is easier to compute but more inefficient than RP. The efficient Nash rule (maximizing the product of utilities) offers stronger group guarantees than both, but fails some simple IC tests . We also uncover a handful of challenging open questions. Joint with H. Aziz and A. Bogomolnaia
26 septembre 2017 de 15h à 16h - A707 Carlos Pimienta "Expériences de vote en ligne (avec Amazon Mechanical Turk)" We test the turnout predictions of the standard two-party, private value, costly voting model through a large-scale, real effort experiment. We do this by recruiting 1,200 participants through Amazon Mechanical Turk and employing a 2 x 2 between subjects design encompassing small (N = 30) and large (N = 300) elections, as well as symmetric and asymmetric ones. We find evidence of the size effect in asymmetric elections and of the competition effect in large elections. We also find evidence of underdog effect in small elections but, contrary to theoretical predictions, we observe bandwagon behavior in large elections. We propose a behavioral model that accounts for these results.
11 septembre 2017 de 14h à 15h - A707 Dominik Peters "Structured preferences"
