For the class of minimum coloring games (introduced by Deng et al. (1999)) we investigate the existence of population monotonic allocation schemes (introduced by Sprumont (1990)). We show that a minimum coloring game on a graph G has a population monotonic allocation scheme if and only if G is (P4, 2K2)-free (or, equivalently, if its complement graph G is quasi-threshold). Moreover, we provide a procedure that for these graphs always selects an integer population monotonic allocation scheme.
|Place of Publication||Tilburg|
|Publication status||Published - 2011|
|Name||CentER Discussion Paper|
- Minimum coloring game
- population monotonic allocation scheme
- 2K2)-free graph
- quasi-threshold graph