A PGM framework for recursive modeling of players in simple sequential Bayesian games

We consider the situation where two agents try to solve each their own task in a common environment. In particular, we study simple sequential Bayesian games with unlimited time horizon where two players share a visible scene, but where the tasks (termed assignments) of the players are private information. We present an influence diagram framework for representing simple type of games, where each player holds private information. The framework is used to model the analysis depth and time horizon of the opponent and to determine an optimal policy under various assumptions on analysis depth of the opponent. Not surprisingly, the framework turns out to have severe complexity problems even in simple scenarios due to the size of the relevant past. We propose two approaches for approximation. One approach is to use Limited Memory Influence Diagrams (LIMIDs) in which we convert the influence diagram into a set of Bayesian networks and perform single policy update. The other approach is information enhancement, where it is assumed that the opponent in a few moves will know your assignment. Empirical results are presented using a simple board game.     

Single-payoff farsighted stable sets in strategic games with dominant punishment strategies

We investigate farsighted stable sets in a class of strategic games with dominant punishment strategies. In this class of games, each player has a strategy that uniformly minimizes the other players’ payoffs for any given strategies chosen by these other players. We particularly investigate a special class of farsighted stable sets, each of which consists of strategy profiles yielding a single payoff vector. We call such a farsighted stable set as a single-payoff farsighted stable set. We propose a concept called an inclusive set that completely characterizes single-payoff farsighted stable sets in strategic games with dominant punishment strategies. We also show that the set of payoff vectors yielded by single-payoff farsighted stable sets is closely related to the strict \(\alpha \)-core in a strategic game. Furthermore, we apply the results to strategic games where each player has two strategies and strategic games associated with some market models.     

三步矩阵对策上的无中生有计及其实例

基于一个历史实例及假定:①三步矩阵对策中赢得矩阵都不变,②每步都是局中人1先行动,③对于每步对策,局中人2观测不到对手究竟使用了何策略;但局中人1可以观测到对手所用的策略,建立了三步矩阵对策上的无中生有计(《三十六计》中的第七计)的对策模型.研究了当局中人2中计,半识破和完全识破对手的无中生有计时的赢得和所用的策略的情况.并用上述实例对模型作了说明.     

Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Individual and group stability in neutral restrictions of hedonic games

We consider a class of coalition formation games called hedonic games, i.e., games in which the utility of a player is completely determined by the coalition that the player belongs to. We first define the class of subset-additive hedonic games and show that they have the same representation power as the class of hedonic games. We then define a restriction of subset-additive hedonic games that we call subset-neutral hedonic games and generalize a result by Bogomolnaia and Jackson (2002) by showing the existence of a Nash stable partition and an individually stable partition in such games. We also consider neutrally anonymous hedonic games and show that they form a subclass of the subset-additive hedonic games. Finally, we show the existence of a core stable partition that is also individually stable in neutrally anonymous hedonic games by exhibiting an algorithm to compute such a partition.     

Congestion games with failures

We introduce a new class of games, congestion games with failures (CGFs), which allows for resource failures in congestion games. In a CGF, players share a common set of resources (service providers), where each service provider (SP) may fail with some known probability (that may be constant or depend on the congestion on the resource). For reliability reasons, a player may choose a subset of the SPs in order to try and perform his task. The cost of a player for utilizing any SP is a function of the total number of players using this SP. A main feature of this setting is that the cost for a player for successful completion of his task is the minimum of the costs of his successful attempts. We show that although CGFs do not, in general, admit a (generalized ordinal) potential function and the finite improvement property (and thus are not isomorphic to congestion games), they always possess a pure strategy Nash equilibrium. Moreover, every best reply dynamics converges to an equilibrium in any given CGF, and the SPs’ congestion experienced in different equilibria is (almost) unique. Furthermore, we provide an efficient procedure for computing a pure strategy equilibrium in CGFs and show that every best equilibrium (one minimizing the sum of the players’ disutilities) is semi-strong. Finally, for the subclass of symmetric CGFs we give a constructive characterization of best and worst equilibria.     

Share functions for cooperative games with levels structure of cooperation

In a standard TU-game it is assumed that every subset of the player set N can form a coalition and earn its worth. One of the first models where restrictions in cooperation are considered is the one of games with coalition structure of Aumann and Drèze (1974). They assumed that the player set is partitioned into unions and that players can only cooperate within their own union. Owen (1977) introduced a value for games with coalition structure under the assumption that also the unions can cooperate among them. Winter (1989) extended this value to games with levels structure of cooperation, which consists of a game and a finite sequence of partitions defined on the player set, each of them being coarser than the previous one.     

Partizan octal games: Partizan subtraction games

A subtraction gameS=(s ₁, ...,s _k)is a two-player game played with a pile of tokens where each player at his turn removes a number ofm of tokens providedmεS. The player first unable to move loses, his opponent wins. This impartial game becomes partizan if, instead of one setS, two finite setsS _L andS _R are given: Left removes tokens as specified byS _L, right according toS _R. We say thatS _L dominatesS _R if for all sufficiently large piles Left wins both as first and as second player. We exhibit a curious property of dominance and provide two subclasses of games in which a dominance relation prevails. We further prove that all partizan subtraction games areperiodic, and investigatepure periodicity.     

Computation of equilibria and the price of anarchy in bottleneck congestion games

We study Nash and strong equilibria in weighted and unweighted bottleneck games. In such a game every (weighted) player chooses a subset of a given set of resources as her strategy. The cost of a resource depends on the total weight of players choosing it and the personal cost every player tries to minimize is the cost of the most expensive resource in her strategy, the bottleneck value. To derive efficient algorithms for finding equilibria in unweighted games, we generalize a transformation of a bottleneck game into a congestion game with exponential cost functions introduced by Caragiannis et al. (2005). For weighted routing games we show that Greedy methods give Nash equilibria in extension-parallel and series-parallel graphs. Furthermore, we show that the strong Price of Anarchy can be arbitrarily high for special cases and give tight bounds depending on the topology of the graph, the number and weights of the users and the degree of the polynomial latency functions. Additionally we investigate the existence of equilibria in generalized bottleneck games, where players aim to minimize not only the bottleneck value, but also the second most expensive resource in their strategy and so on.     

Topological games and continuity of group operations

We consider a topological game GΠ involving two players α and β and show that, for a paratopological group, the absence of a winning strategy for player β implies the group is a topological one. We provide a large class of topological spaces X for which the absence of a winning strategy for player β is equivalent to the requirement that X is a Baire space. This allows to extend the class of paratopological or semitopological groups for which one can prove that they are, actually, topological groups.Conditions of the type “existence of a winning strategy for the player α” or “absence of a winning strategy for the player β” are frequently used in mathematics. Though convenient and satisfactory for theoretical considerations, such conditions do not reveal much about the internal structure of the topological space where they hold. We show that the existence of a winning strategy for any of the players in all games of Banach-Mazur type can be expressed in terms of “saturated sieves” of open sets.     

Average-discounted equilibria in stochastic games

In stochastic games with finite state and action spaces, we examine existence of equilibria where player 1 uses the limiting average reward and player 2 a discounted reward for the evaluations of the respective payoff sequences. By the nature of these rewards, the far future determines player 1's reward, while player 2 is rather interested in the near future. This gives rise to a natural cooperation between the players along the course of the play. First we show the existence of stationary ε-equilibria, for all ε>0, in these games. However, besides these stationary ε-equilibria, there also exist ε-equilibria, in terms of only slightly more complex ultimately stationary strategies, which are rather in the spirit of these games because, after a large stage when the discounted game is not interesting any longer, the players cooperate to guarantee the highest feasible reward to player 1. Moreover, we analyze an interesting example demonstrating that 0-equilibria do not necessarily exist in these games, not even in terms of history dependent strategies. Finally, we examine special classes of stochastic games with specific conditions on the transition and payoff structures. Several examples are given to clarify all these issues.     

Bounded rationality and correlated equilibria

We study an interactive framework that explicitly allows for nonrational behavior. We do not place any restrictions on how players’ behavior deviates from rationality, but rather, on players’ higher-order beliefs about the frequency of such deviations. We assume that there exists a probability p such that all players believe, with at least probability p, that their opponents play rationally. This, together with the assumption of a common prior, leads to what we call the set of p-rational outcomes, which we define and characterize for arbitrary probability p. We then show that this set varies continuously in p and converges to the set of correlated equilibria as p approaches 1, thus establishing robustness of the correlated equilibrium concept to relaxing rationality and common knowledge of rationality. The p-rational outcomes are easy to compute, also for games of incomplete information. Importantly, they can be applied to observed frequencies of play for arbitrary normal-form games to derive a measure of rationality \(\overline{p}\) that bounds from below the probability with which any given player chooses actions consistent with payoff maximization and common knowledge of payoff maximization.     

An adaptive algorithm for discrete-time differential games

This paper presents an algorithm for a player to improve his performance by adapting optimally over his non-optimally playing opponent in discrete-time differential games. The algorithm first estimates the opponent's actual strategies and then constructs an adaptive strategy for the player. The adaptive strategy is periodically updated according to the opponent's behavior using the neighboring optimal closed-loop solution technique. An example is given which demonstrates the superiority of this algorithm over the conventional one which assumes that the opponent plays optimally.     

Numerical solution of special matrix games

A method is proposed for solving large-sized matrix games (zero-sum games) of special form for which there is a fast algorithm of searching for the best pure strategy of a player given any mixed strategy of the opponent. Examples of problems leading to such games are given. The method proposed is numerically compared with the Brown-Robinson iterative method.     

Formulating an <Emphasis Type="Italic">n</Emphasis>-person noncooperative game as a tensor complementarity problem

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.     

Game theory with translucent players

A traditional assumption in game theory is that players are opaque to one another—if a player changes strategies, then this change in strategies does not affect the choice of other players’ strategies. In many situations this is an unrealistic assumption. We develop a framework for reasoning about games where the players may be translucent to one another; in particular, a player may believe that if she were to change strategies, then the other player would also change strategies. Translucent players may achieve significantly more efficient outcomes than opaque ones. Our main result is a characterization of strategies consistent with appropriate analogues of common belief of rationality. Common Counterfactual Belief of Rationality (CCBR) holds if (1) everyone is rational, (2) everyone counterfactually believes that everyone else is rational (i.e., all players i believe that everyone else would still be rational even if i were to switch strategies), (3) everyone counterfactually believes that everyone else is rational, and counterfactually believes that everyone else is rational, and so on. CCBR characterizes the set of strategies surviving iterated removal of minimax-dominated strategies, where a strategy \(\sigma \) for player i is minimax dominated by \(\sigma '\) if the worst-case payoff for i using \(\sigma '\) is better than the best possible payoff using \(\sigma \).     

Two-noisy-versus-one-silent duel with equal accuracy functions

This paper deals with the two-noisy-versus-one-silent duel which is still open, as pointed out by Styszyński (Ref. 1). Player I has a noisy gun with two bullets, and player II has a silent gun with one bullet. Each player fires his bullets aiming at his opponent at any time in [0, 1]. The accuracy function (the probability that one player hits his opponent if he fires at timet) isp(t)=t for each player. If player I hits player II, without being hit himself before, the payoff of the duel is +1; if player I is hit by player II, without hitting player II before, the payoff is taken to be ?1. In this paper, we determine the optimal strategies and the value of the game. The strategy for player II depends explicitly on the firing moment of player I's first shot.     

Constrained games as complementary eigenvalue problems

A class of two-person nonzero sum games where the strategy choices are constrained in some form for each player is analyzed here to show the equivalent nonlinear programs which must be solved for the Cournot-Nash equilibrium. This equilibrium solution is shown in appropriate cases to lead to complementary eigenvalue problems, which have applications in normal solutions of stochastic LP models and optimal design problems in linear regression theory.     

Pure strategy Nash equilibria and the probabilistic prospects of Stackelberg players

We consider the set of all m×n bimatrix games with ordinal payoffs. We show that on the subset E of such games possessing at least one pure strategy Nash equilibrium, both players prefer the role of leader to that of follower in the corresponding Stackelberg games. This preference is in the sense of first-degree stochastic dominance by leader payoffs of follower payoffs. It follows easily that on the complement of E, the follower’s role is preferred in the same sense. Thus we see a tendency for leadership preference to obtain in the presence of multiple pure strategy Nash equilibria in the underlying game.     

Static search games played over graphs and general metric spaces

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.