Convex multi-choice games: Characterizations and monotonic allocation schemes

This paper focuses on new characterizations of convex multi-choice games using the notions of exactness and superadditivity. Furthermore, level-increase monotonic allocation schemes (limas) on the class of convex multi-choice games are introduced and studied. It turns out that each element of the Weber set of such a game is extendable to a limas, and the (total) Shapley value for multi-choice games generates a limas for each convex multi-choice game.     

Convexity properties for interior operator games

Interior operator games arose by abstracting some properties of several types of cooperative games (for instance: peer group games, big boss games, clan games and information market games). This reason allow us to focus on different problems in the same way. We introduced these games in Bilbao et al. (Ann. Oper. Res. 137:141–160, 2005) by a set system with structure of antimatroid, that determines the feasible coalitions, and a non-negative vector, that represents a payoff distribution over the players. These games, in general, are not convex games. The main goal of this paper is to study under which conditions an interior operator game verifies other convexity properties: 1-convexity, k-convexity (k≥2 ) or semiconvexity. But, we will study these properties over structures more general than antimatroids: the interior operator structures. In every case, several characterizations in terms of the gap function and the initial vector are obtained. We also find the family of interior operator structures (particularly antimatroids) where every interior operator game satisfies one of these properties.     

Sufficient conditions for Nash equilibria inN-person games over reflexive Banach spaces

Sufficient conditions are obtained for the existence of Nash equilibrium points inN-person games when the strategy sets are closed, convex subsets of reflexive Banach spaces. These conditions require that each player's cost functional is convex in that player's strategy, weakly continuous in the strategies of the other players, weakly lower semicontinuous in all strategies, and furthermore satisfies a coercivity condition if any of the strategy sets is unbounded. The result is applied to a class of linear-quadratic differential games with no information, to prove that equilibrium points exist when the duration of these games is sufficiently small.This work was supported by a Commonwealth of Australia, Postgraduate Research Award.     

一类混合单调算子新的不动点定理及其应用

引入了广义Φ凹（-φ）凸算子这一概念,在非紧非连续条件下,得到了混合单调算子的几个新的不动点存在唯一性定理.最后给出了一个应用.     

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.     

Variational convergence of bivariate functions: lopsided convergence

We explore convergence notions for bivariate functions that yield convergence and stability results for their maxinf (or minsup) points. This lays the foundations for the study of the stability of solutions to variational inequalities, the solutions of inclusions, of Nash equilibrium points of non-cooperative games and Walras economic equilibrium points, of fixed points, of solutions to inclusions, the primal and dual solutions of convex optimization problems and of zero-sum games. These applications will be dealt with in a couple of accompanying papers.     

博弈的统计演化分析

首先定义了具有确定分布的随机环境中的基于适应度的平均选择算子,然后证明了主体战略集上的任一概率密度在平均选择算子的迭代过程中收敛于平均适应度函数的最大集上的某一分布,然后就多主体的博弈问题定义了平均选择算子,并以此为基础证明了平均选择算子的不动点就是博弈的纳什均衡.     

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.     

<Emphasis Type="Italic">p</Emphasis>-additive games: a class of totally balanced games arising from inventory situations with temporary discounts

We introduce a new class of totally balanced cooperative TU games, namely p-additive games. It is inspired by the class of inventory games that arises from inventory situations with temporary discounts (Toledo Ph.D. thesis, Universidad Miguel Hernández de Elche, 2002) and contains the class of inventory cost games (Meca et al. Math. Methods Oper. Res. 57:481–493, 2003). It is shown that every p-additive game and its corresponding subgames have a nonempty core. We also focus on studying the character of concave or convex and monotone p-additive games. In addition, the modified SOC-rule is proposed as a solution for p-additive games. This solution is suitable for p-additive games, since it is a core-allocation which can be reached through a population monotonic allocation scheme. Moreover, two characterizations of the modified SOC-rule are provided. This work was partially supported by the Spanish Ministry of Education and Science and Generalitat Valenciana (grants MTM2005-09184-C02-02, ACOMP06/040, CSD2006-00032). Authors acknowledge valuable comments made by the Editor and the referee.     

On the existence of almost-pure-strategy Nash equilibrium in <Emphasis Type="Italic">n</Emphasis>-person finite games

This paper gives wide characterization of n-person non-coalitional games with finite players’ strategy spaces and payoff functions having some concavity or convexity properties. The characterization is done in terms of the existence of two-point-strategy Nash equilibria, that is equilibria consisting only of mixed strategies with supports being one or two-point sets of players’ pure strategy spaces. The structure of such simple equilibria is discussed in different cases. The results obtained in the paper can be seen as a discrete counterpart of Glicksberg’s theorem and other known results about the existence of pure (or “almost pure”) Nash equilibria in continuous concave (convex) games with compact convex spaces of players’ pure strategies.     

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.     

Congestion network problems and related games

This paper analyzes network problems with congestion effects from a cooperative game theoretic perspective. It is shown that for network problems with convex congestion costs, the corresponding games have a non-empty core. If congestion costs are concave, then the corresponding game has not necessarily core elements, but it is derived that, contrary to the convex congestion situation, there always exist optimal tree networks. Extensions of these results to a class of relaxed network problems and associated games are derived.     

Efficient Winning Strategies in Random‐Turn Maker–Breaker Games

We consider random‐turn positional games, introduced by Peres, Schramm, Sheffield, and Wilson in 2007. A p‐random‐turn positional game is a two‐player game, played the same as an ordinary positional game, except that instead of alternating turns, a coin is being tossed before each turn to decide the identity of the next player to move (the probability of Player I to move is p ). We analyze the random‐turn version of several classical Maker–Breaker games such as the game Box (introduced by Chvátal and Erd?s in 1987), the Hamilton cycle game and the k‐vertex‐connectivity game (both played on the edge set of ). For each of these games we provide each of the players with a (randomized) efficient strategy that typically ensures his win in the asymptotic order of the minimum value of p for which he typically wins the game, assuming optimal strategies of both players.     

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     

Separable and low-rank continuous games

In this paper, we study nonzero-sum separable games, which are continuous games whose payoffs take a sum-of-products form. Included in this subclass are all finite games and polynomial games. We investigate the structure of equilibria in separable games. We show that these games admit finitely supported Nash equilibria. Motivated by the bounds on the supports of mixed equilibria in two-player finite games in terms of the ranks of the payoff matrices, we define the notion of the rank of an n-player continuous game and use this to provide bounds on the cardinality of the support of equilibrium strategies. We present a general characterization theorem that states that a continuous game has finite rank if and only if it is separable. Using our rank results, we present an efficient algorithm for computing approximate equilibria of two-player separable games with fixed strategy spaces in time polynomial in the rank of the game. This research was funded in part by National Science Foundation grants DMI-0545910 and ECCS-0621922 and AFOSR MURI subaward 2003-07688-1.     

Linear values for interior operator games

Interior operator games were introduced by Bilbao et al. (2005) as additive games restricted by antimatroids. In that paper several interesting cooperative games were shown as examples of interior operator games. The antimatroid is a known combinatorial structure which represents, in the game theory context, a dependence system among the players. The aim of this paper is to study a family of values which are linear functions and satisfy reasonable conditions for interior operator games. Two classes of these values are considered assuming particular properties.     

On the existence of good stationary strategies for nonleavable stochastic games

This paper discusses the problem regarding the existence of optimal or nearly optimal stationary strategies for a player engaged in a nonleavable stochastic game. It is known that, for these games, player I need not have an -optimal stationary strategy even when the state space of the game is finite. On the contrary, we show that uniformly -optimal stationary strategies are available to player II for nonleavable stochastic games with finite state space. Our methods will also yield sufficient conditions for the existence of optimal and -optimal stationary strategies for player II for games with countably infinite state space. With the purpose of introducing and explaining the main results of the paper, special consideration is given to a particular class of nonleavable games whose utility is equal to the indicator of a subset of the state space of the game.     

Effort Games and the Price of Myopia

We consider Effort Games, a game‐theoretic model of cooperation in open environments, which is a variant of the principal‐agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, called the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project. We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the Price of Myopia (PoM) as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort. We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a dominant strategy equilibrium or using iterated elimination of dominated strategies. We show these problems are generally #P‐hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series‐Parallel Graphs (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Cone Concavity and Multiple-Payoff Constrained n-Person Games

This paper investigates special cases of abstract economies, i.e., n-person games with multiple payoff functions. Dominances with certain convex cones and interactive strategies are introduced in such game settings. Gradients of payoff functions are involved to establish certain Lagrange or Kuhn–Tucker conditions which may lead to some algorithms to actually compute an equilibrium. Sufficient and necessary conditions for such multiple payoff constrained n-person games are obtained.     

一类凹与凸算子的推广

运用锥的性质以及单调迭代技巧给出了一类广义凹算子与凸算子正不动点的存在唯一性,并讨论了算子特征值方程的性质.作为应用,利用所获结果研究了一类积分方程正解的存在唯一性.