Nos tutelles

CNRS Dauphine PSL *



Seminar Games and Social Choice

publié le , mis à jour le

This page is maintained by Stefano Moretti and Laurent Gourvès.
The project Jeux et choix social proposes seminars open to every person who is interested in the topic


  • 11 décembre 2018, 11:00-12:00 P301
    Nguyen Kim Thang - "Game Efficiency through Linear Programming Duality".
    The efficiency of a game is typically quantified by the price of anarchy (PoA), defined as the worst ratio of the value of an equilibrium --- solution of the game --- and that of an optimal outcome. Given the tremendous impact of tools from mathematical programming in the design of algorithms and the similarity of the price of anarchy and different measures such as the approximation and competitive ratios, it is intriguing to develop a duality-based method to characterize the efficiency of games.
    In the talk, we present an approach based on linear programming duality to study the efficiency of games. We show that the approach provides a general recipe to analyze the efficiency of games and also to derive concepts leading to improvements. We show the applicability of the approach to the wide variety of games and environments, from congestion games to Bayesian welfare, from full-information settings to incomplete-information ones.
    We also mention some open directions.
  • 30 novembre 2018, 11:00-12:00 salle P301
    Shurojit Chatterji - "Random Mechanism Design on Multidimensional Domains" (joint work with Huaxia Zeng). We study random mechanism design in an environment where the set of alternatives has a
    Cartesian product structure. We first show that all generalized random dictatorships are sd-strategy-proof on a minimally rich domain if and only if all preferences are top-separable. We call a domain satisfying top-separability a multidimensional domain, and furthermore generalize the notion of connectedness (Monjardet, 2009) to a broad class of multidimensional
    domains : connected+ domains. We show that in the class of minimally rich and connected+domains, the multidimensional single-peakedness restriction is necessary and sufficient for the design of a flexible random social choice function that is unanimous and sd-strategy-proof.
    Such a flexible random social choice function allows for a systematic notion of compromise. We prove an analogous result for deterministic social choice functions satisfying anonymity. Our characterization remains valid for a problem of voting under constraints where not all
    alternatives are feasible (Barbera, Masso, and Neme, 1997).
  • 13 mars 2018, 14:00-15:00 salle P301
    Davide grossi - "Liquid Democracy"
    Liquid democracy is a proxy voting method where proxies are delegable : individual a may delegate her vote to b, who in turn may delegate it to c and so on. Ultimately, an individual’s vote carries the weight given by the number of other individuals who (directly or indirectly) entrusted her as proxy. The method has been used and popularised by a number of parties (e.g, Piratenpartei, Germany) and grassroots initiatives for democratic reforms (e.g., MakeYourLaws, US). In this talk I will present recent work aiming at providing theoretical foundations for this novel voting method from the perspective of binary (judgment) aggregation, network theory, and game theory. The talk presents joint work with Zoé Christoff (Bayreuth), Daan Bloembergen (CWI Amsterdam) and Martin Lackner (TU Wien).
  • 15 february 2018, 13:30-15:00 room P301
    Andy Mac Kenzie - "Club good mechanisms : from free-riders to citizen-shareholders, from impossibility to characterization"
    Consider a community that shares a technology for producing a club good (Buchanan, 1965) : any group of agents can "win" for an associated monetary cost. Who should win, and how should production be funded ? To address this question, we seek rules (that is, direct mechanisms) where each agent participates voluntarily and is incentivized to report his valuation honestly, and where these reports are used to select winners efficiently without running a decit. We find that whether or not there are such rules depends on the production technology. If costs are even "somewhat concave," then there are no such rules : the free-rider problem (Wicksell, 1896 ; Samuelson, 1954 ; Green and Laffont, 1979) persists even when agents who do not contribute can be excluded. If costs are symmetric and convex, however, then there are such rules that moreover satisfy no-envy-in-trades (Kolm, 1971 ; Schmeidler and Vind, 1972). We characterize this class, whose Pareto-worst member is the familiar minimum-price Walrasian rule (Vickrey, 1961 ; Clarke, 1971 ; Groves, 1973 ; Demange, 1982 ; Leonard, 1983) ; the other rules do better by treating the agents as equal shareholders in the technology and offering social dividends (Lange, 1936).
  • 13 february 2018, 14:00-15:00 room B102
    Vittorio Bilò - "The Price of Stability of Undirected Broadcast Games is Constant". Joint work with Michele Flammini and Luca Moscardelli.
    Abstract : one of the most challenging open problems in Algorithmic Game Theory is the characterization of the price of stability in undirected network design games with fair cost sharing. In this talk, we present a breakthrough result showing that this quantity is O(1) in the special case of broadcast games, where every node aims at building a connection to a distinguished common source.
  • 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"