On the vertices of the -additive core

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.     

<Emphasis Type="Italic">p</Emphasis>-additive games: a class of totally balanced games arising from inventory situations with temporary discounts

We introduce a new class of totally balanced cooperative TU games, namely p-additive games. It is inspired by the class of inventory games that arises from inventory situations with temporary discounts (Toledo Ph.D. thesis, Universidad Miguel Hernández de Elche, 2002) and contains the class of inventory cost games (Meca et al. Math. Methods Oper. Res. 57:481–493, 2003). It is shown that every p-additive game and its corresponding subgames have a nonempty core. We also focus on studying the character of concave or convex and monotone p-additive games. In addition, the modified SOC-rule is proposed as a solution for p-additive games. This solution is suitable for p-additive games, since it is a core-allocation which can be reached through a population monotonic allocation scheme. Moreover, two characterizations of the modified SOC-rule are provided. This work was partially supported by the Spanish Ministry of Education and Science and Generalitat Valenciana (grants MTM2005-09184-C02-02, ACOMP06/040, CSD2006-00032). Authors acknowledge valuable comments made by the Editor and the referee.     

On the set of imputations induced by the k-additive core

An extension to the classical notion of core is the notion of k-additive core, that is, the set of k-additive games which dominate a given game, where a k-additive game has its Möbius transform (or Harsanyi dividends) vanishing for subsets of more than k elements. Therefore, the 1-additive core coincides with the classical core. The advantages of the k-additive core is that it is never empty once k ? 2, and that it preserves the idea of coalitional rationality. However, it produces k-imputations, that is, imputations on individuals and coalitions of at most k individuals, instead of a classical imputation. Therefore one needs to derive a classical imputation from a k-order imputation by a so-called sharing rule. The paper investigates what set of imputations the k-additive core can produce from a given sharing rule.     

On the bargaining set, kernel and core of superadditive games

We prove that for superadditive games a necessary and sufficient condition for the bargaining set to coincide with the core is that the monotonic cover of the excess game induced by a payoff be balanced for each imputation in the bargaining set. We present some new results obtained by verifying this condition for specific classes of games. For N-zero-monotonic games we show that the same condition required at each kernel element is also necessary and sufficient for the kernel to be contained in the core. We also give examples showing that to maintain these characterizations, the respective assumptions on the games cannot be lifted. Received: March 1998/Revised version: December 1998     

The multichoice consistent value

We consider multichoice NTU games, i.e., cooperative NTU games in which players can participate in the game with several levels of activity. For these games, we define and characterize axiomatically the multichoice consistent value, which is a generalization of the consistent NTU value for NTU games and of the multichoice value for multichoice TU games. Moreover, we show that this value coincides with the consistent NTU value of a replicated NTU game and we provide a probabilistic interpretation. Received: May 1998/Final version: January 2000     

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     

Efficient Winning Strategies in Random‐Turn Maker–Breaker Games

We consider random‐turn positional games, introduced by Peres, Schramm, Sheffield, and Wilson in 2007. A p‐random‐turn positional game is a two‐player game, played the same as an ordinary positional game, except that instead of alternating turns, a coin is being tossed before each turn to decide the identity of the next player to move (the probability of Player I to move is p ). We analyze the random‐turn version of several classical Maker–Breaker games such as the game Box (introduced by Chvátal and Erd?s in 1987), the Hamilton cycle game and the k‐vertex‐connectivity game (both played on the edge set of ). For each of these games we provide each of the players with a (randomized) efficient strategy that typically ensures his win in the asymptotic order of the minimum value of p for which he typically wins the game, assuming optimal strategies of both players.     

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     

Buyer-seller exactness in the assignment game

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the core of the game. These games will be called buyer-seller exact games and satisfy the condition that each mixed-pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyer-seller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer-seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed-pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a “45^o-lattice” by means of the core of an assignment game can now be answered. Received: March 2002/Revised version: January 2003 RID="*" ID="*"  Institutional support from research grants BEC 2002-00642 and SGR2001-0029 is gratefully acknowledged RID="**" ID="**"  The authors thank the referees for their comments     

The diameter game

A large class of Positional Games are defined on the complete graph on n vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his subgraph has a given — usually monotone — property. Here we introduce the d‐diameter game, which means that Maker wins iff the diameter of his subgraph is at most d. We investigate the biased version of the game; i.e., when the players may take more than one, and not necessarily the same number of edges, in a turn. Our main result is that we proved that the 2‐diameter game has the following surprising property: Breaker wins the game in which each player chooses one edge per turn, but Maker wins as long as he is permitted to choose 2 edges in each turn whereas Breaker can choose as many as (1/9)n^1/8/(lnn)^3/8. In addition, we investigate d‐diameter games for d ≥ 3. The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Robust game theory

We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results. The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the Singapore-MIT Alliance. The research of the author was partially supported by the Singapore-MIT Alliance.     

Solution concepts ofk-convexn-person games

For any positive integersk andn, the subclass ofk-convexn-person games is considered. In casek=n, we are dealing with convexn-person games. Three characterizations ofk-convexn-person games, formulated in terms of the core and certain adapted marginal worth vectors, are given. Further it is shown that fork-convexn-person games the intersection of the (pre)kernel with the core consists of a unique point (namely the nucleolus), but that the (pre)kernel may contain points outside the core. For certain 1-convex and 2-convexn-person games the part of the bargaining set outside the core is even disconnected with the core. The Shapley value of ank-convexn-person game can be expressed in terms of the extreme points of the core and a correction-vector whenever the game satisfies a certain symmetric condition. Finally, theτ-value of ank-convexn-person game is given.     

A natural selection from the core of a TU game: the core-center

We present a new allocation rule for the class of games with a nonempty core: the core-center. This allocation rule selects a centrally located point within the core of any such game. We provide a deep discussion of its main properties.     

Directed Path-width and Monotonicity in Digraph Searching

Directed path-width was defined by Reed, Thomas and Seymour around 1995. The author and P. Hajnal defined a cops-and-robber game on digraphs in 2000. We prove that the two notions are closely related and for any digraph D, the corresponding graph parameters differ by at most one. The result is achieved using the mixed-search technique developed by Bienstock and Seymour. A search is called monotone, in which the robber's territory never increases. We show that there is a mixed-search of D with k cops if and only if there is a monotone mixed-search with k cops. For our cops-and-robber game we get a slightly weaker result: the monotonicity can be guaranteed by using at most one extra cop. On leave from Bolyai Institute, University of Szeged, Hungary. This research has been supported by a Marie Curie Fellowship of the European Community under contract number HPMF-CT-2002-01868 and by OTKA Grants F.030737 and T.34475.     

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.     

Polytope Games

Starting from the definition of a bimatrix game, we restrict the pair of strategy sets jointly, not independently. Thus, we have a set , which is the set of all feasible strategy pairs. We pose the question of whether a Nash equilibrium exists, in that no player can obtain a higher payoff by deviating. We answer this question affirmatively for a very general case, imposing a minimum of conditions on the restricted sets and the payoff. Next, we concentrate on a special class of restricted games, the polytope bimatrix game, where the restrictions are linear and the payoff functions are bilinear. Further, we show how the polytope bimatrix game is a generalization of the bimatrix game. We give an algorithm for solving such a polytope bimatrix game; finally, we discuss refinements to the equilibrium point concept where we generalize results from the theory of bimatrix games.     

Banzhaf Measures for Games with Several Levels of Approval in the Input and Output

An axiomatic characterization of ‘a Banzhaf score’ notion is provided for a class of games called (j,k) simple games with a numeric measure associated to the output set, i.e., games with n players, j ordered qualitative alternatives in the input level and k possible ordered quantitative alternatives in the output. Three Banzhaf measures are also introduced which can be used to determine a player's ‘a priori’ value in such a game. We illustrate by means of several real world examples how to compute these measures. Research partially supported by Grant BFM 2003-01314 of the Science and Technology Spanish Ministry and the European Regional Development Fund.     

Stabilization through taxation inn-person games

In formulating solutions forn-person cooperative games, the concept of stability has played a dominant role. Although the core concept has the strongest stability, the core of a game is often empty. In this paper, the taxation system is incorporated into our framework, so that a modified solution concept, which enjoys the stability of core, can be developed. Various formulations based on principles such astaxation proportional to income andequity after tax are given.     

On multi-choice TU games arising from replica of economies

In this paper we derive a multi-choice TU game from r-replica of exchange economy with continuous, concave and monetary utility functions, and prove that the cores of the games converge to a subset of the set of Edgeworth equilibria of exchange economy as r approaches to infinity. We prove that the dominance core of each balanced multi-choice TU game, where each player has identical activity level r, coincides with the dominance core of its corresponding r-replica of exchange economy. We also give an extension of the concept of the cover of the game proposed by Shapley and Shubik (J Econ Theory 1: 9-25, 1969) to multi-choice TU games and derive some sufficient conditions for the nonemptyness of the core of multi-choice TU game by using the relationship among replica economies, multi-choice TU games and their covers.