Representation of finite games as network congestion games

Weighted network congestion games are a natural model for interactions involving finitely many non-identical users of network resources, such as road segments or communication links. However, in spite of their special form, these games are not fundamentally special: every finite game can be represented as a weighted network congestion game. The same is true for the class of (unweighted) network congestion games with player-specific costs, in which the players differ in their cost functions rather than their weights. The intersection of the two classes consists of the unweighted network congestion games. These games are special: a finite game can be represented in this form if and only if it is an exact potential game.     

Decomposition of network communication games

Using network control structures, this paper introduces a general class of network communication games and studies their decomposition into unanimity games. We obtain a relation between the dividends in any network communication game and its underlying transferable utility game, which depends on the structure of the communication network. Moreover, we introduce a new class of network control values which contains both the Myerson value and the position value. The decomposition results are used to explicitly express these values in terms of dividends.     

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.     

On the convexity of communication games

A communication situation consists of a game and a communication graph. By introducing two different types of corresponding communication games, point games and arc games, the Myerson value and the position value of a communication situation were introduced. This paper investigates relations between convexity of the underlying game and the two communication games. In particular, assuming the underlying game to be convex, necessary and sufficient conditions on the communication graph are provided such that the communication games are convex. Moreover, under the same conditions, it is shown that the Myerson value and the posi tion value are in the core of the point game. Some remarks are made on superadditivity and balancedness.     

Inheritance of properties in communication situations

In this paper we consider cooperative games in which the possibilities for cooperation between the players are restricted because communication between the players is restricted. The bilateral communication possibilities are modeled by means of a (communication) graph. We are interested in how the communication restrictions influence the game. In particular, we investigate what conditions on the communication graph guarantee that certain appealing properties of the original game are inherited by the graph-restricted game, the game that arises once the communication restrictions are taken into account. We study inheritance of the following properties: average convexity, inclusion of the Shapley value in the core, inclusion of the Shapley values of a game and all its subgames in the corresponding cores, existence of a population monotonic allocation scheme, and the property that the extended Shapley value is a population monotonic allocation scheme. Received May 1998/Revised version January 2000     

演化博弈与自组织合作

主要研究复杂网络上的演化博弈.首先研究具有社团结构的无标度网络上的演化囚徒困境博弈及Newman-Watts小世界网络中异质性对合作演化的影响.然后考察了在不同合作者和作弊者初始分布配置情况下,不同的初始比例条件对合作水平的影响,且在社会网络上研究了雪堆博弈中的合作演化.进一步地,讨论了网络拓扑和博弈动力学的共同演化问题和网络上演化囚徒困境中的强化学习问题.最后给出了复杂网络上演化博弈论的未来发展方向与应用前景.     

Unequal connections

Empirical work suggests that social and economic networks are characterized by an unequal distribution of connections across individuals. This paper explores the circumstances under which networks will or will not exhibit inequality. Two specific models of network formation are explored. The first is a playing the field game in which the aggregate payoffs of an individual depend only on the number of his links and the aggregate number of links of the rest of the population. The second is a local spillovers game in which the aggregate payoffs of an individual depend on the distribution of links of all players and the identity of neighbors. For both class of games we develop results on existence and characterize equilibrium networks under different combinations of externalities/spillovers. We also examine conditions under which having more connections implies a higher payoff.     

On the core of cost-revenue games: Minimum cost spanning tree games with revenues

In this paper, we analyze cost sharing problems arising from a general service by explicitly taking into account the generated revenues. To this cost-revenue sharing problem, we associate a cooperative game with transferable utility, called cost-revenue game. By considering cooperation among the agents using the general service, the value of a coalition is defined as the maximum net revenues that the coalition may obtain by means of cooperation. As a result, a coalition may profit from not allowing all its members to get the service that generates the revenues. We focus on the study of the core of cost-revenue games. Under the assumption that cooperation among the members of the grand coalition grants the use of the service under consideration to all its members, it is shown that a cost-revenue game has a nonempty core for any vector of revenues if, and only if, the dual game of the cost game has a large core. Using this result, we investigate minimum cost spanning tree games with revenues. We show that if every connection cost can take only two values (low or high cost), then, the corresponding minimum cost spanning tree game with revenues has a nonempty core. Furthermore, we provide an example of a minimum cost spanning tree game with revenues with an empty core where every connection cost can take only one of three values (low, medium, or high cost).     

Shortest path games

We study cooperative games that arise from the problem of finding shortest paths from a specified source to all other nodes in a network. Such networks model, among other things, efficient development of a commuter rail system for a growing metropolitan area. We motivate and define these games and provide reasonable conditions for the corresponding rail application. We show that the core of a shortest path game is nonempty and satisfies the given conditions, but that the Shapley value for these games may lie outside the core. However, we show that the shortest path game is convex for the special case of tree networks, and we provide a simple, polynomial time formula for the Shapley value in this case. In addition, we extend our tree results to the case where users of the network travel to nodes other than the source. Finally, we provide a necessary and sufficient condition for shortest paths to remain optimal in dynamic shortest path games, where nodes are added to the network sequentially over time.     

Transshipment games with identical newsvendors and cooperation costs

In a transshipment game, supply chain agents cooperate to transship surplus products. Although the game has been well studied in the OR literature, the fundamental question whether the agents can afford cooperation costs to set up and maintain the game in the first place has not been addressed thus far. This paper addresses this question for the cooperative transshipment games with identical agents having normally distributed independent demands. We provide characterization of equal allocations which are in the core of symmetric games, and prove that not all transshipment games are convex. In particular, we prove that though individual allocations grow with the coalition size, the growth diminishes according to two rules of diminishing individual allocations. These results are the basis for studying the games with cooperation costs. We model the cooperation costs by the cooperation network topology and the cooperation cost per network link. We consider two network topologies, the clique and the hub, and prove bounds for the cost per link that render coalitions stable. These bounds always limit coalition size for cliques. However, the opposite is shown for hubs, namely newsvendors can afford cooperation costs only if their coalition is sufficiently large.     

超图结构上合作博弈的赋权Position值

在合作博弈的一般模型中总是假设所有联盟都能形成。不过,在实际中由于受到一些因素的制约,有些联盟是不能形成的。基于此,Myerson提出了具有图通讯结构的合作博弈。Myerson值和Position值是超图博弈上的两个重要分配规则。2005年,Slikker给出了在图博弈上Position值的公理化刻画。但超图博弈上Position值的公理化刻画一直悬而未决。本文通过引入 “赋权平衡超边贡献公理”,并结合经典的“分支有效性”,提出了超图博弈上赋权Position值的公理化刻画。作为推论,解决了超图博弈上Position值的公理化刻画问题。     

Cooperative games of choosing partners and forming coalitions in the marketplace

Two games of interacting between a coalition of players in a marketplace and the residual players acting there are discussed, along with two approaches to fair imputation of gains of coalitions in cooperative games that are based on the concepts of the Shapley vector and core of a cooperative game. In the first game, which is an antagonistic one, the residual players try to minimize the coalition's gain, whereas in the second game, which is a noncooperative one, they try to maximize their own gain as a coalition. A meaningful interpretation of possible relations between gains and Nash equilibrium strategies in both games considered as those played between a coalition of firms and its surrounding in a particular marketplace in the framework of two classes of n-person games is presented. A particular class of games of choosing partners and forming coalitions in which models of firms operating in the marketplace are those with linear constraints and utility functions being sums of linear and bilinear functions of two corresponding vector arguments is analyzed, and a set of maximin problems on polyhedral sets of connected strategies which the problem of choosing a coalition for a particular firm is reducible to are formulated based on the firm models of the considered kind.     

DEA production games

In this paper, linear production games are extended so that instead of assuming a linear production technology with fixed technological coefficients, the more general, non-parametric, DEA production technology is considered. Different organizations are assumed to possess their own technology and the cooperative game arises from the possibility of pooling their available inputs, collectively processing them and sharing the revenues. Two possibilities are considered: using a joint production technology that results from merging their respective technologies or each cooperating organization keeping its own technology. This gives rise to two different DEA production games, both of which are totally balanced and have a non-empty core. A simple way of computing a stable solution, using the optimal dual solution for the grand coalition, is presented. The full cooperation scenario clearly produces more benefits for the organizations involved although the implied technology sharing is not always possible. Examples of applications of the proposed approach are given.     

Inheritance of properties in NTU communication situations

In this paper we consider communication situations in which utility is nontransferable. We compare this model with the more familiar model of transferable utility communication situations in terms of the corresponding graph-restricted games. We extend transferable utility results on the inheritance of properties of the underlying game to the graph-restricted game to our context of nontransferable utility.Thanks are due to Peter Borm for some helpful comments.     

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.     

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.     

An Inexact Spingarn’s Partial Inverse Method with Applications to Operator Splitting and Composite Optimization

In this paper, a pursuit-evasion game involving two non-holonomic agents is examined using the theory of differential games. It is assumed that the two players move on the Euclidean plane with fixed but different speeds and they each have a lower bound on their achievable turn radii. Both players steer at each instant by choosing their turn radii value and directions of turn. By formulating the game as a game of kind, we characterize the regions of initial conditions that lead to capture as well as the regions that lead to evasion, when both the players play optimally. The game is then formulated as a game of degree to obtain time-optimal paths for the pursuer and evader inside a capture region. Besides, all possible scenarios are considered for both players that differ in speed ratios and maneuverability constraints. Solutions are provided for those cases using appropriate simulation parameters, which aid in understanding the characteristics of the game of two cars under a wide range of constraints.     

Groupstrategyproofness of the egalitarian mechanism for constrained rationing problems

Motivated by applications in many economic environments, Bochet et al. (2010) generalize the classic rationing model (Sprumont 1991) as follows: there is a moneyless market, in which a non-storable, homogeneous commodity is reallocated between agents with single-peaked preferences. Agents are either suppliers or demanders. Transfers between a supplier and a demander are feasible only if they are linked, and the links form an arbitrary bipartite graph. Information about individual preferences is private, and so is information about feasible links: an agent may unilaterally close one of her links if it is in her interest to do so. For this problem they propose the egalitarian transfer solution, which equalizes the net transfers of rationed agents as much as permitted by the bilateral constraints. Furthermore, they show that the egalitarian mechanism elicits a truthful report of both preferences and links. In the variant where demanders are not strategic but demands need to be exactly met Bochet et al. (2013), they propose a similar mechanism for which truthfully reporting the peaks is a dominant strategy, but truthful reporting of links is not.The key contribution of the paper is a comprehensive study of the egalitarian mechanism with respect to manipulation by a coalition of agents. Our main result is that the egalitarian mechanism is group strategyproof : no coalition of agents can (weakly) benefit from jointly misreporting their peaks. Furthermore, we show that the egalitarian mechanism cannot be manipulated – by misreporting links or by misreporting peaks – by any coalition of suppliers (or any coalition of demanders) in the model where both the suppliers and demanders are agents. Our proofs shed light on the structure of the two models and simplify some of the earlier proofs of strategyproofness. An implication of our results is that the well known algorithm of Megiddo (1977) to compute a lexicographically optimal flow in a network is group strategyproof with respect to the source capacities and sink capacities.     

Splitting graphs when calculating Myerson value for pure overhead games

A communication situation consists of a coalitional game and a graph, the nodes of the graph corresponding to the players of the game. To calculate the Myerson value for such situations, we obtain results which extend those well known for trees and cycle-complete graphs. On the other hand, in order to reduce the associated calculus for communication situations with a pure overhead game, the possibility of splitting the graph in several subgraphs is analyzed. For each fixed decomposition of the graph, a subspace of games compatible with this decomposition is given.     

Effect of local information within network layers on the evolution of cooperation in duplex public goods games

Traditional works of public goods game (PGG) are often studied in simplex networks where agents play games through the same type of social interactions. In order to promote cooperation against the defection in PGGs in simplex network environment, many mechanisms have been proposed from different perspectives, such as the volunteering mechanisms, and the punishment and reward approaches. However, due to diverse types of interactions between agents in reality, the study of PGG should also consider the characteristic of multiplexity of networks. Hence, we firstly model the public goods game in the duplex network (for simplification of analysis, the duplex network is considered), in which agents have two types of social interactions, and thus the network is modeled as two network layers. This type of PGG is naturally named as duplex public goods game (D-PGG), in which agents can select one of the network layers to allocate their limited resources. Then for the new game environment (D-PGG), we propose a novel perspective to promote cooperation: degrading the information integrity, i.e., agents get information just from one network layer (local information) rather than from the whole duplex network (global information) in the evolution process. Finally, through theoretical analyses and simulations, we find that if agents imitate based on the local information of the payoff in the evolution, cooperation can be generally promoted; and the extent of promotion depends on both the network structure and the similarity of the network layers.