nep-gth New Economics Papers
on Game Theory
Issue of 2016‒04‒09
seventeen papers chosen by
László Á. Kóczy
Magyar Tudományos Akadémia

  1. Non-Revelation Mechanisms for Many-to-Many Matching: Equilibria versus Stability By Bettina Klaus; Flip Klijn
  2. Effciency and equilibrium in network games: An experiment By Edoardo Gallo; Chang Yan; ;
  3. The Roommate Problem Revisited By Marilda Sotomayor
  4. Cooperation in the Finitely Repeated Prisoner's Dilemma By Matthew Embrey; Guillaume R. Frechette; Sevgi Yuksel
  5. Trading in Networks: Theory and Experiments By Syngjoo Choi; Andrea Galeotti; Sanjeev Goyal;
  6. Iterative Revelation Mechanisms By Ryuji Sano
  7. Collusion with a Greedy Center in Position Auctions By Emmanuel LORENZON
  8. A rank based mean field game in the strong formulation By Erhan Bayraktar; Yuchong Zhang
  9. The strategic environment effect in beauty contest games By Nobuyuki Hanaki; Angela Sutan; Marc Willinger
  10. Reducing the role of random numbers in matching algorithms for school admission By Hulsbergen, Wouter
  11. A Strong Correspondence Principle for Smooth, Monotone Environments By Finn Christensen
  12. Explicit vs. Statistical Preferential Treatment in Affirmative Action: Theory and Evidence from Chicago's Exam Schools By Umut Dur; Parag A. Pathak; Tayfun Sönmez
  13. Accuracy and Retaliation in Repeated Games with Imperfect Private Monitoring: Experiments and Theory By Yutaka Kayaba; Hitoshi Matsushima; Tomohisa Toyama
  14. Robustness of Full Revelation in Multisender Cheap Talk By Margaret Meyer; Ines Moreno de Barreda; Julia Nafziger
  15. Information Acquisition and Exchange in Social Networks By Sanjeev Goyal; Stephanie Rosenkranz; Utz Weitze; Vincent Buskens
  16. Competitive Fair Division under linear preferences By Anna Bogomolnaia; Herve Moulin
  17. Auction-Based Allocation of Shared Electricity Storage Resources through Physical Storage Rights By Tom Brijs; Daniel Huppmann; Sauleh Siddiqui; Ronnie Belmans

  1. By: Bettina Klaus; Flip Klijn
    Abstract: We study many-to-many matching markets in which agents from a set A are matched to agents from a disjoint set B through a two-stage non-revelation mechanism. In the first stage, A-agents, who are endowed with a quota that describes the maximal number of agents they can be matched to, simultaneously make proposals to the B-agents. In the second stage, B-agents sequentially, and respecting the quota, choose and match to available A-proposers. We study the subgame perfect Nash equilibria of the induced game. We prove that stable matchings are equilibrium outcomes if all A-agents' preferences are substitutable. We also show that the implementation of the set of stable matchings is closely related to the quotas of the A-agents. In particular, implementation holds when A-agents' preferences are substitutable and their quotas are non-binding.
    Keywords: Matching, mechanisms, stability, substitutability
    JEL: C78 D78
    Date: 2016–04
  2. By: Edoardo Gallo; Chang Yan; ;
    Abstract: The tension between efficiency and equilibrium is a central feature of economic systems. In many contexts, social networks mediate this trade-off: an individual's network position determines equilibrium play, and social relations allow coordination on an efficient norm. We examine this trade-o in a network game with a unique Nash equilibrium, but such that agents can achieve a higher payoff by following a "collaborative norm". Subjects establish and maintain a collaborative norm in the circle, but the norm weakens with the introduction of one asymmetric node in the wheel. In complex and asymmetric networks of 15 and 21 nodes, the norm disappears and subjects' play converges to Nash on every node. We provide evidence that subjects base their decisions on their degree, rather than the overall network structure. Methodologically, the paper shows the capabilities of UbiquityLab: a novel platform to conduct interactive experiments online with a large number of participants.
    Keywords: network, online experiment, network game, strategic complements.
    JEL: C99 D03 D85 Z13
    Date: 2015–02–09
  3. By: Marilda Sotomayor
    Abstract: We approach the roommate problem by focusing on simple matchings, which are those individually rational matchings whose blocking pairs, if any, are formed with unmatched agents. We show that the core is non-empty if and only if no simple and unstable matching is Pareto optimal among all simple matchings. The economic intuition underlying this condition is that blocking can be done so that the transactions at any simple and unstable matching need not be undone, as agents reach the core. New properties of economic interest are proved.
    Keywords: Core; Stable matching
    JEL: C78 D78
    Date: 2016–03–04
  4. By: Matthew Embrey (University of Sussex); Guillaume R. Frechette (NYU); Sevgi Yuksel (UCSB)
    Abstract: More than half a century after the first experiment on the finitely repeated prisoner's dilemma, evidence on whether cooperation decreases with experience, as suggested by backward induction, remains inconclusive. This paper provides a meta-analysis of prior experimental research and reports the results of a new experiment to elucidate how cooperation varies with the environment in this canonical game. We describe forces that affect initial play (formation of cooperation) and unraveling (breakdown of cooperation). First, contrary to the backward induction prediction, the parameters of the repeated game have a signifcant effect on initial cooperation. We identify how these parameters impact the value of cooperation - as captured by the size of the basin of attraction of Always Defect- to account for an important part of this effect. Second, despite these initial differences, the evolution of behavior is consistent with the unraveling logic of backward induction for all parameter combinations. Importantly, despite the seemingly contradictory results across studies, the paper establishes a systematic pattern of behavior: Subjects converge to using threshold strategies that conditionally cooperate until a threshold round; and conditional on establishing cooperation, the first defection round moves earlier with experience. Simulation results generated from a learning model estimated at the subject level provide insights on the long-term dynamics and the forces slowing down the unravelling of cooperation.
    Keywords: repeated games, prisoners dilemma, threshold strategies, basin of attraction
    JEL: C73 C92
    Date: 2016–02
  5. By: Syngjoo Choi; Andrea Galeotti; Sanjeev Goyal;
    Abstract: We propose a model of posted prices in networks. The model maps traditional concepts of market power, competition and double marginalization into networks, allowing for the study of pricing in complex structures of intermediation such as supply chains, transportation and communication networks and financial brokerage. We provide a complete characterization of equilibrium prices. Our experiments complement our theoretical work and point to node criticality as an organizing principle for understanding pricing, efficiency and the division of surplus in networked markets.
    Keywords: Intermediation, competition, market power, double marginalization.
    JEL: C70 C71 C91 C92 D40
    Date: 2014–05–16
  6. By: Ryuji Sano (Institute of Economic Research, Kyoto University)
    Abstract: This paper considers dynamic resource allocation processes, called iterative revelation mechanisms, with quasi-linear dichotomous utilities and complete information. Agents gradually reveal their valuation through binary questions. The social planner identifies the efficient outcome, and monetary transfer is determined on a “pay-as-bid” basis. We show that the efficient allocation rule is implemented in a subgame perfect Nash equilibrium, regardless of details of a binary-question process. The analysis applies to the case with limited communication, and every strongly monotone allocation rule is implemented in equilibrium. We also show that if a resource allocation process is ex post incentive compatible, it is an ascending-price mechanism. In a single-object allocation problem, the English auction is a unique mechanism satisfying efficiency, ex post incentive compatibility, and pay-as-bid transfer.
    Keywords: iterative revelation mechanism, limited communication, ascending price, English auction
    JEL: D44 D83 D82 D71 H41
    Date: 2016–03
  7. By: Emmanuel LORENZON
    Abstract: In this paper we aim at studying the sensitivity of the Generalized Second-Price auction to bidder collusion when monetary transfers are allowed. We propose a model of position auction that incorporates third-parties as agents facilitating collusion in complete information. We show that the first-best collusive outcome can be achieved under any Nash condition. Under the locally envy-free criterion, we find that if the collusive gain is uniformly redistributed among members, the best that can be achieved is Vickrey-Clarkes-Groves outcome. Bidders do not have sufficient incentives to reduce even more their expressed demand. We then provide elements upon which an incentive compatible fee can be set by the center. We provide conditions under which bidders can enhance efficient collusion. Doing so we also contribute to the literature on collusion in multiple-objects simultaneous auctions.
    Keywords: Auctions, Online advertising, Position auctions; Bidding ring, Cartel
    JEL: D44 C72 M3 L41
    Date: 2016
  8. By: Erhan Bayraktar; Yuchong Zhang
    Abstract: We discuss a natural game of competition and solve the corresponding mean field game with \emph{common noise} when agents' rewards are \emph{rank dependent}. We use this solution to provide an approximate Nash equilibrium for the finite player game and obtain the rate of convergence.
    Date: 2016–03
  9. By: Nobuyuki Hanaki (GREDEG - Groupe de Recherche en Droit, Economie et Gestion - UNS - Université Nice Sophia Antipolis - CNRS - Centre National de la Recherche Scientifique); Angela Sutan (GESC Dijon - Groupe Ecole Supérieure de Commerce Dijon - Bourgogne); Marc Willinger (LAMETA - Laboratoire Montpelliérain d'Économie Théorique et Appliquée - UM1 - Université Montpellier 1 - Institut national de la recherche agronomique (INRA) - Centre international de hautes études agronomiques méditerranéennes [CIHEAM] - CNRS - Centre National de la Recherche Scientifique, UM - Université de Montpellier)
    Abstract: Recent experimental studies have shown that observed outcomes deviate significantly more from the Nash equilibrium when actions are strategic complements than when they are strategic substitutes. This " strategic environment effect " offers promising insights into the aggregate consequences of interactions among heterogeneous boundedly rational agents, but its macroeconomic implications have been questioned because the underlying experiments involve a small number of agents. We studied beauty contest games with a unique interior Nash equilibrium to determine the critical group size for triggering the strategic environment effect. We show theoretically that the effect operates for interactions among three or more agents. Our experimental results partially support this theory, showing a statistically significant strategic environment effect for groups of five or more agents. Our findings establish that experiments involving a small number of interacting agents can provide major insights into macro phenomena and bolster previous work done on such issues as price dynamics.
    Keywords: beauty contest games,iterative reasoning,strategic substitutability,strategic complementarity
    Date: 2016–03
  10. By: Hulsbergen, Wouter
    Abstract: New methods for solving the college admissions problem with indifference are presented and characterised with a Monte Carlo simulation in a variety of simple scenarios. Based on a qualifier defined as the average rank, it is found that these methods are more efficient than the Boston and Deferred Acceptance algorithms. The improvement in efficiency is directly related to the reduced role of random tie-breakers. The strategy-proofness of the new methods is assessed as well.
    Keywords: college admission problem; deferred acceptance algorithm; Boston algorithm; Zeeburg algorithm; pairwise exchange algorithm; strategic behaviour
    JEL: I2
    Date: 2016–03–12
  11. By: Finn Christensen (Department of Economics, Towson University)
    Abstract: Comparative statics are monotone if and only if equilibrium is exponentially stable under discrete time best response or adaptive dynamics. In addition, if every equilibrium is exponentially stable then equilibrium must be unique. This last result does not require monotonicity. In this sense this result broadens the scope of the correspondence principle to include a relationship between stability and uniqueness, in addition to a relationship between stability and comparative statics.
    Keywords: correspondence principle, stability, comparative statics, uniqueness, best response dynamics, adaptive dynamics, M-matrix.
    JEL: D5 C7
    Date: 2016–03
  12. By: Umut Dur; Parag A. Pathak; Tayfun Sönmez
    Abstract: Affirmative action schemes must confront the tension between admitting the highest scoring applicants and ensuring diversity. In Chicago's affirmative action system for exam schools, applicants are divided into one of four socioeconomic tiers based on the characteristics of their neighborhood. Applicants can be admitted to a school either through a slot reserved for their tier or through a merit slot. Equity considerations motivate equal percentage reserves for each tier, but there is a large debate on the total size of these reserve slots relative to merit slots. An issue that has received much less attention is the order in which slots are processed. Since the competition for merit slots is influenced directly by the allocation to tier slots, equal size reserves are not sufficient to eliminate explicit preferential treatment. We characterize processing rules that are tier-blind. While explicit preferential treatment is ruled out under tier-blind rules, it is still possible to favor certain tiers, by exploiting the distribution of scores across tiers, a phenomenon we call statistical preferential treatment. We characterize the processing order that is optimal for the most disadvantaged tier assuming that these applicants systematically have lower scores. This policy processes merit slots prior to any slots reserved for tiers. Our main result implies that Chicago has been providing an additional boost to the disadvantaged tier beyond their reserved slots. Using data from Chicago, we show that the bias due to processing order for the disadvantaged tier is comparable to that from the 2012 decrease in the size of the merit reserve.
    JEL: C78 I21
    Date: 2016–03
  13. By: Yutaka Kayaba (Hitotsubashi University); Hitoshi Matsushima (University of Tokyo); Tomohisa Toyama (Kogakuin University)
    Abstract: We experimentally examine repeated prisoners' dilemma with random termination, where monitoring is imperfect and private. Our estimation indicates that a significant proportion of subjects follow generous Tit-For-Tat (g-TFT) strategies, straightforward extensions of Tit-For-Tat. However, the observed retaliating policies are inconsistent with the g-TFT equilibria. Contrarily to the theory, subjects tend to retaliate more with high accuracy than with low accuracy. They tend to retaliate more than the theory predicts with high accuracy, while they tend to retaliate lesser with low accuracy. In order to describe these results as unique equilibrium, we demonstrate an alternative theory that incorporates naivete and reciprocity.
    Date: 2016–03
  14. By: Margaret Meyer; Ines Moreno de Barreda; Julia Nafziger
    Abstract: Abstract: This paper studies information transmission in a two-sender, multidimensional cheap talk setting where there are exogenous restrictions on the feasible set of policies for thereceiver. Such restrictions, which are present in most applications, can, by limiting the punishments available to the receiver, prevent the existence of fully revealing equilibria(FRE). We focus on FRE that are i) robust to small mistakes by the senders, in that small differences between the senders’ messages result in only small punishments by the receiver, and ii) independent of the magnitudes of the senders’ bias vectors. For convex policy spaces in an arbitrary number of dimensions, we prove that if there exists a FRE satisfying property ii), then there exists one satisfying both i) and ii). Thus the requirement of robustness is, under these assumptions, not restrictive. For convex policy spaces in two dimensions, we provide a simple geometric condition, the Local Deterrence Condition, on the directions of the senders’ biases relative to the frontier of the policy space, that is necessary and sufficient for the existence of a FRE satisfying i) and ii). We also provide a specific policy rule, the Min Rule, for the receiver that supports a FRE satisfying i) and ii) whenever one exists. The Min Rule is the anonymous rule that punishes incompatible reports in the least severe way, subject to maintaining the senders’ incentives for truthtelling, no matter how large their biases. We characterize necessary and sufficient conditions for collusion-proofness of a FRE supported by the receiver using the Min Rule and show that if such a FRE is not collusion-proof, then no other FRE satisfying ii) can be collusion-proof. We extend our existence results to convex policy spaces in more than two dimensions and to non-convex two-dimensional spaces. Finally, our necessary and sufficient condition, as well as our specific policy rule, can be easily adapted if the receiver is uncertain about the directions of the biases and/or if the biases vary with the state of the world.
    Keywords: Cheap talk, information transmission, multisender, full revelation, robustness
    JEL: D83 D82 C72
    Date: 2016–03–23
  15. By: Sanjeev Goyal; Stephanie Rosenkranz; Utz Weitze; Vincent Buskens
    Abstract: A central feature of social networks is information sharing. The Internet and related computing technologies define the relative costs of private information acquisition and forming links with others. This paper presents an experiment on the effects of changing costs.We find that a decline in relative costs of linking makes private investments more dispersed and gives rise to denser social networks. Aggregate investment falls, but individuals access to investment remains stable, due to increased networking. The overall effect is a significant increase in individual utility and aggregate welfare.
    Date: 2015–12–21
  16. By: Anna Bogomolnaia; Herve Moulin
    Date: 2016–01
  17. By: Tom Brijs; Daniel Huppmann; Sauleh Siddiqui; Ronnie Belmans
    Abstract: This article proposes a new electricity storage business model based on multiple simultaneously considered revenue streams, which can be attributed to different market activities and players. These players thus share electricity storage resources and compete to obtain the right to use them in a dynamic allocation mechanism. It is based on the design of anew periodically organized auction to allocate shared storage resources through physical storage rights between different market players and ac-companying applications. Through such a flexibility platform owners of flexible resources can commercialize their flexible capacity over different applications, while market players looking for additional flexibility can obtain this through a pay-per-use principle and thus not having to make long-term investment commitments. As such, they can quickly adapt their portfolio according to the market situation. Alternatively, through such an allocation mechanism players can effectively share storage re-sources. Players may be incentivized to participate as they can share the investment cost, mitigate risk, exploit economies of scale, overcome regulatory barriers, and merge time-varying and player-dependent flexibility needs. The mechanism allocates the limited storage resources to the most valuable application for each market-clearing, based on the competing players' willingness-to-pay. An illustrative case study is provided in which three players share storage resources that are allocated through a daily auction with hourly market-clearings.
    Keywords: electricity storage, shared storage resources, auction-based allocation, (Generalized) Nash Equilibrium, Mixed Complementarity Problem
    Date: 2016

This nep-gth issue is ©2016 by László Á. Kóczy. It is provided as is without any express or implied warranty. It may be freely redistributed in whole or in part for any purpose. If distributed in part, please include this notice.
General information on the NEP project can be found at For comments please write to the director of NEP, Marco Novarese at <>. Put “NEP” in the subject, otherwise your mail may be rejected.
NEP’s infrastructure is sponsored by the School of Economics and Finance of Massey University in New Zealand.