Search

Battigalli (1997) has shown that in dynamic games with perfect information and without relevant ties, the forward induction concept of extensive-form rationalizability yields the backward induction outcome. In this paper we provide a new proof for this remarkable result, based on four steps. We first show that extensive-form rationalizability can be characterized by the iterated application of a special reduction operator, the strong belief reduction operator. We next prove that this operator satisfies a mild version of monotonicity, which we call monotonicity on reachable histories. This property is used to show that for this operator, every possible order of elimination leads to the same set of outcomes. We finally show that backward induction yields a possible order of elimination for the strong belief reduction operator. These four properties together imply Battigalli's theorem.

There exists a wide gap between the predictions of strategic models of network formation and empirical observations of the characteristics of socio-economic networks. Empirical observations underline a complex structure characterized by fat-tailed degree distribution, short average distance, large clustering coefficient and positive assortativity. Game theoretic models offer a detailed representation of individuals’ incentives but they predict the emergence of much simpler structures than these observed empirically. Random network formation processes, such as preferential attachment, provide a much better fit to empirical observations but generally lack micro-foundations. In order to bridge this gap, we propose to model network formation as extensive games and investigate under which conditions equilibria of these games are observationally equivalent with random network formation process. In particular, we introduce a class of games in which players compete with their predecessors and their successors for the utility induced by the links they form with other nodes in the network. Such sequential competition games can represent a number of strategic economic interactions such as oligopolistic competition in supply networks or diffusion of influence in opinion networks. We show that the focal equilibrium that emerges in this setting is one where players use probability distributions with full support and target the whole network with probabilities inversely proportional, to the utility of each node. Notably, when the utility of a node is inversely proportional to its degree, equilibrium play induces a preferential attachment process.

We introduce and analyze three definitions of equilibrium for finite extensive games with imperfect information and ambiguity averse players. In a setting where players' preferences are represented by maxmin expected utility, as characterized in Gilboa and Schmeidler (1989), our definitions capture the intuition that players may consider the possibility of slight arbitrary mistakes. This generalizes the idea leading to trembling-hand perfect equilibrium as introduced in Selten (1975), by allowing for ambiguous trembles characterized by sets of distributions. We prove existence for two of our equilibrium notions, and relate our de finitions to standard equilibrium concepts with expected utility maximizing players. Our analysis shows that ambiguity aversion can lead to behavioral implications that are distinct from those attained under expected utility maximization, even if ambiguous beliefs only arise from the possibility of slight mistakes in the implementation of unambiguous strategies.

Many experimental studies indicate that people are motivated by reciprocity. Rabin (1993) develops techniques for incorporating such concerns into game theory and economics. His model, however, does not fare well when applied to situations with an interesting dynamic structure (like many experimental games), because it is developed for normal form games in which information about the sequential structure of a strategic situation is suppressed. In this paper we develop a theory of reciprocity for extensive games in which the sequential structure of a strategic situation is made explicit. We propose a new solution concept— sequential reciprocity equilibrium—which is applicable to extensive games, and we prove a general equilibrium existence result. The model is applied in several examples, including some well known experimental games like the Ultimatum game and the Sequential Prisoners’ Dilemma.

Kuhn's Theorem shows that extensive games with perfect recall can equivalently be analyzed using mixed or behavioral strategies, as long as players are expected utility maximizers. This note constructs an example that illustrate the limits of Kuhn's Theorem in an environment with ambiguity averse players who use maxmin decision rule and full Bayesian updating., 7 figures

This present thesis aims to analyse Czechoslovak crisis in 1968 using the game theoretic approach. In the theoretical part of thesis are outlines the basics of game theory, its possibilities and main assumptions as well as the traits that it has in common with some theories of international relations. Consequent part begins with the description of historic events during Czechoslovak crisis of 1968. International circumstances, causes and consequences are also summarized in this part. The practical part of the thesis contains analysis of rational solutions of game-theoretic models that were chosen on the grounds of compatibility with historic events. The outcomes of models were afterwards compared with those historic, to conclude the rational or irrational behavior of the states according to game theory during the crisis.

Technical report TR09-15. Sequential decision-making with multiple agents and imperfect information is commonly modeled as an extensive game. One efficient method for computing Nash equilibria in large, zero-sum, imperfect information games is counterfactual regret minimization (CFR). In the domain of poker, CFR has proven effective, particularly when using a domain-specific augmentation involving chance outcome sampling. In this paper, we describe a general family of domain-independent CFR sample-based algorithms called Monte Carlo counterfactual regret minimization (MCCFR) of which the original and poker-specific versions are special cases. We start by showing that MCCFR performs the same regret updates as CFR on expectation. Then, we introduce two sampling schemes: outcome sampling and external sampling, showing that both have bounded overall regret with high probability. Thus, they can compute an approximate equilibrium using self-play. Finally, we prove a new tighter bound on the regret for the original CFR algorithm and relate this new bound to MCCFR's bounds. We show empirically that, although the sample-based algorithms require more iterations, their lower cost per iteration can lead to dramatically faster convergence in various games. | TRID-ID TR09-15

La comercialización minorista de electricidad fue un monopolio regulado, pero las tendencias a la liberalización de mercados han llegado también a los servicios públicos. Luego es relevante analizar los efectos que esta interacción entre firmas competidoras generará en los precios. Para ello se indaga por un marco que permita explicar el comportamiento estratégico que adoptan las firmas participantes en la actividad de comercialización de electricidad minorista. A partir de la identificación de un conjunto limitado de posibles alternativas de organización empresarial estratégica, se construye un modelo de un juego extensivo que permite identificar el comportamiento óptimo que adoptarán las empresas, tomando en cuenta las actuaciones óptimas de los otros agentes. Además, se propone un análisis de decisiones empresariales eficientes bajo las posibilidades disponibles en el juego, en cuanto a la organización empresarial, la decisión de mantenerse compitiendo o de retirarse y la posibilidad de adquirir a los competidores. El modelo aporta evidencia de que el juego puede proveer mejoras en el bienestar general de la sociedad, pero siempre lo hará primero en los consumidores de altos ingresos, en perjuicio de los consumidores de bajos ingresos. Electricity retail merchandising was a regulated monopoly but market liberalization trends have also reached public utilities, making it relevant to analyze the price effects that such an interaction among competing firms will generate. To do so, this article theoretically seeks a framework to enable explaining the strategic behavior that the firms participating in electricity retail merchandising activities will adopt. After identifying a limited set of possible strategic business organization alternatives, an extensive game model is built, which allows identifying the optimum behavior that the companies will adopt, taking into account the optimum conduct of all other stakeholders. An analysis of efficient business decisions is also proposed, considering the possibilities available in the game regarding the business organization, the decision to keep competitive or to get out of the game, and the possibility of acquiring the competing firms. The model contributes evidence that the game may provide improved general welfare for the society, but it will always do so first for high-income bracket consumers and against low-income bracket consumers.

Cet article poursuit l'analyse logique modale dynamique de la rationalité procédurale dans les jeux proposée par van Benthem [5]. Nous modélisons les jeux extensifs en utilisant une logique des préférences et proposons une analyse de processus analogue à l'induction à rebours. Ceci nous conduit à distinguer deux types de rationalité : la rationalité de la décision et celle des préférences. A ces deux types de rationalité correspondent des tranformations de jeux, pour lesquels nous donnons des contreparties syntaxiques dans une logique modale. Dans le modèle final auquel nous parvenons par les transformations d'un jeu non générique, il peut subsister des chemins qui n'appartiennent à aucun équilibre parfait. Plus généralement la nature des solutions que notre approche peut induire est incompatible avec la nature retrospective des concepts de la théorie des jeux. Nous terminons par quelques remarques sur l'utilité d'une telle approche modale pour l'analyse des jeux en information imparfaite et en rationalité limitée. This paper continues the dynamic modal logic analysis provided by van Benthem [5] of procedural rationality in games. Specifically we look at extensive games, and use preference logic to provide a closer analysis of backward induction type algorithms. This results in distinguishing two kinds of rationality : decision rationality and preference rationality. To these two kinds of rationality correspond game transformations, for which we give syntactic counterparts in a modal logic. In the final model arrived at through transformations of a nongeneric game, there can be paths which are in no subgame-perfect equilibrium. More generally the nature of solutions that our approach can induce is incompatible with the retrospective nature of the usual concepts of game theory. We end the paper with some remarks on potential uses of such a modal logic analysis to the cases of imperfect information or where rationality is bounded.

Technical report TR07-14. Extensive games are a powerful model of multiagent decision-making scenarios with incomplete information. Finding a Nash equilibrium for very large instances of these games has received a great deal of recent attention. In this paper, we describe a new technique for solving large games based on regret minimization. In particular, we introduce the notion of counterfactual regret, which exploits the degree of incomplete information in an extensive game. We show how minimizing counterfactual regret minimizes overall regret, and therefore in self-play can be used to compute a Nash equilibrium. We demonstrate this technique in the domain of poker, showing we can solve abstractions of limit Texas Hold'em with as many as 10^12 states, two orders of magnitude larger than previous methods. | TRID-ID TR07-14

I will show that the semantic structure of a new imperfect-information propositional logic can be described in terms of extensive forms of semantic games. I will discuss some ensuing properties of these games such as imperfect recall, informational consistency, and team playing. Finally, I will suggest a couple of applications that arise in physics, and most notably in quantum theory and quantum logics.

Many experimental studies indicate that people are motivated by reciprocity. Rabin (1993) develops techniques for incorporating such concerns into game theory and economics. His model, however, does not fare well when applied to situations with an interesting dynamic structure (like many experimental games), because it is developed for normal form games in which information about the sequential structure of a strategic situation is suppressed. In this paper we develop a theory of reciprocity for extensive games in which the sequential structure of a strategic situation is made explicit. We propose a new solution concept— sequential reciprocity equilibrium—which is applicable to extensive games, and we prove a general equilibrium existence result. The model is applied in several examples, including some well known experimental games like the Ultimatum game and the Sequential Prisoners’ Dilemma.

Many experimental studies indicate that people are motivated by reciprocity. Rabin (1993) develops techniques for incorporating such concerns into game theory and economics. His model, however, does not fare well when applied to situations with an interesting dynamic structure (like many experimental games), because it is developed for normal form games in which information about the sequential structure of a strategic situation is suppressed. In this paper we develop a theory of reciprocity for extensive games in which the sequential structure of a strategic situation is made explicit. We propose a new solution concept— sequential reciprocity equilibrium—which is applicable to extensive games, and we prove a general equilibrium existence result. The model is applied in several examples, including some well known experimental games like the Ultimatum game and the Sequential Prisoners’ Dilemma.

Many experimental studies indicate that people are motivated by reciprocity. Rabin (1993) develops techniques for incorporating such concerns into game theory and economics. His model, however, does not fare well when applied to situations with an interesting dynamic structure (like many experimental games), because it is developed for normal form games in which information about the sequential structure of a strategic situation is suppressed. In this paper we develop a theory of reciprocity for extensive games in which the sequential structure of a strategic situation is made explicit. We propose a new solution concept— sequential reciprocity equilibrium—which is applicable to extensive games, and we prove a general equilibrium existence result. The model is applied in several examples, including some well known experimental games like the Ultimatum game and the Sequential Prisoners’ Dilemma.

We study the computational complexity of deciding the existence of a Pure Nash Equilibrium or a subgame perfect equilibrium with a given payoff and other related problems in finite multi-player extensive games with perfect information. We first propose three way of representing a game with different degrees of succinctness for the components of the game. We show that when the number of moves of each player is large and the player function and the utilities are represented succinctly the considered problems are PSPACE-complete. In contraposition, when the game is described extensively by means of its associated tree all the problems are decidable in polynomial time.