Nash equilibria in multi-agent motor interactions.

Social interactions in classic cognitive games like the ultimatum game or the prisoner's dilemma typically lead to Nash equilibria when multiple competitive decision makers with perfect knowledge select optimal strategies. However, in evolutionary game theory it has been shown that Nash equilibria can also arise as attractors in dynamical systems that can describe, for example, the population dynamics of microorganisms. Similar to such evolutionary dynamics, we find that Nash equilibria arise naturally in motor interactions in which players vie for control and try to minimize effort. When confronted with sensorimotor interaction tasks that correspond to the classical prisoner's dilemma and the rope-pulling game, two-player motor interactions led predominantly to Nash solutions. In contrast, when a single player took both roles, playing the sensorimotor game bimanually, cooperative solutions were found. Our methodology opens up a new avenue for the study of human motor interactions within a game theoretic framework, suggesting that the coupling of motor systems can lead to game theoretic solutions.

A notion of subgame perfect Nash equilibrium under knightian uncertainty

We define a subgame perfect Nash equilibrium under Knightian uncertainty for two players, by means of a recursive backward induction procedure. We prove an extension of the Zermelo-von Neumann-Kuhn Theorem for games of perfect information, i. e., that the recursive procedure generates a Nash equilibrium under uncertainty (Dow and Werlang(1994)) of the whole game. We apply the notion for two well known games: the chain store and the centipede. On the one hand, we show that subgame perfection under Knightian uncertainty explains the chain store paradox in a one shot version. On the other hand, we show that subgame perfection under uncertainty does not account for the leaving behavior observed in the centipede game. This is in contrast to Dow, Orioli and Werlang(1996) where we explain by means of Nash equilibria under uncertainty (but not subgame perfect) the experiments of McKelvey and Palfrey(1992). Finally, we show that there may be nontrivial subgame perfect equilibria under uncertainty in more complex extensive form games, as in the case of the finitely repeated prisoner's dilemma, which accounts for cooperation in early stages of the game.

A notion of subgame perfect nash equilibrium under knightian uncertainty

We define a subgame perfect Nash equilibrium under Knightian uncertainty for two players, by means of a recursive backward induction procedure. We prove an extension of the Zermelo-von Neumann-Kuhn Theorem for games of perfect information, i. e., that the recursive procedure generates a Nash equilibrium under uncertainty (Dow and Werlang(1994)) of the whole game. We apply the notion for two well known games: the chain store and the centipede. On the one hand, we show that subgame perfection under Knightian uncertainty explains the chain store paradox in a one shot version. On the other hand, we show that subgame perfection under uncertainty does not account for the leaving behavior observed in the centipede game. This is in contrast to Dow, Orioli and Werlang(1996) where we explain by means of Nash equilibria under uncertainty (but not subgame perfect) the experiments of McKelvey and Palfrey(1992). Finally, we show that there may be nontrivial subgame perfect equilibria under uncertainty in more complex extensive form games, as in the case of the finitely repeated prisoner's dilemma, which accounts for cooperation in early stages of the game .

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium.

General-sum stochastic games: Verifiability conditions for Nash equilibria

Unlike zero-sum stochastic games, a difficult problem in general-sum stochastic games is to obtain verifiable conditions for Nash equilibria. We show in this paper that by splitting an associated non-linear optimization problem into several sub-problems, characterization of Nash equilibria in a general-sum discounted stochastic games is possible. Using the aforementioned sub-problems, we in fact derive a set of necessary and sufficient verifiable conditions (termed KKT-SP conditions) for a strategy-pair to result in Nash equilibrium. Also, we show that any algorithm which tracks the zero of the gradient of the Lagrangian of every sub-problem provides a Nash strategy-pair. (c) 2012 Elsevier Ltd. All rights reserved.

Endogenous Timing in Pollution Control: Stackelberg versus Cournot-Nash Equilibria

27 p.

Nash equilibria of network formation games under consent

We investigate the Nash equilibria of game theoretic models of network formation based on explicit consent in link formation. These so-called “consent models” explicitly take account of link formation costs. We provide characterizations of Nash equilibria of such consent models under both one-sided and two-sided costs of link formation. We relate these equilibrium concepts to link-based stability concepts, in particular strong link deletion proofness.

Decentralized Computation of Pareto Optimal Pure Nash Equilibria of Boolean Games with Privacy Concerns

In Boolean games, agents try to reach a goal formulated as a Boolean formula. These games are attractive because of their compact representations. However, few methods are available to compute the solutions and they are either limited or do not take privacy or communication concerns into account. In this paper we propose the use of an algorithm related to reinforcement learning to address this problem. Our method is decentralized in the sense that agents try to achieve their goals without knowledge of the other agents’ goals. We prove that this is a sound method to compute a Pareto optimal pure Nash equilibrium for an interesting class of Boolean games. Experimental results are used to investigate the performance of the algorithm.

Spike-based decision learning of nash equilibria in two-player games

Humans and animals face decision tasks in an uncertain multi-agent environment where an agent's strategy may change in time due to the co-adaptation of others strategies. The neuronal substrate and the computational algorithms underlying such adaptive decision making, however, is largely unknown. We propose a population coding model of spiking neurons with a policy gradient procedure that successfully acquires optimal strategies for classical game-theoretical tasks. The suggested population reinforcement learning reproduces data from human behavioral experiments for the blackjack and the inspector game. It performs optimally according to a pure (deterministic) and mixed (stochastic) Nash equilibrium, respectively. In contrast, temporal-difference(TD)-learning, covariance-learning, and basic reinforcement learning fail to perform optimally for the stochastic strategy. Spike-based population reinforcement learning, shown to follow the stochastic reward gradient, is therefore a viable candidate to explain automated decision learning of a Nash equilibrium in two-player games.

Bounded Rationality and Repeated Network Formation

We define a finite-horizon repeated network formation game with consent and study the differences induced by two levels of individual rationality. Perfectly rational players will remain unconnected at the equilibrium, while nonempty equilibrium networks may form when players are assumed to behave as finite automata of limited complexity. We provide structural properties of the sequences of networks which are likely to form in Nash and subgame perfect Nash equilibria of the repeated game. For instance, players can form totally different connected networks at each period or the sequence of networks can exhibit a total order relationship.

Strategic interactions of urban land developers in the housing market

This thesis studies the supply side of the housing market taking into account the strategic interactions that occur between urban land developers. The thesis starts by reviewing the literature on new housing supply, concluding that there are very few studies where strategic interactions are taken into account. Next, we develop a model with two urban land developers, who rst decide the quality of housing and then compete in prices, considering that the marginal production costs depend on the housing quality. First, we analyze the price competition game and characterize the Nash equilibrium of the price game. Finally, we examine the rst stage of the game and determine numerically the subgame perfect Nash equilibrium (SPNE) of the quality-price game. In the price competition game, our results show that the equilibrium price of an urban land developer is an increasing function of its own quality, while it is a non-monotonic function of the rival s quality. The behavior of the equilibrium pro ts reveals that, in general, urban land developers gain by di¤erentiating their quality. However, the urban land developer located at the Central Business District (CBD), may prefer to have the same quality than the rival when transportation costs are high by exploiting its locational advantage. The analysis of the rst stage of the game also reveals that, in general, the rms best response is to di¤erentiate their quality and that, in most cases, there are two subgame perfect Nash equilibria that involve quality di¤erentiation. However, the results depend on transportation costs and the quality valuation parameter. For small quality valuations, in equilibrium, the market is not fully covered and, if the unit transportation costs are high, only the urban land developers located at the CBD operates. For higher quality valuations, all the consumers are served. Furthermore, the equilibrium qualities and pro ts are increasing with quality valuation parameter. RESUMO: Esta tese estuda a oferta no mercado da habitação, tendo em conta as interações es- tratégicas que ocorrem entre os produtores de habitação. A tese revê a literatura sobre a oferta de habitação, concluindo que existem poucos estudos que tenham tido em conta as interações estratégicas. De seguida, desenvolvemos um modelo com dois produtores de habitação, que primeiro decidem a qualidade da habitação e depois competem em preços, considerando que os custos marginais de produção dependem da qualidade. Primeiro analisamos o jogo em preços e caracterizamos o equilíbrio de Nash. Posteriormente, ex- aminamos o primeiro estágio do jogo e determinamos numericamente o equilíbrio perfeito em todos os subjogos (SPNE) do jogo. No jogo de competição em preços, os resultados mostram que, o preço de equilíbrio, é uma função crescente da qualidade da habitação, sendo uma função não monótona da qualidade do rival. O lucro de equilíbrio revela que, geralmente, os produtores de habitação têm ganhos em diferenciar a qualidade. No entanto, o produtor localizado no Centro (CBD), pode preferir oferecer a mesma qualidade que o rival, caso os custos unitários de transporte sejam elevados, através da sua vantagem de localização. A análise do primeiro estágio do jogo, revela que, geralmente, a melhor resposta de um produtor é a de diferenciar a qualidade. Na maior parte dos casos existem dois SPNE que envolvem essa diferenciação. No entanto, os resultados dependem dos custos unitários de transporte e da valorização da qualidade por parte do consumidor. Para uma reduzida valorização da qualidade, em equilíbrio, o mercado não é totalmente coberto e, se o custo unitário de transporte é elevado, apenas o produtor localizado no CBD opera no mercado. Para uma valorização elevada da qualidade, todos os consumidores são servidos. Além disso, as qualidades e os lucros de equilíbrio são crescentes com a valorização da qualidade.

A Behavioral Foundation for Models of Evolutionary Drift

Binmore and Samuelson (1999) have shown that perturbations (drift) are crucial to study the stability properties of Nash equilibria. We contribute to this literature by providing a behavioural foundation for models of evolutionary drift. In particular, this article introduces a microeconomic model of drift based on the similarity theory developed by Tversky (1977), Kahneman and Tversky (1979) and Rubinstein (1988),(1998). An innovation with respect to those works is that we deal with similarity relations that are derived from the perception that each agent has about how well he is playing the game. In addition, the similarity relations are adapted to a dynamic setting. We obtain different models of drift depending on how we model the agent´s assessment of his behaviour in the game. The examples of the ultimatum game and the chain-store game are used to show the conditions for each model to stabilize elements in the component of Nash equilibria that are not subgame- perfect. It is also shown how some models approximate the laboratory data about those games while others match the data.

Partial Cooperative Equilibria: Existence and Characterization

We study the solution concepts of partial cooperative Cournot-Nash equilibria and partial cooperative Stackelberg equilibria. The partial cooperative Cournot-Nash equilibrium is axiomatically characterized by using notions of rationality, consistency and converse consistency with regard to reduced games. We also establish sufficient conditions for which partial cooperative Cournot-Nash equilibria and partial cooperative Stackelberg equilibria exist in supermodular games. Finally, we provide an application to strategic network formation where such solution concepts may be useful.