Balancedness conditions for exact games

We provide two new characterizations of exact games. First, a game is exact if and only if it is exactly balanced; and second, a game is exact if and only if it is totally balanced and overbalanced. The condition of exact balancedness is identical to the one of balancedness, except that one of the balancing weights may be negative, while for overbalancedness one of the balancing weights is required to be non-positive and no weight is put on the grand coalition. Exact balancedness and overbalancedness are both easy to formulate conditions with a natural game-theoretic interpretation and are shown to be useful in applications. Using exact balancedness we show that exact games are convex for the grand coalition and we provide an alternative proof that the classes of convex and totally exact games coincide. We provide an example of a game that is totally balanced and convex for the grand coalition, but not exact. Finally we relate classes of balanced, totally balanced, convex for the grand coalition, exact, totally exact, and convex games to one another.     

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.     

The maximum and the addition of assignment games

In the framework of two-sided assignment markets, we first consider that, with several markets available, the players may choose where to trade. It is shown that the corresponding game, represented by the maximum of a finite set of assignment games, may not be balanced. Some conditions for balancedness are provided and, in that case, properties of the core are analyzed. Secondly, we consider that players may trade simultaneously in more than one market and then add up the profits. The corresponding game, represented by the sum of a finite set of assignment games, is balanced. Moreover, under some conditions, the sum of the cores of two assignment games coincides with the core of the sum game.     

Fuzzy cores and fuzzy balancedness

We study the relation between the fuzzy core and balancedness for fuzzy games. For regular games, this relation has been studied by Bondareva (Problemy Kibernet 10:119–139, 1963) and Shapley (Naval Res Logist Q 14: 453–460, 1967). First, we gain insight in this relation when we analyse situations where the fuzzy game is continuous. Our main result shows that any fuzzy game has a non-empty core if and only if it is balanced. We also consider deposit games to illustrate the use of the main result.     

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.     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

多选择NTU结构对策下的社会稳定核心

本文研究了多选择情形下NTU结构对策及其社会稳定核心的理论和应用。定义了多选择NTU结构对策的转移率规则和支付依赖平衡性质,给出了K-K-M-S定理在多选择NTU结构对策下的一个扩展形式,并用扩展后的K-K-M-S定理证明了如果转移率规则包含某些力量函数值,且多选择NTU结构对策关于转移率规则是支付依赖平衡的,则多选择NTU结构对策的社会稳定核心是非空的。     

On the balancedness of multiple machine sequencing games

This paper takes a game theoretical approach to sequencing situations with m parallel and identical machines. We show that in a cooperative environment cooperative m-sequencing games, which involve n players, give rise to m-machine games, which involve m players. Here, n corresponds to the number of jobs in an m-sequencing situation, and m corresponds to the number of machines in the same m-sequencing situation. We prove that an m-sequencing game is balanced if and only if the corresponding m-machine game is balanced. Furthermore, it is shown that m-sequencing games are balanced if m∈{1,2}. Finally, if m⩾3, balancedness is established for two special classes of m-sequencing games. Furthermore, we consider a special class of m-sequencing situations in a noncooperative setting and show that a transfer payments scheme exists that is both incentive compatible and budget balanced.     

Production-inventory games and PMAS-games: Characterizations of the Owen point

Production-inventory games were introduced in [Guardiola, L.A., Meca, A., Puerto, J. (2008). Production-Inventory games: A new class of totally balanced combinatorial optimization games. Games Econom. Behav. doi:10.1016/j.geb.2007.02.003] as a new class of totally balanced combinatorial optimization games. From among all core-allocations, the Owen point was proposed as a specifically appealing solution. In this paper we study some relationships of the class of production-inventory games and other classes of new and known games. In addition, we propose three axiomatic characterizations of the Owen point. We use eight axioms for these characterizations, among those, inessentiality and additivity of players’ demands are used for the first time in this paper.     

On the core of ordered submodular cost games

A general ordertheoretic linear programming model for the study of matroid-type greedy algorithms is introduced. The primal restrictions are given by so-called weakly increasing submodular functions on antichains. The LP-dual is solved by a Monge-type greedy algorithm. The model offers a direct combinatorial explanation for many integrality results in discrete optimization. In particular, the submodular intersection theorem of Edmonds and Giles is seen to extend to the case with a rooted forest as underlying structure. The core of associated polyhedra is introduced and applications to the existence of the core in cooperative game theory are discussed. Received: November 2, 1995 / Accepted: September 15, 1999?Published online February 23, 2000     

The core of a cooperative game without side payments

For cooperative games without side payments, there are several types of conditions which guarantee nonemptiness of the core, for example balancedness and convexity. In the present paper, a general condition for nonempty core is introduced which includes the known ones as special cases. Moreover, it is shown that every game with nonempty core satisfies this condition.     

Balancedness of multiple machine sequencing games revisited

We study m-sequencing games, which were introduced by [Hamers, H., Klijn, F., Suijs, J., (1999). On the balancedness of multiple machine sequencing games. European Journal of Operational Research 119, 678–691]. We answer the open question whether all these games are balanced in the negative. We do so, by an example of a 3-sequencing situation with 5 jobs, whose associated 3-sequencing game has an empty core. The counterexample finds its basis in an inconsistency in [Hamers et al., ibid], which was probably overlooked by the authors. This observation demands for a detailed reconsideration of their proofs.¹     

Axiomatizations of the core on the universal domain and other natural domains

We prove that the core on the set of all transferable utility games with players contained in a universe of at least five members can be axiomatized by the zero inessential game property, covariance under strategic equivalence, anonymity, boundedness, the weak reduced game property, the converse reduced game property, and the reconfirmation property. These properties also characterize the core on certain subsets of games, e.g., on the set of totally balanced games, on the set of balanced games, and on the set of superadditive games. Suitable extensions of these properties yield an axiomatization of the core on sets of nontransferable utility games. Received September 1999/Final version December 2000     

A convex representation of totally balanced games

We analyze the least increment function, a convex function of n variables associated to an n-person cooperative game. Another convex representation of cooperative games, the indirect function, has previously been studied. At every point the least increment function is greater than or equal to the indirect function, and both functions coincide in the case of convex games, but an example shows that they do not necessarily coincide if the game is totally balanced but not convex. We prove that the least increment function of a game contains all the information of the game if and only if the game is totally balanced. We also give necessary and sufficient conditions for a function to be the least increment function of a game as well as an expression for the core of a game in terms of its least increment function.     

k-Balanced games and capacities

In this paper, we present a generalization of the concept of balanced game for finite games. Balanced games are those having a nonempty core, and this core is usually considered as the solution of the game. Based on the concept of k-additivity, we define the so-called k-balanced games and the corresponding generalization of core, the k-additive core, whose elements are not directly imputations but k-additive games. We show that any game is k-balanced for a suitable choice of k, so that the corresponding k-additive core is not empty. For the games in the k-additive core, we propose a sharing procedure to get an imputation and a representative value for the expectations of the players based on the pessimistic criterion. Moreover, we look for necessary and sufficient conditions for a game to be k-balanced. For the general case, it is shown that any game is either balanced or 2-balanced. Finally, we treat the special case of capacities.     

Totally monotonic games and flow games

Equivalences between totally balanced games and flow games, and between monotonic games and pseudoflow games are well-known. This paper shows that for every totally monotonic game there exists an equivalent flow game and that for every monotonic game, there exists an equivalent flow-based secondary market game.     

A characterization of edge-perfect graphs and the complexity of recognizing some combinatorial optimization games

We characterize edge-perfect graphs and prove that it is co-NP-complete to recognize them. In consequence, recognizing the defining matrices of totally balanced packing games is also co-NP-complete, in contrast with the polynomiality for the covering case. In addition, we solve the computational complexity of universally balanced (with respect to the resources constraints) packing games.     

On the core and nucleolus of directed acyclic graph games

We introduce directed acyclic graph (DAG) games, a generalization of standard tree games, to study cost sharing on networks. This structure has not been previously analyzed from a cooperative game theoretic perspective. Every monotonic and subadditive cost game—including monotonic minimum cost spanning tree games—can be modeled as a DAG-game. We provide an efficiently verifiable condition satisfied by a large class of directed acyclic graphs that is sufficient for the balancedness of the associated DAG-game. We introduce a network canonization process and prove various structural results for the core of canonized DAG-games. In particular, we characterize classes of coalitions that have a constant payoff in the core. In addition, we identify a subset of the coalitions that is sufficient to determine the core. This result also guarantees that the nucleolus can be found in polynomial time for a large class of DAG-games.     

Highway games on weakly cyclic graphs

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera (2007) introduce highway problems and the corresponding cooperative cost games called highway games to address the problem of fair allocation of the construction costs in case the underlying graph is a tree. In this paper, we study the concavity and the balancedness of highway games on weakly cyclic graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. We show that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we prove that highway games on weakly cyclic graphs are balanced.     

A generalization of the Shapley–Ichiishi result

The Shapley–Ichiishi result states that a game is convex if and only if the convex hull of marginal vectors equals the core. In this paper, we generalize this result by distinguishing equivalence classes of balanced games that share the same core structure. We then associate a system of linear inequalities with each equivalence class, and we show that the system defines the class. Application of this general theorem to the class of convex games yields an alternative proof of the Shapley–Ichiishi result. Other applications range from computation of stable sets in non-cooperative game theory to determination of classes of TU games on which the core correspondence is additive (even linear). For the case of convex games we prove that the theorem provides the minimal defining system of linear inequalities. An example shows that this is not necessarily true for other equivalence classes of balanced games.