Order cones: a tool for deriving k -dimensional faces of cones of subfamilies of monotone games
- PDF / 580,104 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 58 Downloads / 164 Views
Order cones: a tool for deriving k-dimensional faces of cones of subfamilies of monotone games P. García-Segador1
· P. Miranda2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper we introduce the concept of order cone. This concept is inspired by the concept of order polytopes, a well-known object coming from Combinatorics with which order cones share many properties. Similarly to order polytopes, order cones are a special type of polyhedral cones whose geometrical structure depends on the properties of a partially ordered set (brief poset). This allows to study the geometrical properties of these cones in terms of the subjacent poset, a problem that is usually simpler to solve. Besides, for a given poset, the corresponding order polytope and order cone are deeply related. From the point of view of applicability, it can be seen that many cones appearing in the literature of monotone TU-games are order cones. Especially, it can be seen that the cones of monotone games with restricted cooperation are order cones, no matter the structure of the set of feasible coalitions and thus, they can be studied in a general way applying order cones. Keywords Monotone games · Restricted cooperation · Order polytope · Cone
1 Introduction Consider a finite set of n players N = {1, 2, . . . , n}. We will denote subsets of N by capital letters A, B, . . . and by P (N ) the set of parts of N . A game v is a function v : P (N ) → R satisfying v(∅) = 0. The value v(A) represents the minimal worth coalition A can obtain if all players in A agree to cooperate, no matter what players outside A might do. In general, several additional conditions can be imposed on function v. One of the most natural conditions is monotonicity in v, i.e. v(A) ≤ v(B) if A ⊂ B. This means that if players add to a coalition, the corresponding worth increases. We will denote by MG (N ) the
This paper has been supportesd by the Ministry of Economy and Competitiveness of Spain under Grant PGC2018-095194-B-100 and by the Interdisciplinary Mathematical Institute of Complutense University.
B
P. Miranda [email protected] P. García-Segador [email protected]
1
National Statistics Institute, Paseo de la Castellana, 183, 28071 Madrid, Spain
2
Complutense University of Madrid, Plaza de Ciencias, 3, 28040 Madrid, Spain
123
Annals of Operations Research
set of all monotone games on N . Other popular conditions are additivity, supermodularity, and many others (see Grabisch 2016). On the other hand, it could be the case that some coalitions fail to form. Thus, v cannot be defined on some of the elements of P (N ) and we have a subset FC (N ) of P (N ) containing all feasible coalitions. From now on, we will not include ∅ in FC (N ). Usually, FC (N ) has a concrete structure (for example, FC (N ) could be a lattice if ∅ is added). Thus, depending on the structure of FC (N ), the set of TU-games whose set of feasible coalitions is FC (N ) has different properties. With some abuse of notation, we will denote by v
Data Loading...
