Zero-sum constrained stochastic games with independent state processes

We consider a zero-sum stochastic game with side constraints for both players with a special structure. There are two independent controlled Markov chains, one for each player. The transition probabilities of the chain associated with a player as well as the related side constraints depend only on the actions of the corresponding player; the side constraints also depend on the player’s controlled chain. The global cost that player 1 wishes to minimize and that player 2 wishes to maximize, depend however on the actions and Markov chains of both players. We obtain a linear programming formulations that allows to compute the value and saddle point policies for this problem. We illustrate the theoretical results through a zero-sum stochastic game in wireless networks in which each player has power constraints     

Unilateral vs. bilateral link-formation: A transition without decay

We provide a model that bridges the gap between the simplest variation of two benchmark models of strategic network formation: Bala and Goyal’s two-way flow model without decay, where links can be unilaterally formed, and a variation of Jackson and Wolinsky’s model based on bilateral formation of links assuming no decay. In the model introduced and studied here a link can be created unilaterally. When it is only supported by one of the two players the flow through the link suffers some degree of decay, but when it is supported by both the flow runs without friction. When the decay in links supported by only one player is maximal (i.e. there is no flow) we have a simple variation of Jackson and Wolinsky’s connections model assuming no decay, while when flow in those links is perfect we have Bala and Goyal’s two-way flow model without decay. We study Nash, strict Nash and pairwise Nash stability for the intermediate models. Efficiency and dynamics are also examined.     

Mean-field games with a major player

We introduce and study mathematically a new class of mean-field-game systems of equations. This class of equations allows us to model situations involving one major player (or agent) and a “large” group of “small” players.     

Stochastic Discrete-Time Nash Games with Constrained State Estimators

In this paper, we consider stochastic linear-quadratic discrete-time Nash games in which two players have access only to noise-corrupted output measurements. We assume that each player is constrained to use a linear Kalman filter-like state estimator to implement his optimal strategies. Two information structures available to the players in their state estimators are investigated. The first has access to one-step delayed output and a one-step delayed control input of the player. The second has access to the current output and a one-step delayed control input of the player. In both cases, statistics of the process and statistics of the measurements of each player are known to both players. A simple example of a two-zone energy trading system is considered to illustrate the developed Nash strategies. In this example, the Nash strategies are calculated for the two cases of unlimited and limited transmission capacity constraints.     

Network formation when players seek confirmation of information

We study network formation in a situation where the network allows players to obtain information (signals) about other players. This information is important for making a payoff relevant decision. However, not all information is reliable and so players may have an incentive to check it. By obtaining multiple messages about the same player through the network, a player learns whether his information is reliable for making the payoff relevant decision. We study the existence and architecture of strict Nash networks. We find that players who are involved in at least three links sponsor all links they are involved in. These players are similar to the central players in center sponsored stars. We show that strict Nash networks can be over-connected as well as under-connected as compared to efficient networks. Finally, we extend the basic model to study heterogeneous populations. In the first scenario, we allow for the co-existence of players who only value checked information and players who also value information with unknown reliability. In the second scenario, players who do not care about checking their information co-exist with players who do. Our results are robust to both types of heterogeneity, with one exception: the presence of a single player who cares only about checked information is enough to ensure that center sponsored stars are no longer stable.     

“Procedural” values for cooperative games

This paper introduces a new notion of a “procedural” value for cooperative TU games. A procedural value is determined by an underlying procedure of sharing marginal contributions to coalitions formed by players joining in random order. We consider procedures under which players can only share their marginal contributions with their predecessors in the ordering, and study the set of all resulting values. The most prominent procedural value is, of course, the Shapley value obtaining under the simplest procedure of every player just retaining his entire marginal contribution. But different sharing rules lead to other interesting values, including the “egalitarian solution” and the Nowak and Radzik “solidarity value”. All procedural values are efficient, symmetric and linear. Moreover, it is shown that these properties together with two very natural monotonicity postulates characterize the class of procedural values. Some possible modifications and generalizations are also discussed. In particular, it is shown that dropping one of monotonicity axioms is equivalent to allowing for sharing marginal contributions with both predecessors and successors in the ordering.     

Layers of noncooperative games

We model and analyze classes of antagonistic stochastic games of two players. The actions of the players are formalized by marked point processes recording the cumulative damage to the players at any moment of time. The processes evolve until one of the processes crosses its fixed preassigned threshold of tolerance. Once the threshold is reached or exceeded at some point of the time (exit time), the associated player is ruined. Both stochastic processes are being “observed” by a third party point stochastic process, over which the information regarding the status of both players is obtained. We succeed in these goals by arriving at closed form joint functionals of the named elements and processes. Furthermore, we also look into the game more closely by introducing an intermediate threshold (see a layer), which a losing player is to cross prior to his ruin, in order to analyze the game more scrupulously and see what makes the player lose the game.     

Random Walk Analysis in Antagonistic Stochastic Games

Abstract

This article deals with two “antagonistic random processes” that are intended to model classes of completely noncooperative games occurring in economics, engineering, natural sciences, and warfare. In terms of game theory, these processes can represent two players with opposite interests. The actions of the players are manifested by a series of strikes of random magnitudes imposed onto the opposite side and rendered at random times. Each of the assaults is aimed to inflict damage to vital areas. In contrast with some strictly antagonistic games where a game ends with one single successful hit, in the current setting, each side (player) can endure multiple strikes before perishing. Each player has a fixed cumulative threshold of tolerance which represents how much damage he can endure before succumbing. Each player will try to defeat the adversary at his earliest opportunity, and the time when one of them collapses is referred to as the “ruin time”. We predict the ruin time of each player, and the cumulative status of all related components for each player at ruin time. The actions of each player are formalized by a marked point process representing (an economic) status of each opponent at any given moment of time. Their marks are assumed to be weakly monotone, which means that each opposite side accumulates damages, but does not have the ability to recover. We render a time-sensitive analysis of a bivariate continuous time parameter process representing the status of each player at any given time and at the ruin time and obtain explicit formulas for related functionals.     

Limiting distributions of the number of pure strategy Nash equilibria in n-person games

We study the number of pure strategy Nash equilibria in a “random” n-person non-cooperative game in which all players have a countable number of strategies. We consider both the cases where all players have strictly and weakly ordinal preferences over their outcomes. For both cases, we show that the distribution of the number of pure strategy Nash equilibria approaches the Poisson distribution with mean 1 as the numbers of strategies of two or more players go to infinity. We also find, for each case, the distribution of the number of pure strategy Nash equilibria when the number of strategies of one player goes to infinity, while those of the other players remain finite.     

Power Measures and Solutions for Games Under Precedence Constraints

Games under precedence constraints model situations, where players in a cooperative transferable utility game belong to some hierarchical structure, which is represented by an acyclic digraph (partial order). In this paper, we introduce the class of precedence power solutions for games under precedence constraints. These solutions are obtained by allocating the dividends in the game proportional to some power measure for acyclic digraphs. We show that all these solutions satisfy the desirable axiom of irrelevant player independence, which establishes that the payoffs assigned to relevant players are not affected by the presence of irrelevant players. We axiomatize these precedence power solutions using irrelevant player independence and an axiom that uses a digraph power measure. We give special attention to the hierarchical solution, which applies the hierarchical measure. We argue how this solution is related to the known precedence Shapley value, which does not satisfy irrelevant player independence, and thus is not a precedence power solution. We also axiomatize the hierarchical measure as a digraph power measure.     

Robust Multiple Objective Game Theory

In this paper, we propose a distribution-free model instead of considering a particular distribution for multiple objective games with incomplete information. We assume that each player does not know the exact value of the uncertain payoff parameters, but only knows that they belong to an uncertainty set. In our model, the players use a robust optimization approach for each of their objective to contend with payoff uncertainty. To formulate such a game, named “robust multiple objective games” here, we introduce three kinds of robust equilibrium under different preference structures. Then, by using a scalarization method and an existing result on the solutions for the generalized quasi-vector equilibrium problems, we obtain the existence of these robust equilibria. Finally, we give an example to illustrate our model and the existence theorems. Our results are new and fill the gap in the game theory literature.     

Emergence and nonemergence of alternating offers in bilateral bargaining

We study in what circumstance players alternate offers in bilateral bargaining. To examine this question, we suppose that players choose whether to take the initiative in each period. The player who tries to take the initiative is able to make an offer only when the other player does not. The probability that a player tries to take the initiative is referred to as the frequency of initiative taking. We assume that this is conditioned on mutually observable states and is, once chosen, unchangeable. When players make their frequency of initiative taking dependent on the identity of the latest proposer, the players alternate their offers (possibly with some stochastic delay). In contrast, when players always use the same frequency of initiative taking, or when players only distinguish odd-numbered from even-numbered periods for the frequency of initiative taking, both players constantly try to take the initiative. Consequently, an impasse arises.     

A simple expression for the nucleolus in a special case

We present a simple algorithm for calculating the nucleolus of a game whenever (a) the characteristic function is non-positive, ie. a “cost” function, and (b) the players can be ordered by “size” in such a way that the cost of any coalition is equal to the cost of the largest player in that coalition. The cumulative nucleolus is approximately equal to the convex envelope of this cost function. A numerical and geometric illustration is given for a game based upon Birmingham airport runway costs, where there are over 13,000 players (aircraft movements) of 11 distinct (aircraft) types.     

A globalized Newton method for the computation of normalized Nash equilibria

The generalized Nash equilibrium is a Nash game, where not only the players’ cost functions, but also the constraints of a player depend on the rival players decisions. We present a globally convergent algorithm that is suited for the computation of a normalized Nash equilibrium in the generalized Nash game with jointly convex constraints. The main tool is the regularized Nikaido–Isoda function as a basis for a locally convergent nonsmooth Newton method and, in another way, for the definition of a merit function for globalization. We conclude with some numerical results.     

A unifying model of strategic network formation

We provide a model that merges two basic models of strategic network formation and incorporates them as extreme cases: Jackson and Wolinsky’s connections model based on bilateral formation of links, and Bala and Goyal’s two-way flow model, where links can be unilaterally formed. In our model a link can be created unilaterally, but when it is only supported by one of the two players the flow through it suffers some friction or decay, but more than when it is supported by both players. When the friction in singly-supported links is maximal (i.e. there is no flow) we have Jackson and Wolinsky’s connections model, while when flow in singly-supported links is as good as in doubly-supported links we have Bala and Goyal’s two-way flow model. In this setting, a joint generalization of the results relative to efficiency and stability in both seminal papers is achieved, and the robustness in both models is tested with positive results.     

On the minimal representation of homogeneous games

It is known that the lattice-minimal representation (by natural numbers) of a weighted majority game may be not unique and may lack of equal treatment (Isbell 1959). The same is true for the total-weight minimal representation. Both concepts coincide on the class of homogeneous games. The main theorem of this article is that for homogeneous games there is a unique minimal representation. This result is given by means of a construction that depends on the natural order on the set of player types. This order coincides with one induced by the “desirability relation”. In order to compute the minimal representation inductively, while proceeding from smaller players to the greater one, we are led to distinguish two different kinds of players: some players are “replacable” by smaller ones, some not.     

边赋权图对策Myerson值的和分解

2003年,Gómez等在考虑社会网络中心性度量时,引入了对称对策上Myerson值的和分解概念,本文将这一概念推广到边赋权图对策上,给出了相应于边赋权图对策的组内Myerson值和组间Myerson值。其中边的权表示这条边的两个端点之间的直接通讯容量,组内Myerson值衡量了每个参与者来自它所在联盟的收益,而组间Myerson值评估了参与者作为其他参与者中介所获取的收益。本文侧重分析了边赋权图对策的组内Myerson值和组间Myerson值的权稳定性和广义稳定性, 并给出了这两类值的刻画。     

Algorithms for multiplayer multicommodity flow problems

We investigate the multiplayer multicommodity flow problem: several players have different networks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value. We show that the social optimum can be computed by linear programming, and we propose algorithms based on column generation and Lagrangian relaxation. In contrast, we prove that it is hard to decide if an equilibrium solution exists, although some natural conditions guarantee its existence.     

An experimental study of constant-sum centipede games

In this paper, we report the results of a series of experiments on a version of the centipede game in which the total payoff to the two players is constant. Standard backward induction arguments lead to a unique Nash equilibrium outcome prediction, which is the same as the prediction made by theories of “fair” or “focal” outcomes. We find that subjects frequently fail to select the unique Nash outcome prediction. While this behavior was also observed in McKelvey and Palfrey (1992) in the “growing pie” version of the game they studied, the Nash outcome was not “fair”, and there was the possibility of Pareto improvement by deviating from Nash play. Their findings could therefore be explained by small amounts of altruistic behavior. There are no Pareto improvements available in the constant-sum games we examine. Hence, explanations based on altruism cannot account for these new data. We examine and compare two classes of models to explain these data. The first class consists of non-equilibrium modifications of the standard “Always Take” model. The other class we investigate, the Quantal Response Equilibrium model, describes an equilibrium in which subjects make mistakes in implementing their best replies and assume other players do so as well. One specification of this model fits the experimental data best, among the models we test, and is able to account for all the main features we observe in the data.     

Optimal strategies for node selection games on oriented graphs: Skew matrices and symmetric games

In the node selection game Γ_D each of the two players simultaneously selects a node from the oriented graph D. If there is an arc between the selected nodes, then there is a payoff from the “dominated” player to the “dominating” player. We investigate the set of optimal strategies for the players in the node selection game Γ_D. We point out that a classical theorem from game theory relates the dimension of the polytope of optimal strategies for Γ_D to the nullity of certain skew submatrix of the payoff matrix for Γ_D. We show that if D is bipartite (with at least two nodes in each partite set), then an optimal strategy for the node selection game Γ_D is never unique. Our work also implies that if D is a tournament, then there is a unique optimal strategy for each player, a result obtained by Fisher and Ryan [Optimal strategies for a generalized “scissors, paper, and stone” game, Amer. Math. Monthly 99 (1992) 935–942] and independently by Laffond, Laslier, and Le Breton [The bipartisan set of a tournament game, Games Econom. Behav. 5 (1993) 182–201].