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.¹     

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.     

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.     

An algorithm for computing the nucleolus of disjunctive non-negative additive games with an acyclic permission structure

A cooperative game with a permission structure describes a situation 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. In this paper we consider non-negative additive games with an acyclic permission structure. For such a game we provide a polynomial time algorithm for computing the nucleolus of the induced restricted game. The algorithm is applied to a market situation where sellers can sell objects to buyers through a directed network of intermediaries.     

Games with Ordered Outcomes

We present a brief review of the most important concepts and results concerning games in which the goal structure is formalized by binary relations called preference relations. The main part of the work is devoted to games with ordered outcomes, i.e., game-theoretic models in which preference relations of players are given by partial orders on the set of outcomes. We discuss both antagonistic games and n-person games with ordered outcomes. Optimal solutions in games with ordered outcomes are strategies of players, situations, or outcomes of the game. In the paper, we consider noncooperative and certain cooperative solutions. Special attention is paid to an extension of the order on the set of probabilistic measures since this question is substantial for constructing the mixed extension of the game with ordered outcomes. The review covers works published from 1953 until now.     

On thek-stability ofm-quota games

We consider thek-stability ofm-quota games ofn players. We prove that anm-quota game (N, v), which satisfies the conditionv(S)=0 for allS, ¦S¦ ≤m ?1, is (m ?1)-stable if and only if there is no weak player. Further, some relationships between ak-stable pair and anm-quota are shown. Some ofLuce's results [1955] on Shapley quota games are generalized tom-quota 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.     

Linear Transformation of Products: Games and Economies

In this paper, we introduce situations involving the linear transformation of products (LTP). LTP situations are production situations where each producer has a single linear transformation technique. First, we approach LTP situations from a (cooperative) game theoretical point of view. We show that the corresponding LTP games are totally balanced. By extending an LTP situation to one where a producer may have more than one linear transformation technique, we derive a new characterization of (nonnegative) totally balanced games: each totally balanced game with nonnegative values is a game corresponding to such an extended LTP situation. The second approach to LTP situations is based on a more economic point of view. We relate (standard) LTP situations to economies in two ways and we prove that the economies are standard exchange economies (with production). Relations between the equilibria of these economies and the cores of cooperative LTP games are investigated.     

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.     

<Emphasis Type="Italic">n</Emphasis>-Person Second-Order Games: A Paradigm Shift in Game Theory

In this paper, we present a new approach to n-person games based on the Habitual domain theory. Unlike the traditional game theory models, the constructed model captures the fact that the underlying changes in the psychological aspects and mind states of the players over the arriving events are the key factors, which determine the dynamic process of coalition formation. We introduce two new concepts of solution for games: strategically stable mind profile and structurally stable mind profile. The theory introduced in this paper overcomes the dichotomy of non-cooperative/cooperative games, prevailing in the existing game theory, which makes game theory more applicable to real-world game situations.     

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.     

Totally balanced combinatorial optimization games

Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty for every induced subgame of it.?We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, and minimum coloring games. Received: November 5, 1998 / Accepted: September 8, 1999?Published online February 23, 2000     

The nucleolus and kernel for simple games or special valid inequalities for 0–1 linear integer programs

An equivalence between simplen-person cooperative games and linear integer programs in 0–1 variables is presented and in particular the nucleolus and kernel are shown to be special valid inequalities of the corresponding 0–1 program. In the special case of weighted majority games, corresponding to knapsack inequalities, we show a further class of games for which the nucleolus is a representation of the game, and develop a single test to show when payoff vectors giving identical amounts or zero to each player are in the kernel. Finally we give an algorithm for computing the nucleolus which has been used successfully on weighted majority games with over twenty players.     

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.     

A note on balancedness and nonemptiness of the core in voting games

Consider a society with a finite number,n, of individuals who have to choose an alternative from a setA in them-dimensional Euclidean space IR ^m . Assuming that the preference relation overA of every individual is convex and continuous, Greenberg (1979) showed some that if the set of winning coalitions (i.e. those that have the veto power) consists of all coalitions with more thanmn/m + 1 individuals the core of the induced game is nonempty. Greenberg and Weber (1984) have strengthened this result by showing that the induced game is in fact balanced. On the other hand Le Breton (1987), Schofield (1984a) and Strnad (1985) have generalized Greenberg's theorem to arbitrary voting games. The purpose of this note is to show that however the induced game is not generally balanced.     

Conflict dissolution by reframing game payoffs using linear perturbations

Human beings have a prevailing drive to achieve their self-interest goals or equilibrium states, which may subsume their social interests. An ideal working environment or cooperative game situation would be one in which each participant or player maximizes his/her own interest while maximizing his/her contribution to the collective group interest. This paper addresses the feasibility, methods, and bounds for reframing a generaln-person game into an ideal game in which full cooperation or a targeted solution can be induced and maintained by the players' self-interest maximization. Criteria for good reframing are introduced. Monotonic games, self-interest cooperative and noncooperative games, and a decomposition theory of general games are also introduced to facilitate the study. It is shown that everyn-person game can be written as the sum of a self-interest cooperative game and a self-interest noncooperative game. Everyn-person game can be reframed so that full cooperation can be achieved by the players' self-interest maximization. Everyn-person game can be reframed so that a targeted solution can be obtained and maintained through the players' self-interest maximization.     

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.     

Potentials and reduced games for share functions

A value function for cooperative games with transferable utility assigns to every game a distribution of the payoffs. A value function is efficient if for every such a game it exactly distributes the worth that can be obtained by all players cooperating together. An approach to efficiently allocate the worth of the ‘grand coalition’ is using share functions which assign to every game a vector whose components sum up to one. Every component of this vector is the corresponding players’ share in the total payoff that is to be distributed. In this paper we give characterizations of a class of share functions containing the Shapley share function and the Banzhaf share function using generalizations of potentials and of Hart and Mas-Colell's reduced game property.     

On balanced games with infinitely many players: Revisiting Schmeidler's result

We consider transferable utility cooperative games with infinitely many players and the core understood in the space of bounded additive set functions. We show that, if a game is bounded below, then its core is non-empty if and only if the game is balanced. This finding generalizes Schmeidler (1967) “On Balanced Games with Infinitely Many Players”, where the game is assumed to be non-negative. We also generalize Schmeidler's (1967) result to the case of restricted cooperation too.     

Monotonicity and dummy free property for multi-choice cooperative games

Given a coalition of ann-person cooperative game in characteristic function form, we can associate a zero-one vector whose non-zero coordinates identify the players in the given coalition. The cooperative game with this identification is just a map on such vectors. By allowing each coordinate to take finitely many values we can define multi-choice cooperative games. In such multi-choice games we can also define Shapley value axiomatically. We show that this multi-choice Shapley value is dummy free of actions, dummy free of players, non-decreasing for non-decreasing multi-choice games, and strictly increasing for strictly increasing cooperative games. Some of these properties are closely related to some properties of independent exponentially distributed random variables. An advantage of multi-choice formulation is that it allows to model strategic behavior of players within the context of cooperation.Partially funded by the NSF grant DMS-9024408