Cooperative Games on Lattices

In cooperative game theory, for a given set of players N, TU-games are functions v : 2 N → 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 2 N . 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 2 N , 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 ∈ R n | x(S) ≥ v(S), ∀S ∈ F , x(N) = v(N)}

where x(S) is a shorthand for ∑ i∈S x i . When F = 2 N , 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.