Two Game Models for Cooperation with Implicit Noncooperation

We propose two flexible game models to represent and analyze cases that cannot be modeled by current game models. One is called sharing creditability game (SCG) and the other is called bottomline game (BLG). The new models transform cooperative games into new games that incorporate auxiliary information (noncooperative in nature) usually neglected in previous theories. The new games will be solved only by traditional noncooperative game theory. When the new solutions are applied to the original games, the solutions can reflect the auxiliary information in addition to the original objectives of the decision makers or players. Generally, the new solutions are different from the cooperative and the noncooperative solutions of the original games. Existing transferable utility (TU) games and noncooperative games will coincide with special cases of the two new game models. Using SCG and BLG, the prisoner’s dilemma can be reformulated and a richer set of decisions can be considered for the players. The two new game models have potential applications in military and socioeconomic situations.This research was partly funded by the College Engineering, Ohio State University.     

最短路博弈群体单调分配方案构造

群体单调分配方案(Population Monotonic Allocation Scheme, 后简称PMAS)是合作博弈的一类分配机制。在合作博弈中, PMAS为每一个子博弈提供一个满足群体单调性的核中的分配方案, 从而保证大联盟的动态稳定性。本文主要贡献为利用线性规划与对偶理论构造与求解一类基于最短路问题的合作博弈(最短路博弈)的PMAS。我们首先借助对偶理论, 利用组合方法为最短路博弈构造了一个基于平均分摊思想的PMAS。然后借鉴计算核仁的Maschler方案, 将PMAS的存在性问题转化为一个指数规模的线性规划的求解问题, 并通过巧妙的求解得到了与之前组合方法相同的最短路博弈的PMAS。     

最短路博弈群体单调分配方案构造

群体单调分配方案(Population Monotonic Allocation Scheme, 后简称PMAS)是合作博弈的一类分配机制。在合作博弈中, PMAS为每一个子博弈提供一个满足群体单调性的核中的分配方案, 从而保证大联盟的动态稳定性。本文主要贡献为利用线性规划与对偶理论构造与求解一类基于最短路问题的合作博弈(最短路博弈)的PMAS。我们首先借助对偶理论, 利用组合方法为最短路博弈构造了一个基于平均分摊思想的PMAS。然后借鉴计算核仁的Maschler方案, 将PMAS的存在性问题转化为一个指数规模的线性规划的求解问题, 并通过巧妙的求解得到了与之前组合方法相同的最短路博弈的PMAS。     

Two noncooperative games between a coalition and its surrounding in a class of n-person games with constant sum

A cooperative game engendered by a noncooperative n-person game (the master game) in which any subset of n players may form a coalition playing an antagonistic game against the residual players (the surrounding) that has a (Nash equilibrium) solution, is considered, along with another noncooperative game in which both a coalition and its surrounding try to maximize their gains that also possesses a Nash equilibrium solution. It is shown that if the master game is the one with constant sum, the sets of Nash equilibrium strategies in both above-mentioned noncooperative games (in which a coalition plays with (against) its surrounding) coincide.     

The Compromise Value for Cooperative Games with Random Payoffs

This paper introduces and studies the compromise value for cooperative games with random payoffs, that is, for cooperative games where the payoff to a coalition of players is a random variable. This value is a compromise between utopia payoffs and minimal rights and its definition is based on the compromise value for NTU games and the τ-value for TU games. It is shown that the nonempty core of a cooperative game with random payoffs is bounded by the utopia payoffs and the minimal rights. Consequently, for such games the compromise value exists. Further, we show that the compromise value of a cooperative game with random payoffs coincides with the τ-value of a related TU game if the players have a certain type of preferences. Finally, the compromise value and the marginal value, which is defined as the average of the marginal vectors, coincide on the class of two-person games. This results in a characterization of the compromise value for two-person games.I thank Peter Borm, Ruud Hendrickx and two anonymous referees for their valuable comments.     

On shortest path games

A class of cooperative TU-games arising from shortest path problems is introduced and analyzed. Some conditions under which a shortest path game is balanced are obtained. Also an axiomatic characterization of the Shapley value for this class of games is provided.     

Dynamic realization games in newsvendor inventory centralization

Consider a set N of n (> 1) stores with single-item and single-period nondeterministic demands like in a classic newsvendor setting with holding and penalty costs only. Assume a risk-pooling single-warehouse centralized inventory ordering option. Allocation of costs in the centralized inventory ordering corresponds to modelling it as a cooperative cost game whose players are the stores. It has been shown that when holding and penalty costs are identical for all subsets of stores, the game based on optimal expected costs has a non empty core (Hartman et al. 2000, Games Econ Behav 31:26–49; Muller et al. 2002, Games Econ Behav 38:118–126). In this paper we examine a related inventory centralization game based on demand realizations that has, in general, an empty core even with identical penalty and holding costs (Hartman and Dror 2005, IIE Trans Scheduling Logistics 37:93–107). We propose a repeated cost allocation scheme for dynamic realization games based on allocation processes introduced by Lehrer (2002a, Int J Game Theor 31:341–351). We prove that the cost subsequences of the dynamic realization game process, based on Lehrer’s rules, converge almost surely to either a least square value or the core of the expected game. We extend the above results to more general dynamic cost games and relax the independence hypothesis of the sequence of players’ demands at different stages.     

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.     

Processing games with shared interest

This paper introduces processing problems with shared interest as an extension of processing situations with restricted capacities (Meertens, M., et al., Processing games with restricted capacities, 2004). Next to an individual capacity to handle jobs, each player now may have interest in the completion of more than one job, and the degrees of interest may vary among players. By cooperating the players can bundle their capacities and follow an optimal processing scheme to minimize total joint costs. The resulting cost allocation problem is analyzed by considering an associated cooperative cost game. An explicit core allocation of this game 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.     

Constrained core solutions for totally positive games with ordered players

In many applications of cooperative game theory to economic allocation problems, such as river-, polluted river- and sequencing games, the game is totally positive (i.e., all dividends are nonnegative), and there is some ordering on the set of the players. A totally positive game has a nonempty core. In this paper we introduce constrained core solutions for totally positive games with ordered players which assign to every such a game a subset of the core. These solutions are based on the distribution of dividends taking into account the hierarchical ordering of the players. The Harsanyi constrained core of a totally positive game with ordered players is a subset of the core of the game and contains the Shapley value. For special orderings it coincides with the core or the Shapley value. The selectope constrained core is defined for acyclic orderings and yields a subset of the Harsanyi constrained core. We provide a characterization for both solutions.     

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.     

On the Structural Stability of Values for Cooperative Games

It is generally assumed that any set of players can form a feasible coalition for classical cooperative games. But, in fact, some players may withdraw from the current game and form a union, if this makes them better paid than proposed. Based on the principle of coalition split, this paper presents an endogenous procedure of coalition formation by levels and bargaining for payoffs simultaneously, where the unions formed in the previous step continue to negotiate with others in the next step as “individuals,” looking for maximum share of surplus by organizing themselves as a partition. The structural stability of the induced payoff configuration is discussed, using two stability criteria of core notion for cooperative games and strong equilibrium notion for noncooperative games.

     

Connection problems in mountains and monotonic allocation schemes

Directed minimum cost spanning tree problems of a special kind are studied, namely those which show up in considering the problem of connecting units (houses) in mountains with a purifier. For such problems an easy method is described to obtain a minimum cost spanning tree. The related cost sharing problem is tackled by considering the corresponding cooperative cost game with the units as players and also the related connection games, for each unit one. The cores of the connection games have a simple structure and each core element can be extended to a population monotonic allocation scheme (pmas) and also to a bi-monotonic allocation scheme. These pmas-es for the connection games result in pmas-es for the cost game.     

Cores in noncooperative games

Noncooperative games in normal form and in characteristic function form are considered. The supergame of the noncooperative game is defined as an infinite sequence of plays of the original game. The notions of strong Pareto equilibrium point (s.p.e.p.) and essential core are introduced. A relationship between the essential core of a noncooperative game and the set of s.p.e.p. of its supergame is asserted. This result is similar to that ofAumann for cooperative games without side payments.     

基于Choquet积分形式的模糊联盟核心

在具有联盟结构的合作对策中,针对局中人以某种程度参与到合作中的情况,研究了模糊联盟结构的合作对策的收益分配问题。首先,定义了具有模糊联盟结构的合作对策及相关概念。其次,定义了Choquet积分形式的模糊联盟核心,提出了该核心与联盟核心之间的关系,对于强凸联盟对策,证明Choquet积分形式的模糊Owen值属于其所对应的模糊联盟核心。最后通过算例,对该分配模型的可行性进行分析。     

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.     

Cooperative games with stochastic payoffs

This paper introduces a new class of cooperative games arising from cooperative decision making problems in a stochastic environment. Various examples of decision making problems that fall within this new class of games are provided. For a class of games with stochastic payoffs where the preferences are of a specific type, a balancedness concept is introduced. A variant of Farkas' lemma is used to prove that the core of a game within this class is non-empty if and only if the game is balanced. Further, other types of preferences are discussed. In particular, the effects the preferences have on the core of these games are considered.     

Cooperative games under bubbly uncertainty

The allocation problem of rewards/costs is a basic question for players, namely, individuals and companies that are planning cooperation under uncertainty. The involvement of uncertainty in cooperative game theory is motivated by the real world in which noise in observation and experimental design, incomplete information and vagueness in preference structures and decision-making play an important role. In this study, a new class of cooperative games, namely, the cooperative bubbly games, where the worth of each coalition is a bubble instead of a real number, is presented. Furthermore, a new solution concept, the bubbly core, is defined. Finally, the properties and the conditions for the non-emptiness of the bubbly core are given. The paper ends with a conclusion and an outlook to related and future studies.