Inheritance of convexity for the $$\mathcal {P}_{\min }$$ P min -restricted game
- PDF / 1,733,001 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 91 Downloads / 184 Views
Inheritance of convexity for the Pmin -restricted game A. Skoda1 Received: 9 July 2019 / Revised: 30 March 2020 / Accepted: 1 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We consider restricted games on weighted graphs associated with minimum partitions. We replace in the classical definition of Myerson restricted game the connected components of any subgraph by the sub-components corresponding to a minimum partition. This minimum partition Pmin is induced by the deletion of the minimum weight edges. We provide a characterization of the graphs satisfying inheritance of convexity from the underlying game to the restricted game associated with Pmin . Moreover, we prove that these graphs can be recognized in polynomial time. Keywords Cooperative game · Convexity · Graph-restricted game · Graph partitions Mathematics Subject Classification 91A12 · 91A43 · 90C27 · 05C75
1 Introduction A cooperative game is a pair (N , v) where N is a finite set of players and v : 2 N → R is a set function assigning a worth to each coalition of players with v(∅) = 0. For any coalition A ⊆ N , v(A) represents the worth that players in A can generate by cooperation. However, in many situations, the cooperation of players may be restricted by some communication or social structures. Then, the worths of coalitions have to be modified to take these restrictions into account, leading to the introduction of restricted games. Lots of restricted games considered in the literature can be described by the P-restricted game introduced by Skoda (2017). P is a correspondence associating with any subset A of N a partition P(A) of A. The partition restricted game (N , v) associated with P, called P-restricted game, is defined by: v(A) =
v(F), for all A ⊆ N .
(1)
F∈P (A)
B 1
A. Skoda [email protected] Centre d’Economie de la Sorbonne, Université de Paris I, 106-112 Bd de l’Hôpital, 75013 Paris, France
123
A. Skoda
This partition restricted game appears in many different works with specific correspondences. A founding example is the graph-restricted game introduced by Myerson (1977) for communication games. Communication games are cooperative games (N , v) defined on the set of vertices N of an undirected graph G = (N , E). Assuming that the members of a given coalition can cooperate if and only if they are connected in G, the Myerson graph-restricted game (N , v G ) is defined by v G (A) = F∈P M (A) v(F) for all A ⊆ N , where P M (A) is the partition of A into connected components. Many other correspondences have been considered to define restricted games (see, e.g., Algaba et al. 2001; Bilbao 2000, 2003; Faigle 1989; Grabisch and Skoda 2012; Grabisch 2013). For a given correspondence, a classical problem is to study the inheritance of convexity from the initial game (N , v) to the restricted game (N , v). Inheritance of convexity is of special interest as it implies that good properties are inherited, for instance superadditivity, non-emptiness of the core, and that the Shapley value i
Data Loading...
