An Approach to Fuzzy Noncooperative Nash Games

Systems that involve more than one decision maker are often optimized using the theory of games. In the traditional game theory, it is assumed that each player has a well-defined quantitative utility function over a set of the player decision space. Each player attempts to maximize/minimize his/her own expected utility and each is assumed to know the extensive game in full. At present, it cannot be claimed that the first assumption has been shown to be true in a wide variety of situations involving complex problems in economics, engineering, social and political sciences due to the difficulty inherent in defining an adequate utility function for each player in these types of problems. On the other hand, in many of such complex problems, each player has a heuristic knowledge of the desires of the other players and a heuristic knowledge of the control choices that they will make in order to meet their ends.In this paper, we utilize fuzzy set theory in order to incorporate the players' heuristic knowledge of decision making into the framework of conventional game theory or ordinal game theory. We define a new approach to N-person static fuzzy noncooperative games and develop a solution concept such as Nash for these types of games. We show that this general formulation of fuzzy noncooperative games can be applied to solve multidecision-making problems where no objective function is specified. The computational procedure is illustrated via application to a multiagent optimization problem dealing with the design and operation of future military operations.     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

From hierarchies to levels: new solutions for games with hierarchical structure

Recently, applications of cooperative game theory to economic allocation problems have gained popularity. In many of these problems, players are organized according to either a hierarchical structure or a levels structure that restrict the players’ possibilities to cooperate. In this paper, we propose three new solutions for games with hierarchical structure and characterize them by properties that relate a player’s payoff to the payoffs of other players located in specific positions in the hierarchical structure relative to that player. To define each solution, we consider a certain mapping that transforms the hierarchical structure into a levels structure, and then we apply the standard generalization of the Shapley value to the class of games with levels structure. Such transformation mappings are studied by means of properties that relate a player’s position in both types of structure.     

Quitting games – An example

Quitting games are multi-player sequential games in which, at every stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; each player i then receives a payoff r _S ⁱ, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is zero.? We exhibit a four-player quitting game, where the “simplest” equilibrium is periodic with period two. We argue that this implies that all known methods to prove existence of an equilibrium payoff in multi-player stochastic games are therefore bound to fail in general, and provide some geometric intuition for this phenomenon. Received: October 2001     

Epistemic characterizations of iterated deletion of inferior strategy profiles in preference-based type spaces

Bonanno (Logics and the foundations of game and decision theory, Amsterdam University Press, Amsterdam, 2008) provides an epistemic characterization for the solution concept of iterated deletion of inferior strategy profiles (IDIP) by embedding strategic-form games with ordinal payoffs in non-probabilistic epistemic models which are built on Kripke frames. In this paper, we will follow the event-based approach to epistemic game theory and supplement strategic games with type space models, where each type is associated with a preference relation on the state space. In such a framework, IDIP can be characterized by the conditions that at least one player has correct beliefs about the state of the world and that there is common belief that every player is rational, has correct beliefs about the state of the world and has strictly monotone preferences. Moreover, we shall compare the epistemic motivations for IDIP and its mixed strategy variant known as strong rationalizability (SR). Presuppose the above conditions. Whenever there is also common belief that players’ preferences are representable by some expected utility function IDIP still applies. But if there is common belief that players’ preferences are representable by some expected payoff function, then SR results.     

Repeated proximity games

We consider repeated games with complete information and imperfect monitoring, where each player is assigned a fixed subset of players and only observes the moves chosen by the players in this subset. This structure is naturally represented by a directed graph. We prove that a generalized folk theorem holds for any payoff function if and only if the graph is 2-connected, and then extend this result to the context of finitely repeated games. Received June 1997/Revised version March 1998     

Computing payoff allocations in the approximate core of linear programming games in a privacy-preserving manner

We investigate privacy-preserving ways of allocating payoffs among players participating in a joint venture, using tools from cooperative game theory and differential privacy. In particular, we examine linear programming games, an important class of cooperative games that model a myriad of payoff sharing problems, including those from logistics and network design. We show that we can compute a payoff allocation in the approximate core of these games in a way that satisfies joint differential privacy.     

Fictitious play in coordination games

We study the Fictitious Play process with bounded and unbounded recall in pure coordination games for which failing to coordinate yields a payoff of zero for both players. It is shown that every Fictitious Play player with bounded recall may fail to coordinate against his own type. On the other hand, players with unbounded recall are shown to coordinate (almost surely) against their own type as well as against players with bounded recall. In particular, this implies that a FP player's realized average utility is (almost surely) at least as large as his minmax payoff in 2×2 coordination games. Received: December 1997/Final version: November 1998     

Periodic stopping games

Stopping games (without simultaneous stopping) are sequential games in which at every stage one of the players is chosen, who decides whether to continue the interaction or stop it, whereby a terminal payoff vector is obtained. Periodic stopping games are stopping games in which both of the processes that define it, the payoff process as well as the process by which players are chosen, are periodic and do not depend on the past choices. We prove that every periodic stopping game without simultaneous stopping, has either periodic subgame perfect ϵ-equilibrium or a subgame perfect 0-equilibrium in pure strategies. This work is part of the master thesis of the author done under the supervision of Prof. Eilon Solan. I am thankful to Prof. Solan for his inspiring guidance. I also thank two anonymous referees of the International Journal of Game Theory for their comments.     

Stochastic games with non-observable actions

We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players.     

Pure subgame-perfect equilibria in free transition games

We consider a class of stochastic games, where each state is identified with a player. At any moment during play, one of the players is called active. The active player can terminate the game, or he can announce any player, who then becomes the active player. There is a non-negative payoff for each player upon termination of the game, which depends only on the player who decided to terminate. We give a combinatorial proof of the existence of subgame-perfect equilibria in pure strategies for the games in our class.     

连续区间策略下二人零和对策问题研究

考虑连续区间策略下的二人零和对策问题,研究其均衡策略的存在性。首先分析了完全信息下的二人零和对策问题,证明了该问题均衡策略的存在性并给出求解方法。然后进一步研究了收益函数不确定的不完全信息二人零和对策问题,在各局中人都认为对方是风险厌恶型的假设下,分析该类对策纯策略均衡的存在性,并通过研究纯策略均衡存在的充要条件给出判断并寻找纯策略均衡解的方法。最后给出一个数值算例,验证本文所提出方法的可行性。     

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.     

On the ordinal equivalence of the Johnston, Banzhaf and Shapley power indices

In this paper, we characterize the games in which Johnston, Shapley-Shubik and Penrose-Banzhaf-Coleman indices are ordinally equivalent, meaning that they rank players in the same way. We prove that these three indices are ordinally equivalent in semicomplete simple games, which is a newly defined class that contains complete games and includes most of the real-world examples of binary voting systems. This result constitutes a twofold extension of Diffo Lambo and Moulen’s result (Diffo Lambo and Moulen, 2002) in the sense that ordinal equivalence emerges for three power indices (not just for the Shapley-Shubik and Penrose-Banzhaf-Coleman indices), and it holds for a class of games strictly larger than the class of complete games.     

Preferred coalitions in cooperative differential games

There are many interesting situations which can be described by anN-person general-sum differential game. Such games are characterized by the fact that the strategy of each player depends upon reasonable assumptions about the strategies of the remaining players; and, thus, these games cannot be considered asN uncoupled optimal control problems. In such cases, we say that the game is not strictly competitive, but involves a mutual interest which makes it possible for all of the players to reduce their costs by cooperating with one another, provided the resulting agreement can be enforced. When cooperation is allowed and there are more than two players, there is always the question of whether all possible subcoalitions will be formed with equal ease. This work considers the situation in which a particular subcoalition is preferred. A theory of general-sum games with preferred coalitions is presented, together with constructive examples of alternative approaches which are unsatisfactory.     

不确定偏好序下的双边匹配博弈

针对带有不确定偏好序的双边匹配问题,现有方法大都仅注重整体收益之和,忽略了参与人的个体收益以及在交互选择中的策略运用.基于最大满意度准则,给出不确定序下的收益（满意度）矩阵的推导过程;然后,从个体理性视角,结合矩阵博弈的思想构建一种兼顾整体和个体收益的博弈匹配优化模型,并证明模型最优解满足纳什均衡.最后,进一步探讨各种策略选择及其优劣分析.     

On the NP-completeness of finding an optimal strategy in games with common payoffs

Consider a very simple class of (finite) games: after an initial move by nature, each player makes one move. Moreover, the players have common interests: at each node, all the players get the same payoff. We show that the problem of determining whether there exists a joint strategy where each player has an expected payoff of at least r is NP-complete as a function of the number of nodes in the extensive-form representation of the game. Received January 2001/Final version May 1, 2001     

Differential games with mixed leadership: The open-loop solution

This paper introduces the notion of mixed leadership in nonzero-sum differential games, where there is no fixed hierarchy in decision making with respect to the players. Whether a particular player is leader or follower depends on the instrument variable s/he is controlling, and it is possible for a player to be both leader and follower, depending on the control variable. The paper studies two-player open-loop differential games in this framework, and obtains a complete set of equations (differential and algebraic) which yield the controls in the mixed-leadership Stackelberg solution. The underlying differential equations are coupled and have mixed-boundary conditions. The paper also discusses the special case of linear-quadratic differential games, in which case solutions to the coupled differential equations can be expressed in terms of solutions to coupled Riccati differential equations which are independent of the state trajectory.     

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.     

A note on NTU convexity

For cooperative games with transferable utility, convexity has turned out to be an important and widely applicable concept. Convexity can be defined in a number of ways, each having its own specific attractions. Basically, these definitions fall into two categories, namely those based on a supermodular interpretation and those based on a marginalistic interpretation. For games with nontransferable utility, however, the literature mainly focuses on two kinds of convexity, ordinal and cardinal convexity, which both extend the supermodular interpretation. In this paper, we analyse three types of convexity for NTU games that generalise the marginalistic interpretation of convexity. Received: December 2000