=Paper=
{{Paper
|id=None
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1062/invited3.pdf
|volume=Vol-1062
}}
==None==
<pdf width="1500px">https://ceur-ws.org/Vol-1062/invited3.pdf</pdf>
<pre>
                    Cooperative Games on Lattices

                                     Michel Grabisch

                                Paris School of Economics
                                     Université Paris I
                           106-112, Bd de l’Hôpital, 75013 Paris
                           michel.grabisch@univ-paris1.fr

     In cooperative game theory, for a given set of players N, TU-games are functions
v : 2N → R which express for each nonempty coalition S ⊆ N of players the best they
can achieve by cooperation.
     In the classical setting, every coalition may form without any restriction, i.e., the
domain of v is indeed 2N . In practice, this assumption is often unrealistic, since some
coalitions may not be feasible for various reasons, e.g., players are political parties with
divergent opinions, or have restricted communication abilities, or a hierarchy exists
among players, and the formation of coalitions must respect the hierarchy, etc.
     Many studies have been done on games defined on specific subdomains of 2N , e.g.,
antimatroids [1], convex geometries [3, 4], distributive lattices [6], or others [2, 5]. In
this paper, we mainly deal with the case of distributive lattices. To this end, we assume
that there exists some partial order  on N describing some hierarchy or precedence
constraint among players, as in [6]. We say that a coalition S is feasible if the coalition
contains all its subordinates, i.e., i ∈ S implies that any j  i belongs to S as well. Then
feasible coalitions are downsets, and by Birkhoff’s theorem, form a distributive lattice.
From now on, we denote by F the set of feasible coalitions, assuming that 0,     / N∈F.
    The main problem in cooperative game theory is to define a rational solution of the
game, that is, supposing that the grand coalition N will form, how to share among its
members the total worth v(N). The core is the most popular solution concept, since it
ensures stability of the game, in the sense that no coalition has an incentive to deviate
from the grand coalition. For a game v on a family F of feasible coalitions, the core is
defined by
                  C (v) = {x ∈ Rn | x(S) ≥ v(S), ∀S ∈ F , x(N) = v(N)}
where x(S) is a shorthand for ∑i∈S xi . When F = 2N , the core is either empty or a convex
bounded polyhedron. However, for games whose cooperation is restricted, the study of
the core becomes much more complex, since it may be unbounded or even contain
no vertices (see a survey in [7]). For the case of games with precedence constraints,
it is known that the core is always unbounded or empty, but contains no line (i.e., it
has vertices). The problem arises then, to select a significant bounded part of the core
as a reasonable concept of solution, since unbounded payments make no sense. We
propose to select a bounded face of the core. A systematic study of bounded faces is
done through the concept of normal collections.
     We also present some results when F is not a distributive lattice, but a set lattice
closed under intersection, or a regular set system.
     Lastly, we introduce games on concept lattices, show that this induces in fact two
games, and give some results on the core.
6     Michel Grabisch


References
 1. E. Algaba, J. M. Bilbao, R. van den Brink, and A. Jiménez-Losada. Cooperative games on
    antimatroids. Discrete Mathematics, 282:1–15, 2004.
 2. S. Béal, E. Rémila, and Ph. Solal. Rooted-tree solutions for tree games. European Journal
    of Operational Research, 203(2):404–408, 2010.
 3. J. M. Bilbao. Axioms for the Shapley value on convex geometries. European Journal of
    Operational Research, 110:368–376, 1998.
 4. J. M. Bilbao, E. Lebrón, and N. Jiménez. The core of games on convex geometries. European
    Journal of Operational Research, 119:365–372, 1999.
 5. U. Faigle, M. Grabisch, and M. Heyne. Monge extensions of cooperation and com-
    munication structures. European Journal of Operational Research, 206:104–110, 2010.
    10.1016/j.ejor.2010.01.043.
 6. U. Faigle and W. Kern. The Shapley value for cooperative games under precedence con-
    straints. Int. J. of Game Theory, 21:249–266, 1992.
 7. M. Grabisch. The core of games on ordered structures and graphs. Annals of Operations
    Research, Vol. 204 (2013), 33-64.
 8. M. Grabisch. Ensuring the boundedness of the core of games with restricted cooperation.
    Annals of Operations Research, 191:137–154, 2011.
 9. M. Grabisch and P. Sudhölter. On the restricted cores and the bounded core of games on
    distributive lattices. Technical Report 2012.67, Centre d’Economie de la Sorbonne, Paris,
    2012. http://ideas.repec.org/s/mse/cesdoc.html.
10. M. Grabisch and P. Sudhölter. The bounded core for games with precedence constraints.
    Annals of Operations Research, Vol. 201 (2012), 251-264. doi: 10.1007/s10479-012-1228-
    9.
11. M. Grabisch and L. J. Xie. The restricted core of games on distributive lattices: how to share
    benefits in a hierarchy. Mathematical Methods of Operations Research, 73:189–208, 2011.

</pre>