An application of optimization theory to the study of equilibria for games: a survey

This contribution is a survey about potential games and their applications. In a potential game the information that is sufficient to determine Nash equilibria can be summarized in a single function on the strategy space: the potential function. We show that the potential function enable the application of optimization theory to the study of equilibria. Potential games and their generalizations are presented. Two special classes of games, namely team games and separable games, turn out to be potential games. Several properties satisfied by potential games are discussed and examples from concrete situations as congestion games, global emission games and facility location games are illustrated.     

On some families of cooperative fuzzy games

In a fuzzy cooperative game the players may choose to partially participate in a coalition. A fuzzy coalition consists of a group of participating players along with their participation level. The characteristic function of a fuzzy game specifies the worth of each such coalition. This paper introduces well-known properties of classical cooperative games to the theory of fuzzy games, and studies their interrelations. It deals with convex games, exact games, games with a large core, extendable games and games with a stable core.     

Values for Interior Operator Games

The aim of this paper is to study a new class of cooperative games called interior operator games. These games are additive games restricted by antimatroids. We consider several types of cooperative games as peer group games, big boss games, clan games and information market games and show that all of them are interior operator games. Next, we analyze the properties of these games and compute the Shapley, Banzhaf and Tijs values.     

Monotonic games are spanning network games

Spanning network games, which are a generalization of minimum cost spanning tree games, were introduced by Granot and Maschler (1991), who showed that these games are always monotonic. In this paper a subclass of spanning network games is introduced, namely simplex games, and it is shown that every monotonic game is a simplex game. Hence, the class of spanning network games coincides with the class of monotonic games.     

An average lexicographic value for cooperative games

For games with a non-empty core the Alexia value is introduced, a value which averages the lexicographic maxima of the core. It is seen that the Alexia value coincides with the Shapley value for convex games, and with the nucleolus for strongly compromise admissible games and big boss games. For simple flow games, clan games and compromise stable games an explicit expression and interpretation of the Alexia value is derived. Furthermore it is shown that the reverse Alexia value, defined by averaging the lexicographic minima of the core, coincides with the Alexia value for convex games and compromise stable games.     

Regular simple games

Using Kelley's intersection number (and a variant of it) we define two classes of simple games, the regular and the strongly regular games. We show that the strongly regular games are those in which the set of winning coalitions and the set of losing coalitions can be strictly separated by a finitely additive probability measure. This, in particular, provides a combinatorial characterization for the class of finite weighted majority games within the finite simple games. We also prove that regular games have some nice properties and show that the finite regular games are exactly those simple games which are uniquely determined by their counting vector. This, in particular, generalizes a result of Chow and Lapidot.     

Approximating the least core value and least core of cooperative games with supermodular costs

We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a 3-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time algorithm for computing a cost allocation in the 2-approximate least core of these games. This approximation framework extends naturally to submodular profit cooperative games. For scheduling games, a special class of supermodular cost cooperative games, we give a fully polynomial-time approximation scheme for computing the least core value. For matroid profit games, a special class of submodular profit cooperative games, we give exact polynomial-time algorithms for computing the least core value as well as a least core cost allocation.     

Bargaining sets and the core in partitioning games

Partitioning games are useful on two counts: first, in modeling situations with restricted cooperative possibilities between the agents; second, as a general framework for many unrestricted cooperative games generated by combinatorial optimization problems.We show that the family of partitioning games defined on a fixed basic collection is closed under the strategic equivalence of games, and also for taking the monotonic cover of games. Based on these properties we establish the coincidence of the Mas-Colell, the classical, the semireactive, and the reactive bargaining setswith the core for interesting balanced subclasses of partitioning games, including assignment games, tree-restricted superadditive games, and simple network games. Prepared during the author’s Bolyai János Research Fellowship. Also supported by OTKA grant T46194.     

When is tit-for-tat unbeatable?

We characterize the class of symmetric two-player games in which tit-for-tat cannot be beaten even by very sophisticated opponents in a repeated game. It turns out to be the class of exact potential games. More generally, there is a class of simple imitation rules that includes tit-for-tat but also imitate-the-best and imitate-if-better. Every decision rule in this class is essentially unbeatable in exact potential games. Our results apply to many interesting games including all symmetric 2 $\times $ 2 games, and standard examples of Cournot duopoly, price competition, public goods games, common pool resource games, and minimum effort coordination games.     

Cores and related solution concepts for multi-choice games

A multi-choice game is a generalization of a cooperative game in which each player has several activity levels. Cooperative games form a subclass of the class of multi-choice games.This paper extends some solution concepts for cooperative games to multi-choice games. In particular, the notions of core, dominance core and Weber set are extended. Relations between cores and dominance cores and between cores and Weber sets are extensively studied. A class of flow games is introduced and relations with non-negative games with non-empty cores are investigated.     

Total Reward Stochastic Games and Sensitive Average Reward Strategies

In this paper, total reward stochastic games are surveyed. Total reward games are motivated as a refinement of average reward games. The total reward is defined as the limiting average of the partial sums of the stream of payoffs. It is shown that total reward games with finite state space are strategically equivalent to a class of average reward games with an infinite countable state space. The role of stationary strategies in total reward games is investigated in detail. Further, it is outlined that, for total reward games with average reward value 0 and where additionally both players possess average reward optimal stationary strategies, it holds that the total reward value exists.     

多目标大博弈中弱Pareto-Berge均衡的存在性

研究了具有任意多个局中人的非合作多目标博弈(多目标大博弈).基于一般非合作博弈中的Berge均衡概念,定义多目标大博弈中的弱Pareto-Berge均衡.进一步推广了截口定理,得到新的截口定理,并且利用这个新的截口定理证明多目标大博弈中弱Pareto-Berge均衡的存在性.多目标大博弈中弱Pareto-Nash均衡的存在性结论可作为弱Pareto-Berge均衡存在性的特例给出.     

Equilibria for Pooling Situations

This paper deals with pooling situations, which can be considered as exchange economies with indivisible goods and money, and two related cooperative games which we refer to as pooling games with individual rights and pooling games without individual rights. It is shown that the classes of pooling games without individual rights and transportation games coincide and are contained in the class of pooling games with individual rights. With tools from discrete convexity theory, it is proved that competitive equilibria for pooling situations exist. As a consequence, an alternative proof of the nonemptiness of the core of pooling games is provided.     

A polynomial time algorithm for computing the nucleolus for a class of disjunctive games with a permission structure

Recently, applications of cooperative game theory to economic allocation problems have gained popularity. In many such allocation problems there is some hierarchical ordering of the players. In this paper we consider a class of games with a permission structure describing situations in which players in a cooperative TU-game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. The corresponding restricted game takes account of the limited cooperation possibilities by assigning to every coalition the worth of its largest feasible subset. In this paper we provide a polynomial time algorithm for computing the nucleolus of the restricted games corresponding to a class of games with a permission structure which economic applications include auction games, dual airport games, dual polluted river games and information market games.     

Search and Ambush Games with Capacities

Search games with capacities are bipersonal zero-sum games where a player has to hide a number of objects or an amount of material in a fixed number of containers and his opponent attempts to locate them. In this article, we deal with games on a discrete structureless set and on a discrete set with linear order. In both cases, the capacities under consideration are continuous. Some of the games studied generalize previously studied games.     

集合对策边缘解的公理化方法

本文将单调集合对策边缘解推广到一般集合对策上,利用三个公理,确定了集合对策边缘解的唯—性．在证明唯—性的过程中,引进了单调集合对策将集合对策进行分解．证明过程与Aarts等人的方法完全不一样,在某些地方吸收了Young的有关思想．     

New techniques for cost sharing in combinatorial optimization games

Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrate the power of these techniques, we apply them to traveling salesman and vehicle routing games. Our results generalize and unify several results in the literature. The main underlying idea is that suitable valid inequalities for the associated combinatorial optimization problems can be used to derive improved cost shares.     

Dynamic feedback Stackelberg games with alternating leaders

In all past researches on dynamic Stackelberg games, the leader(s) and the followers are always assumed to be fixed. In practice, the roles of the players in a game may change from time to time. Some player in contract bridge, for example, acts as a leader at some stage but as a follower at the subsequent stage, which motivates the Stackelberg games with unfixed leaders. We aim to analyze the dynamic Stackelberg games with two players under such circumstances and call them dynamic Stackelberg games with alternating leaders. There are two goals in this paper. One goal is to establish models for a new type of games, dynamic Stackelberg games of alternating leaders with two players. The other goal is to extend dynamic programming algorithms to discrete time dynamic Stackelberg games with alternating leaders under feedback information structure.