The bounded core for games with precedence constraints. (English) Zbl 1272.91023
In this paper, the authors consider cooperative games in which there are restrictions on cooperation. These restrictions are modeled by a hierarchical structure on the set of players (cf. [U. Faigle and W. Kern, Int. J. Game Theory 21, No. 3, 249–266 (1992; Zbl 0779.90078)]), who are motivated by the existence of a partial order in the sense that if a coalition can be formed and a player belongs to a coalition, then, all players preceding him in the partial-order relation are also in the coalition. The classic model of cooperative games as a special case appears when all players are incomparable.
It is a known fact that the core of cooperative games with transferable utility and with precedence constraints can be unbounded. Therefore, they appear in the literature various attempts to define a subset of the core that is bounded and having good properties. Although this core, which is a convex polyhedral set, can have unbounded faces, this paper considers the so-called bounded core that is defined as the union of all bounded faces. The bounded core can be interpreted as the set of core elements such that every player gets the most out of their subordinates. It coincides with the core in classic games. The paper shows that the bounded core is nonempty when the core is nonempty. To do this, they formulate a generalization of the Bondareva-Shapley theorem (cf. [O. N. Bondareva, Probl. Kibern. 10, 119–139 (1963; Zbl 1013.91501)]) for games with precedence constraints given in [U. Faigle, Z. Oper. Res. 33, No. 6, 405–422 (1989; Zbl 0685.90103)]. Furthermore, the bounded core is a continuous correspondence on games with coinciding precedence constraints.
They generalize some well-known properties of solutions on a set of classic games: Pareto optimality, covariance under strategic equivalence, anonymity, boundedness, boundedness w.r.t. singletons, and the two-person zero-inessential game property. Furthermore, they generalize several properties of reduced games (called reduced-game property, weak reduced-game property, converse reduced-game property, reconfirmation property, and reconfirmation property w.r.t. classical games, respectively), for which they first define a generalization of the so-called Davis-Maschler reduced game.
If the set of players has more than four elements, they axiomatically characterize the bounded core by the two-person zero-inessential game property, anonymity, covariance under strategic equivalence, reduced-game property, reconfirmation property w.r.t. classical games, converse reduced-game property, and boundedness. Moreover, the core is the maximum solution that satisfies the two-person zero-inessential game property, anonymity, covariance under strategic equivalence, reduced-game property, reconfirmation property w.r.t. classical games, converse reduced-game property, and boundedness w.r.t. singletons.
Using variants of the reduced-game property, they obtain new characterizations of the bounded core and the core on the so-called games with connected hierarchies, so that these results are valid for any set of players. The proof of the axiomatic characterization of the bounded core is similar to the proof of the axiomatization of the prekernel (cf. [B. Peleg, Int. J. Game Theory 15, 187–200 (1986; Zbl 0629.90099)]).
Finally, they study the independence of the sets of axioms of the main results.
It is a known fact that the core of cooperative games with transferable utility and with precedence constraints can be unbounded. Therefore, they appear in the literature various attempts to define a subset of the core that is bounded and having good properties. Although this core, which is a convex polyhedral set, can have unbounded faces, this paper considers the so-called bounded core that is defined as the union of all bounded faces. The bounded core can be interpreted as the set of core elements such that every player gets the most out of their subordinates. It coincides with the core in classic games. The paper shows that the bounded core is nonempty when the core is nonempty. To do this, they formulate a generalization of the Bondareva-Shapley theorem (cf. [O. N. Bondareva, Probl. Kibern. 10, 119–139 (1963; Zbl 1013.91501)]) for games with precedence constraints given in [U. Faigle, Z. Oper. Res. 33, No. 6, 405–422 (1989; Zbl 0685.90103)]. Furthermore, the bounded core is a continuous correspondence on games with coinciding precedence constraints.
They generalize some well-known properties of solutions on a set of classic games: Pareto optimality, covariance under strategic equivalence, anonymity, boundedness, boundedness w.r.t. singletons, and the two-person zero-inessential game property. Furthermore, they generalize several properties of reduced games (called reduced-game property, weak reduced-game property, converse reduced-game property, reconfirmation property, and reconfirmation property w.r.t. classical games, respectively), for which they first define a generalization of the so-called Davis-Maschler reduced game.
If the set of players has more than four elements, they axiomatically characterize the bounded core by the two-person zero-inessential game property, anonymity, covariance under strategic equivalence, reduced-game property, reconfirmation property w.r.t. classical games, converse reduced-game property, and boundedness. Moreover, the core is the maximum solution that satisfies the two-person zero-inessential game property, anonymity, covariance under strategic equivalence, reduced-game property, reconfirmation property w.r.t. classical games, converse reduced-game property, and boundedness w.r.t. singletons.
Using variants of the reduced-game property, they obtain new characterizations of the bounded core and the core on the so-called games with connected hierarchies, so that these results are valid for any set of players. The proof of the axiomatic characterization of the bounded core is similar to the proof of the axiomatization of the prekernel (cf. [B. Peleg, Int. J. Game Theory 15, 187–200 (1986; Zbl 0629.90099)]).
Finally, they study the independence of the sets of axioms of the main results.
MSC:
| 91A12 | Cooperative games |
References:
| [1] | Bondareva, O. N. (1963). Some applications of linear programming methods to the theory of cooperative games. Problemy Kibernetiki, 10, 119–139. · Zbl 1013.91501 |
| [2] | Derks, J. J. M., & Gilles, R. P. (1995). Hierarchical organization structures and constraints on coalition formation. International Journal of Game Theory, 24, 147–163. · Zbl 0831.90139 · doi:10.1007/BF01240039 |
| [3] | Faigle, U. (1989). Cores of games with restricted cooperation. Zeitschrift für Operations Research [Mathematical Methods of Operations Research], 33, 405–422. · Zbl 0685.90103 |
| [4] | Faigle, U., & Kern, W. (1992). The Shapley value for cooperative games under precedence constraints. International Journal of Game Theory, 21, 249–266. · Zbl 0779.90078 · doi:10.1007/BF01258278 |
| [5] | Fujishige, S. (2005). Annals of discrete mathematics: Vol. 58. Submodular functions and optimization (2nd ed.). Amsterdam: Elsevier. |
| [6] | Gilles, R. P., Owen, G., & van den Brink, R. (1992). Games with permission structures: the conjunctive approach. International Journal of Game Theory, 20, 277–293. · Zbl 0764.90106 · doi:10.1007/BF01253782 |
| [7] | Grabisch, M. (2011). Ensuring the boundedness of the core of games with restricted cooperation. Annals of Operations Research, 191, 137–154. · Zbl 1233.91017 · doi:10.1007/s10479-011-0920-5 |
| [8] | Hwang, Y.-A., & Sudhölter, P. (2001). Axiomatizations of the core on the universal domain and other natural domains. International Journal of Game Theory, 29, 597–623. · Zbl 1060.91016 · doi:10.1007/s001820100060 |
| [9] | Maschler, M., Peleg, B., & Shapley, L. S. (1972). The kernel and bargaining set for convex games. International Journal of Game Theory, 1, 73–93. · Zbl 0251.90056 · doi:10.1007/BF01753435 |
| [10] | Peleg, B. (1986). On the reduced game property and its converse. International Journal of Game Theory, 15, 187–200. · Zbl 0629.90099 · doi:10.1007/BF01769258 |
| [11] | Peleg, B., & Sudhölter, P. (2007). Theory and decisions library, series C: game theory, mathematical programming and operations research. Introduction to the theory of cooperative games (2nd ed.). Berlin: Springer. · Zbl 1193.91002 |
| [12] | Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press. · Zbl 0193.18401 |
| [13] | Shapley, L. S. (1967). On balanced sets and cores. Naval Research Logistics Quarterly, 14, 453–460. · doi:10.1002/nav.3800140404 |
| [14] | Tomizawa, N. (1983). Theory of hyperspace (XVI)–on the structure of hedrons. Papers of the technical group on circuits and systems CAS82-172. Inst. of Electronics and Communications Engineers of Japan. In Japanese. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
