CAPACITIES AND GAMES ON LATTICES: A SURVEY OF RESULTS
---
paper_title: Introduction to the Theory of Cooperative Games

paper_content:

"Introduction to the Theory of Cooperative Games" systematically studies the main solutions of cooperative games: the core, bargaining set, kernel, nucleolus, and the Shapley value of TU games, and the core, the Shapley value, and the ordinal bargaining set of NTU games. To each solution, a separate chapter is devoted, in which its properties are investigated in full detail. Moreover, important variants are defined or even intensively analyzed. Separate chapters cover continuity, dynamics, and geometric properties of solutions of TU games. This study culminates in uniform and coherent axiomatizations of all the foregoing solutions (excluding the bargaining set). Except for the Shapley value such axiomatizations have not appeared in any book. Moreover, "Introduction to the Theory of Cooperative Games" contains a detailed analysis of the main results on cooperative games without side payments. Such analysis is very limited or non-existent in the existing literature on game theory.
---
paper_title: Cooperative Games, Solutions and Applications

paper_content:

I Cooperative Games and Examples.- II Solution Concepts for Cooperative Games and Related Subjects.- III the ?-Value.- IV A Game Theoretic Approach to the Cost Allocation Problem by Means of the ?-Value, the Nucleolus and the Shapley Value.- V Convex Games and Solution Concepts.- VI Division Rules and Associated Game Theoretic Solutions for Bankruptcy Problems.- VII k-Convex Games and Solution Concepts.- References.- Author Index.
---
paper_title: Non-additive measure and integral

paper_content:

Preface. 1. Integration of Monotone Functions on Intervals. 2. Set Functions and Caratheodory Measurability. 3. Construction of Measures using Topology. 4. Distribution Functions, Measurability and Comonotonicity of Functions. 5. The Asymmetric Integral. 6. The Subadditivity Theorem. 7. The Symmetric Integral. 8. Sequences of Functions and Convergence Theorems. 9. Nullfunctions and the Lebesgue Spaces Lp. 10. Families of Measures and their Envelopes. 11. Densities and the Radon-Nikodym Theorem. 12. Products. 13. Representing Functionals as Integrals. References. Index.
---
paper_title: Cooperative Games on Combinatorial Structures

paper_content:

Preface. 1. Structures. 2. Linear optimization methods. 3. Discrete convex analysis. 4. Computational complexity. 5. Restricted games by partition systems. 6. Restricted games by union stable systems. 7. Values for games on convex geometries. 8. Values for games on matroids. 9. The core, the selectope and the Weber set. 10. Simple games on closure spaces. 11. Voting power. 12. Computing values with Mathematica. Bibliography. Index.
---
paper_title: Ternary Voting Games

paper_content:

We define ternary voting games $(TVGs)$, a generalization of simple voting games $(SVGs)$. In a play of an SVG each voter has just two options: voting `yes' or `no'. In a TVG a third option is added: abstention. Every SVG can be regarded as a (somewhat degenerate) TVG; but the converse is false. We define appropriate generalizations of the Shapley-Shubik and Banzhaf indices for TVGs. We define also the responsiveness (or degree of democratic participation) of a TVG and determine, for each n, the most responsive TVGs with n voters. We show that these maximally responsive TVGs are more responsive than the corresponding SVGs.
---
paper_title: The Shapley value for cooperative games under precedence constraints

paper_content:

Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.
---
paper_title: N-person games in partition function form

paper_content:

This paper gives a formulation of a theory of n‐person cooperative games with side payments in terms of a partition function which is defined on the set of all partitions of the set of players. The results for all games with n ≤ 3 are presented. This development generalizes the von Neumann‐Morgenstern theory of games in characteristic function form.
---
paper_title: Models in Cooperative Game Theory: Crisp, Fuzzy, and Multi-Choice Games

paper_content:

Cooperative Games with Crisp Coalitions.- Cooperative Games with Fuzzy Coalitions.- Multichoice Games.
---
paper_title: Shapley Value for Multichoice Cooperative Games, I

paper_content:

Abstract We extend cooperative games in characteristic function form to multichoice cooperative games. In such multichoice games, Shapley value is extended. The explicit formula is given to compute the value. American Mathematical Society Classification Numbers: 90D12, 90D40; Journal of Economic Literature Classification Numbers: C71, D46, D61, D72.
---
paper_title: The core of games on convex geometries

paper_content:

Abstract A game on a convex geometry is a real-valued function defined on the family L of the closed sets of a closure operator which satisfies the finite Minkowski–Krein–Milman property. If L is the Boolean algebra 2N then we obtain a n-person cooperative game. We will introduce convex and quasi-convex games on convex geometries and we will study some properties of the core and the Weber set of these games.
---
paper_title: Axioms for the Shapley value on convex geometries

paper_content:

The purpose of this article is an extension of Shapley's value for games with restricted cooperation. The classical model of cooperative game where every subset of players is a feasible coalition may be unrealistic. The feasible coalitions in our model will be the convex sets, i.e., those subsets of players belonging to a convex geometry L. In the last section, we apply this model to several examples about the power in the Council of Ministers of the European Union.
---
paper_title: Cooperative Games on Combinatorial Structures

paper_content:

Preface. 1. Structures. 2. Linear optimization methods. 3. Discrete convex analysis. 4. Computational complexity. 5. Restricted games by partition systems. 6. Restricted games by union stable systems. 7. Values for games on convex geometries. 8. Values for games on matroids. 9. The core, the selectope and the Weber set. 10. Simple games on closure spaces. 11. Voting power. 12. Computing values with Mathematica. Bibliography. Index.
---
paper_title: Triangular Norm-Based Measures and Games with Fuzzy Coalitions

paper_content:

Introduction. I. Triangular Norm-Based Tribes. II. Triangular Norm-Based Measures. III. Too-Measures. IV. Games with Fuzzy Coalitions. V. Extensions of the Diagonal Value. VI. Related Topics and Applications. Bibliography. Index.
---
paper_title: Capacities on lattices and k-ary capacities

paper_content:

We propose a general notion of capacity defined on any finite distributive lattice, encompassing usual capacities, bi-capacities, and their immediate extensions called k-ary capacities. We define key notions such as Mobius transform, derivative, Shapley value and Choquet integral.
---
paper_title: The Shapley value for cooperative games under precedence constraints

paper_content:

Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.
---
paper_title: Extensions of functions of 0-1 variables and applications to combinatorial optimization

paper_content:

For in § 2 we introduce and study “tight extensions” fD : [0, 1]n → R, defined on each n-simplex Di of a triangulation D of [0,1]n, with all vertices in {0,1}n, as the unique affine function which interpolates f at the vertices of Di. In § 3 we study convexity of tight extensions. In §4 we show the existence of polyhedral convex (generally, non-tight) extensions. As applications, in §5 we give some duality theorems for minimization and maximization of submodular functions and in §6 (Appendix) we obtain new insight into the “greedy solutions” of a certain linear maximization problem.
---
paper_title: Capacities on lattices and k-ary capacities

paper_content:

We propose a general notion of capacity defined on any finite distributive lattice, encompassing usual capacities, bi-capacities, and their immediate extensions called k-ary capacities. We define key notions such as Mobius transform, derivative, Shapley value and Choquet integral.
---
paper_title: Aggregation of Interacting Criteria by Means of the Discrete Choquet Integral

paper_content:

The most often used operator to aggregate criteria in decision making problems is the classical weighted arithmetic mean. In many problems however, the criteria considered interact, and a substitute to the weighted arithmetic mean has to be adopted. Under rather natural conditions, the discrete Choquet integral is proved to be an adequate aggregation operator that extends the weighted arithmetic mean by the taking into consideration of the interaction among criteria. The axiomatic that supports the Choquet integral is presented and some subfamilies are studied.
---
paper_title: The Shapley value for cooperative games under precedence constraints

paper_content:

Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.
---
paper_title: Models in Cooperative Game Theory: Crisp, Fuzzy, and Multi-Choice Games

paper_content:

Cooperative Games with Crisp Coalitions.- Cooperative Games with Fuzzy Coalitions.- Multichoice Games.
---
paper_title: Shapley Value for Multichoice Cooperative Games, I

paper_content:

Abstract We extend cooperative games in characteristic function form to multichoice cooperative games. In such multichoice games, Shapley value is extended. The explicit formula is given to compute the value. American Mathematical Society Classification Numbers: 90D12, 90D40; Journal of Economic Literature Classification Numbers: C71, D46, D61, D72.
---
paper_title: An axiomatization of the Shapley value and interaction index for games on lattices

paper_content:

Games on lattices generalize classical cooperative games (coalitional games), bi-cooperative games, multichoice games, etc., and provide a general framework to define actions of players in a cooperative game. We provide here an axiomatization of the Shapley value and interaction index for such games.
---
paper_title: Games on lattices, multichoice games and the Shapley value: a new approach

paper_content:

Multichoice games have been introduced by Hsiao and Raghavan as a generalization of classical cooperative games. An important notion in cooperative game theory is the core of the game, as it contains the rational imputations for players. We propose two definitions for the core of a multichoice game, the first one is called the precore and is a direct generalization of the classical definition. We show that the precore coincides with the definition proposed by Faigle, and that it contains unbounded imputations, which makes its application questionable. A second definition is proposed, imposing normalization at each level, causing the core to be a convex closed set. We study its properties, introducing balancedness and marginal worth vectors, and defining the Weber set and the pre-Weber set. We show that the classical properties of inclusion of the (pre)core into the (pre)-Weber set as well as their equality remain valid. A last section makes a comparison with the core defined by van den Nouweland et al.
---
paper_title: Derivative of functions over lattices as a basis for the notion of interaction between attributes

paper_content:

The paper proposes a general notion of interaction between attributes, which can be applied to many fields in decision making and data analysis. It generalizes the notion of interaction defined for criteria modelled by capacities, by considering functions defined on lattices. For a given problem, the lattice contains for each attribute the partially ordered set of remarkable points or levels. The interaction is based on the notion of derivative of a function defined on a lattice, and appears as a generalization of the Shapley value or other probabilistic values.
---
paper_title: Some Characterizations of Lower Probabilities and Other Monotone Capacities through the use of Möbius Inversion.

paper_content:

Monotone capacities (on finite sets) of finite or infinite order (lower probabilities) are characterized by properties of their Mobius inverses. A necessary property of probabilities dominating a given capacity is demonstrated through the use of Gale’s theorem for the transshipment problem. This property is shown to be also sufficient if and only if the capacity is monotone of infinite order. A characterization of dominating probabilities specific to capacities of order 2 is also proved.
---
paper_title: On the entropy of fuzzy measures

paper_content:

Fuzzy measures provides a structure for modeling the knowledge available about variables whose values are unknown and uncertain. A large class of different types of uncertainty can be represented in this framework. In this work, we provide a measure of entropy that can be used to calculate the amount of uncertainty associated with a fuzzy measure.
---
paper_title: Entropy of capacities on lattices and set systems

paper_content:

We propose a definition for the entropy of capacities defined on lattices. Classical capacities are monotone set functions and can be seen as a generalization of probability measures. Capacities on lattices address the general case where the family of subsets is not necessarily the Boolean lattice of all subsets. Our definition encompasses the classical definition of Shannon for probability measures, as well as the entropy of Marichal defined for classical capacities. Some properties and examples are given.
---
paper_title: Entropy of Discrete Fuzzy Measures

paper_content:

The concept of entropy of a discrete fuzzy measure has been recently introduced in two different ways. A first definition was proposed by Marichal in the aggregation framework, and a second one by Yager in the framework of uncertain variables. We present a comparative study between these two proposals and point out their properties. We also propose a definition for the entropy of an ordinal fuzzy measure, that is, a fuzzy measure taking its values in an ordinal scale in the sense of measurement theory.
---
paper_title: General entropy of general measures

paper_content:

The concept of entropy is an important part of the theory of additive measures. In this paper, a definition of entropy is introduced for general (not necessarily additive) measures as the infinum of the Shannon entropies of "subordinate" additive measures. Several properties of the general entropy are discussed and proved. Some of the properties require that the measure belongs to the class of so-called "equientropic" general measures introduced and studied in this paper. The definition of general entropy is extended to the countable case for which a sufficient condition of convergence is proved. We introduce a method of "conditional combination" of general measures and prove that in that case the general entropy possesses the "subset independence" property.
---
paper_title: Entropy of discrete choquet capacities

paper_content:

We introduce a measure of entropy for any discrete Choquet capacity and we interpret it in the setting of aggregation by the Choquet integral.
---
paper_title: An axiomatization of entropy of capacities on set systems

paper_content:

We present an axiomatization of the entropy of capacities defined on set systems which are not necessarily the whole power set, but satisfy a condition of regularity. This entropy encompasses the definition of Marichal and Roubens for the entropy of capacities. Its axiomatization is in the spirit of the one of Faddeev for the classical Shannon entropy. In addition, we present also an axiomatization of the entropy for capacities proposed by Dukhovny
---
paper_title: Entropy of bi-capacities

paper_content:

In the context of multicriteria decision making whose aggregation process is based on the Choquet integral, bi-capacities can be regarded as a natural extension of capacities when the underlying evaluation scale is bipolar. The notion of entropy, recently generalized to capacities to measure their uniformity, is now extended to bi-capacities. We show that the resulting entropy measure has a very natural interpretation in terms of the Choquet integral and satisfies many natural properties that one would expect from an entropy measure.
---
paper_title: A general construction for unipolar and bipolar interpolative aggregation

paper_content:

We present a general view of interpolative aggregation, using the geometric realization of a poset, and its natural triangulation. This includes as particular cases the Choquet integral for capacities and k-ary capacities. In a second part, we address the problem of extending a given interpolative aggregation function, considered as unipolar, to bipolar aggregation.
---
paper_title: Cooperative Games on Combinatorial Structures

paper_content:

Preface. 1. Structures. 2. Linear optimization methods. 3. Discrete convex analysis. 4. Computational complexity. 5. Restricted games by partition systems. 6. Restricted games by union stable systems. 7. Values for games on convex geometries. 8. Values for games on matroids. 9. The core, the selectope and the Weber set. 10. Simple games on closure spaces. 11. Voting power. 12. Computing values with Mathematica. Bibliography. Index.
---
paper_title: Entropy of capacities on lattices and set systems

paper_content:

We propose a definition for the entropy of capacities defined on lattices. Classical capacities are monotone set functions and can be seen as a generalization of probability measures. Capacities on lattices address the general case where the family of subsets is not necessarily the Boolean lattice of all subsets. Our definition encompasses the classical definition of Shannon for probability measures, as well as the entropy of Marichal defined for classical capacities. Some properties and examples are given.
---

Title: CAPACITIES AND GAMES ON LATTICES: A SURVEY OF RESULTS

Section 1: Introduction
Description 1: Introduce the emergence of new notions of capacities and games on general structures and the main motivation behind these generalizations.

Section 2: Capacities, fuzzy measures, games and the like
Description 2: Define capacities, fuzzy measures, and transferable utility games, and discuss their various contexts and applications.

Section 3: Generalizations of games and capacities
Description 3: Discuss the motivations for the generalizations of classical games and capacities and present specific examples of such generalizations.

Section 4: Examples of generalized games
Description 4: Introduce main examples of games defined on more general structures, such as games on convex geometries, ternary voting games, and fuzzy games.

Section 5: Examples of generalized capacities
Description 5: Present examples of generalized capacities, including bi-capacities and k-ary capacities.

Section 6: Games and capacities on lattices
Description 6: Discuss games and capacities on lattice structures and provide definitions and useful facts about lattices.

Section 7: Games on product lattices
Description 7: Focus on games on product lattices, demonstrating how previous examples can be cast into this framework.

Section 8: Roadmap
Description 8: Outline the plan to re-build usual tools from game theory and capacity theory for general lattice structures.

Section 9: The Choquet integral for bi-capacities
Description 9: Define the Choquet integral for bi-capacities and explain its fundamental properties and significance.

Section 10: The Möbius transform
Description 10: Present the definition of the Möbius transform for games on lattices and its expression through the Möbius function.

Section 11: The Shapley value
Description 11: Provide an overview of the classical Shapley value and its generalizations for different types of games, including multichoice games.

Section 12: The core
Description 12: Define the concept of the core in game theory and its variations for multichoice games.

Section 13: The entropy
Description 13: Discuss the generalization of the concept of entropy for capacities and its properties.

Section 14: The case of bipolar structures
Description 14: Examine bi-capacities and bi-cooperative games, and discuss their interpretation and symmetrization.

Section 15: Conclusion
Description 15: Summarize the field's current state, highlight active areas of research, and suggest future directions involving set systems and regular set systems.