190,859 research outputs found
Correlated Nash Equilibrium
No full textNash equilibrium presumes that players have expected utility preferences, and therefore the beliefs of each player are represented by a probability measure. Motivated by Ellsberg-type behavior, which contradicts the probabilistic representation of beliefs, we generalize Nash equilibrium in n-player strategic games to allow for preferences conforming to the maxmin expected utility model of Gilboa and Schmeidler [Journal of Mathematical Economics, 18 (1989), 141–153]. With no strings attached, our equilibrium concept can be characterized by the suitably modified epistemic conditions for Nash equilibrium.Agreeing to disagree, Correlated equilibrium, Epistemic conditions, Knightian uncertainty, Multiple priors, Nash equilibrium
Partially-honest Nash implementation: Characterization results
No full textThis paper studies implementation problems in the wake of a recent trend of implementation of non-consequentialist nature, which draws on the evidence taken from experimental and behavioral economics. Specifically, following the seminal works by Matsushima (2008) and Dutta and Sen (2009), the paper considers implementation problems with partially-honest agents, which presume that there is at least one individual in society who concerns herself with not only outcomes but also honest behavior at least in a limited manner. Given this setting, the paper provides a general characterization of Nash implementation with partially-honest individuals. It also provides the necessary and sufficient condition for Nash implementation with partially-honest individuals by mechanisms with some types of strategy-space reductions. As a consequence, it shows that in contrast to the case of the standard framework, the equivalence between Nash implementation and Nash implementation with strategy space reduction no longer holds.Nash implementation, canonical-mechanisms, s-mechanisms, self-relevant mechanisms, partial-honesty, permissive results
A Distributed Algorithm for Optimising over Pure Strategy Nash Equilibria
No full textWe develop an efficient algorithm for computing pure strategy Nash equilibria that satisfy various criteria (such as the utilitarian or Nash--Bernoulli social welfare functions) in games with sparse interaction structure. Our algorithm, called Valued Nash Propagation (VNP), integrates the optimisation problem of maximising a criterion with the constraint satisfaction problem of finding a game's equilibria to construct a criterion that defines a c-semiring. Given a suitably compact game structure, this criterion can be efficiently optimised using message-passing. To this end, we first show that VNP is complete in games whose interaction structure forms a hypertree. Then, we go on to provide theoretic and empirical results justifying its use on games with arbitrary structure; in particular, we show that it computes the optimum >82% of the time and otherwise selects an equilibrium that is always within 2% of the optimum on average
Stability and Nash implementation in matching markets with couples
No full textHaake C-J, Klaus B. Stability and Nash implementation in matching markets with couples. Working Papers. Institute of Mathematical Economics. Vol 399. Bielefeld: Universität Bielefeld; 2008.We consider two-sided matching markets with couples. First, we extend a result by Klaus and Klijn (2005, Theorem 3.3) and show that for any weakly responsive couples market there always exists a "double stable" matching, i.e., a matching that is stable for the couples market and for any associated singles market. Second, we show that for weakly responsive couples markets the associated stable correspondence is (Maskin) monotonic and Nash implementable. In contrast, the correspondence that assigns all double stable matchings is neither monotonic nor Nash implementable
Recommended from our members
An Experiment on Nash Implementation
No full textWe perform an experimental test of a modification of the controversial canonical mechanism for Nash implementation, using three subjects in non-repeated groups, as well as three outcomes, states of nature, and integer choices. We find that this mechanism successfully implements the desired
outcome a large majority of the time, providing empirical evidence for the feasibility of such implementation. In addition, the performance is further improved by imposing a fine on a dissident,
so that the mechanism implements strict Nash equilibria. While our environment is stylized, our results offer hope that experiments can identify reasonable features for practical implementation mechanisms.Publicad
Two-agent Nash implementation: A new result
No full text[Moore and Repullo, \emph{Econometrica} \textbf{58} (1990) 1083-1099] and [Dutta and Sen, \emph{Rev. Econom. Stud.} \textbf{58} (1991) 121-128] are two fundamental papers on two-agent Nash implementation. Both of them are based on Maskin's classic paper [Maskin, \emph{Rev. Econom. Stud.} \textbf{66} (1999) 23-38]. A recent work [Wu, http://arxiv.org/abs/1002.4294, \emph{Inter. J. Quantum Information}, 2010 (accepted)] shows that when an additional condition is satisfied, the Maskin's theorem will no longer hold by using a quantum mechanism. Furthermore, this result holds in the macro world by using an algorithmic mechanism. In this paper, we will investigate two-agent Nash implementation by virtue of the algorithmic mechanism. The main result is: The sufficient and necessary conditions for Nash implementation with two agents shall be amended, not only in the quantum world, but also in the macro world.Quantum game theory; Mechanism design; Nash implementation.
Choice-Nash Equilibria
No full textWe provide existence results for equilibria of games where players employ abstract (non binary) choice rules. Such results are shown to encompass as a relevant instance that of games where players have (non-transitive) SSB (Skew-Symmetric Bilinear) preferences, as will as other well-known transitive (e. g. Nash´s) and non-transitive (e. g. Shafer and Sonnenschein´s) models in the literature. Further, our general model contains games where players display procedural rationality.
Computing Good Nash Equilibria in Graphical Games
No full textThis paper addresses the problem of fair equilibrium selection in graphical games. Our approach is based on the data structure called the {\em best response policy}, which was proposed by Kearns et al.~\cite{kls} as a way to represent all Nash equilibria of a graphical game. In~\cite{egg}, it was shown that the best response policy has polynomial size as long as the underlying graph is a path. In this paper, we show that if the underlying graph is a bounded-degree tree and the best response policy has polynomial size then there is an efficient algorithm which constructs a Nash equilibrium that guarantees certain payoffs to all participants. Another attractive solution concept is a Nash equilibrium that maximizes the social welfare. We show that, while exactly computing the latter is infeasible (we prove that solving this problem may involve algebraic numbers of an arbitrarily high degree), there exists an FPTAS for finding such an equilibrium as long as the best response policy has polynomial size. These two algorithms can be combined to produce Nash equilibria that satisfy various fairness criteria
Monotonicity and Nash implementation in matching markets with contracts
No full textHaake C-J, Klaus B. Monotonicity and Nash implementation in matching markets with contracts. Working Papers. Institute of Mathematical Economics. Vol 372. Bielefeld: Universität Bielefeld; 2005.We consider general two-sided matching markets, so-called matching with contracts markets as introduced by Hatfield and Milgrom (2005), and analyze (Maskin) monotonic and Nash implementable solutions. We show that for matching with contracts markets the stable correspondence is monotonic and implementable (Theorems 1 and 3). Furthermore, any solution that is Pareto efficient, individually rational, and monotonic is a supersolution of the stable correspondence (Theorem 2). In other words, the stable correspondence is the minimal solution that is Pareto efficient, individually rational, and implementable
A simplicial algorithm approach to Nash equilibria in concave games
No full textHaake C-J, Su FE. A simplicial algorithm approach to Nash equilibria in concave games. Working Papers. Institute of Mathematical Economics. Vol 382. Bielefeld: Universität Bielefeld; 2006.In this paper we demonstrate a new method for computing approximate Nash equilibria in n-person games. Strategy spaces are assumed to be represented by simplices, while payoff functions are assumed to be concave. Our procedure relies on a simplicial algorithm that traces paths through the set of strategy profiles using a new variant of Sperner's Lemma for labelled triangulations of simplotopes, which we prove in this paper. Our algorithm uses a labelling derived from the satisficing function of Geanakoplos (2003) and can be used to compute approximate Nash equilibria for payoff functions that are not necessarily linear. Finally, in bimatrix games, we can compare our simplicial algorithm to the combinatorial algorithm proposed by Lemke & Howson (1964)
- …
