|
on Game Theory |
|
Issue of 2011‒10‒22
twelve papers chosen by Laszlo A. Koczy Hungarian Academy of Sciences and Obuda University |
| By: | Dirk Bergemann (Cowles Foundation, Yale University); Stephen Morris (Dept. of Economics, Princeton University) |
| Abstract: | We define a notion of correlated equilibrium for games with incomplete information in a general setting with finite players, finite actions, and finite states, which we call Bayes correlated equilibrium. The set of Bayes correlated equilibria of a fixed incomplete information game equals the set of probability distributions over actions, states and types that might arise in any Bayes Nash equilibrium where players observed additional information. We show that more information always shrinks the set of Bayes correlated equilibria. |
| Keywords: | Correlated equilibrium, Incomplete information, Robust predictions, Information structure |
| JEL: | C72 D82 D83 |
| Date: | 2011–10 |
| URL: | http://d.repec.org/n?u=RePEc:cwl:cwldpp:1822&r=gth |
| By: | Chiu Yu Ko (Boston College) |
| Abstract: | This paper extends Bernheim and Whinston's (1986) menu auction model under transferable utilities to a framework with non-transferable utilities and budget constraints. Under appropriate definitions of equilibria, it is shown that every truthful Nash equilibrium (TNE) is a coalition-proof Nash equilibrium (CPNE) and that the set of TNE payoffs and the set of CPNE payoffs are equivalent, as in a transferable utility framework. The existence of a CPNE is assured in contrast with the possible non-existence of Nash equilibrium under the definition by Dixit, Grossman, and Helpman (1997). Moreover, the set of CPNE payoffs is equivalent to the bidder-optimal weak core. |
| Keywords: | non-transferable utility, menu auction, coalition-proof Nash equilibrium, truthful Nash equilibrium |
| JEL: | C72 D79 |
| Date: | 2011–10–20 |
| URL: | http://d.repec.org/n?u=RePEc:boc:bocoec:787&r=gth |
| By: | Thomas, C.D. |
| Abstract: | In this thesis we present a new take on two classic problems of game theory: the "multiarmed bandit" problem of dynamic learning, and the "Colonel Blotto" game, a multidi- mensional contest. In Chapters 2-4 we treat the questions of experimentation with congestion: how do players search and learn about options when they are competing for access with other players? We consider a bandit model in which two players choose between learning about the quality of a risky option (modelled as a Poisson process with unknown arrival rate), and competing for the use of a single shared safe option that can only be used by one agent at the time. We present the equilibria of the game when switching to the safe option is irrevocable, and when it is not. We show that the equilibrium is always inefficient: it involves too little experimentation when compared to the planner solution. The striking equilibrium dynamics of the game with revocable exit are driven by a strategic option-value arising purely from competition between the players. This constitutes a new result in the bandit literature. Finally we present extensions to the model. In particular we assume that players do not observe the result of their opponent's experimentation. In Chapter 5 we turn to the n-dimensional Blotto game and allow battlefields to have different values. We describe a geometrical method for constructing equilibrium distribution in the Colonel Blotto game with asymmetric battlfield values. It generalises the 3-dimensional construction method first described by Gross and Wagner (1950). The proposed method does particularly well in instances of the Colonel Blotto game in which the battlefield weights satisfy some clearly defined regularity conditions. The chapter also explores the parallel between these conditions and the integer partitioning problem in combinatorial optimisation. |
| Date: | 2011–08–28 |
| URL: | http://d.repec.org/n?u=RePEc:ner:ucllon:http://discovery.ucl.ac.uk/1325637/&r=gth |
| By: | Pintér, Miklós; Udvari, Zsolt |
| Abstract: | Ordinary type spaces (Heifetz and Samet, 1998) are essential ingredients of incomplete information games. With ordinary type spaces one can grab the notions of beliefs, belief hierarchies and common prior etc. However, ordinary type spaces cannot handle the notions of finite belief hierarchy and unawareness among others. In this paper we consider a generalization of ordinary type spaces, and introduce the so called generalized type spaces which can grab all notions ordinary type spaces can and more, finite belief hierarchies and unawareness among others. We also demonstrate that the universal generalized type space exists. |
| Keywords: | type space; unawareness; finite belief hierarchy; generalized type space; generalized belief hierarchy; incomplete information games |
| JEL: | D83 C72 |
| Date: | 2011 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:34107&r=gth |
| By: | Pintér, Miklós |
| Abstract: | The notion of common prior is well-understood and widely-used in the incomplete information games literature. For ordinary type spaces the common prior is defined. Pinter and Udvari (2011) introduce the notion of generalized type space. Generalized type spaces are models for various bonded rationality issues, for finite belief hierarchies, unawareness among others. In this paper we define the notion of common prior for generalized types spaces. Our results are as follows: the generalization (1) suggests a new form of common prior for ordinary type spaces, (2) shows some quantum game theoretic results (Brandenburger and La Mura, 2011) in new light. |
| Keywords: | Type spaces; Generalized type spaces; Common prior; Harsányi Doctrine; Quantum games |
| JEL: | D83 C72 |
| Date: | 2011 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:34118&r=gth |
| By: | Biran, Omer |
| Abstract: | Nous étudions la question de la collusion dans les enchères. Nous commençons par présenter un modèle d'enchère au premier prix en information complète et externalités directes non-symétriques. Nous suivons une approche non-coopérative en étudiant le processus de négociation qui décrit la formation d'un cartel. Nous montrons qu'en présence d'externalités directes la formation de la grande coalition n'est pas assurée, en proposant un exemple d'enchère dans lequel une petite coalition se forme à l'équilibre. Nous continuons par étudier la stabilité (au sens du cœur) de coalitions dans les jeux bayésiens. Nous montrons que tout équilibre coalitionnel est sans perte de généralité incitatif. Nous appliquons ainsi la notion de stabilité aux procédures d'enchères communes sans externalités directes, en établissant (surtout) la stabilité de la grande coalition. Avec externalités directes en information complète nous montrons que la grande coalition (ainsi qu'une coalition plus petite) peut devenir instable. Nous finissons par examiner la notion de stabilité dans les enchères au deuxième prix avec externalités directes en information incomplète. Nous identifions une classe d'équilibres maniables dans ces enchères pour toutes formes de collusion données. Finalement, dans ce modèle, nous démontrons l'instabilité de la grande coalition en présence d'externalités directes, en identifiant encore les externalités directes comme un obstacle au coopération. |
| Abstract: | We study the question of collusion in auctions. We start by presenting a model of a first price auction with complete information and direct asymmetric externalities. Following a non-cooperative approach we study the negotiations process which yields a cartel. We show that in the presence of direct externalities the grand coalition may not form, proposing an example of an auction in which a small coalition forms in equilibrium. We continue by studying the stability (in the sense of the core) of coalitions in Bayesian games. We show that all coalitional equilibria can be made incentive compatible. We apply the notion of stability on standard auctions without direct externalities, establishing (mainly) the stability of the grand coalition. With direct externalities and complete information we show that the grand coalition (as well as small coalitions) may become unstable. We conclude by examining the notion of stability in second price auctions with direct externalities and incomplete information. We identify a class of tractable equilibria for these auctions for any given collusion scheme. Finally, in this model, we demonstrate the instability of the grand coalition in the presence of direct externalities, identifying (again) direct externalities as an obstacle to cooperation. |
| Keywords: | Alliances stratégiques; Négociations; Cartels; Théorie des jeux; Vente aux enchères; |
| JEL: | D74 C7 |
| Date: | 2011–06 |
| URL: | http://d.repec.org/n?u=RePEc:ner:dauphi:urn:hdl:123456789/7238&r=gth |
| By: | Barbanel, Julius B.; Brams, Steven J. |
| Abstract: | A cake is a metaphor for a heterogeneous, divisible good. When two players divide such a good, there is always a perfect division—one that is efficient (Pareto-optimal), envy-free, and equitable—which can be effected with a finite number of cuts under certain mild conditions; this is not always the case when there are more than two players (Brams, Jones, and Klamler, 2011b). We not only establish the existence of such a division but also provide an algorithm for determining where and how many cuts must be made, relating it to an algorithm, “Adjusted Winner” (Brams and Taylor, 1996, 1999), that yields a perfect division of multiple homogenous goods. |
| Keywords: | Cake-cutting; fair division; envy-freeness; adjusted winner; heterogeneous good |
| JEL: | D63 D30 D74 C61 D61 C72 |
| Date: | 2011–10–22 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:34263&r=gth |
| By: | Ianni, Antonella |
| Abstract: | This paper studies the analytical properties of the reinforcement learning model proposed in Erev and Roth (1998), also termed cumulative reinforcement learning in Laslier et al (2001). This stochastic model of learning in games accounts for two main elements: the law of effect (positive reinforcement of actions that perform well) and the law of practice (the magnitude of the reinforcement effect decreases with players' experience). The main results of the paper show that, if the solution trajectories of the underlying replicator equation converge exponentially fast, then, with probability arbitrarily close to one, all the realizations of the reinforcement learning process will, from some time on, lie within an " band of that solution. The paper improves upon results currently available in the literature by showing that a reinforcement learning process that has been running for some time and is found suffciently close to a strict Nash equilibrium, will reach it with probability one. |
| Keywords: | Strict Nash Equilibrium; Reinforcement Learning |
| JEL: | C92 D83 C72 |
| Date: | 2011–10–07 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:33936&r=gth |
| By: | Brams, Steven J.; Jones, Michael A.; Klamler, Christian |
| Abstract: | A cake is a metaphor for a heterogeneous, divisible good, such as land. A perfect division of cake is efficient (also called Pareto-optimal), envy-free, and equitable. We give an example of a cake in which it is impossible to divide it among three players such that these three properties are satisfied, however many cuts are made. It turns out that two of the three properties can be satisfied by a 3-cut and a 4-cut division, which raises the question of whether the 3-cut division, which is not efficient, or the 4-cut division, which is not envy-free, is more desirable (a 2-cut division can at best satisfy either envy-freeness or equitability but not both). We prove that no perfect division exists for an extension of the example for three or more players. |
| Keywords: | Cake-cutting; fair division; efficiency; envy-freeness; equitability; heterogeneous good |
| JEL: | D71 D63 D30 D74 D61 C61 C72 |
| Date: | 2011–10–22 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:34264&r=gth |
| By: | Noussair, Charles; van Soest, Daan; Stoop, Jan |
| Abstract: | We report a framed field experiment, in which we study the effectiveness of punishment and reward in sustaining cooperation in a social dilemma. Punishments tend to be directed at non-cooperators and rewards are assigned by those who are relatively cooperative. In contrast to the results typically found in laboratory experiments, however, we find that punishments and rewards fail to increase cooperation. |
| Keywords: | Field experiment; public goods game; social preferences; punishment; reward |
| JEL: | C92 C93 C72 |
| Date: | 2011–09–26 |
| URL: | http://d.repec.org/n?u=RePEc:pra:mprapa:34067&r=gth |
| By: | Murat Kurt (University of Pittsburgh); Mark S. Roberts (University of Pittsburgh); Andrew J. Schaefer (University of Pittsburgh); M. Utku Ünver (Boston College) |
| Abstract: | End-stage renal disease (ESRD) is the ninth-leading cause of death in the U.S. Transplantation is the most viable renal replacement therapy for ESRD patients, but there is a severe disparity between the demand for kidneys for transplantation and the supply. This shortage is further complicated by incompatibilities in blood-type and antigen matching between patient-donor pairs. Paired kidney exchange (PKE), a cross-exchange of kidneys among incompatible patient-donor pairs, overcomes many difficulties in matching patients with incompatible donors. In a typical PKE, transplantation surgeries take place simultaneously so that no donor may renege after her intended recipient receives the kidney. Therefore, in a PKE, the occurrence of a transplantation requires compatibility among the pairs' willingnesses to exchange. We consider an arbitrary number of autonomous patients with probabilistically evolving health statuses in a prearranged PKE, and model their transplant timing decisions as a discrete-time non-zero-sum noncooperative stochastic game. We explore necessary and sufficient conditions for patients' decisions to be a stationary-perfect equilibrium, and formulate a mixed-integer linear programming representation of equilibrium constraints, which provides a characterization of the socially optimal stationary-perfect equilibria. We carefully calibrate our model using a large scale nationally representative clinical data, and empirically confirm that randomized strategies, which are less consistent with clinical practice and rationality of the patients, do not yield a significant social welfare gain over pure strategies. We also quantify the social welfare loss due to patient autonomy and demonstrate that maximizing the number of transplants may be undesirable. Our results highlight the importance of the timing of an exchange and the disease severity on matching patient-donor pairs. |
| Keywords: | medical decision making, paired kidney exchange, game theory, Markov decision processes, integer programming |
| JEL: | C78 I11 |
| Date: | 2011–10–10 |
| URL: | http://d.repec.org/n?u=RePEc:boc:bocoec:785&r=gth |
| By: | Maria Laura Pesce (Università di Napoli Federico II and CSEF) |
| Abstract: | In most economies, a fair allocation does not exist. Thus, it seems that we are condemned to live in an unfair world, since we are not happy with what we have and we look at the others with envious eyes. In this paper we want to give an hope for a more equitable society. |
| Keywords: | Asymmetric information; fair allocation; constrained market equilibrium; Maximin and Bayesian expected utility function. |
| JEL: | D63 D82 |
| Date: | 2011–10–10 |
| URL: | http://d.repec.org/n?u=RePEc:sef:csefwp:292&r=gth |