Can I read Coalition Games on Interaction Graphs: A Horticultural Perspective on EtoBox?

Coalition Games on Interaction Graphs: A Horticultural Perspective by Nicolas Bousquet; Zhentao Li; Adrian Vetta is a scholarly article available to read on EtoBox.

What is Coalition Games on Interaction Graphs: A Horticultural Perspective about?

We examine cooperative games where the viability of a coalition is determined by whether or not its members have the ability to communicate amongst themselves independently of non-members. This necessary condition for viability was proposed by Myerson [1977] and is modeled via an interaction graph G = (V, E); a coalition S ⊆ V is then viable if and only if the induced graph G[S] is connected. The non-emptiness of the core of a coalition game can be tested by a well-known covering LP. Moreover, the integrality gap of its dual packing LP defines exactly the multiplicative least-core and the relative cost of stability of the coalition game. This gap is upper bounded by the packing-covering ratio which, for graphical coalition games, is known to be at most the treewidth of the interaction graph plus one [Meir et al. 2013]. We examine the packing-covering ratio and integrality gaps of graphical coalition games in more detail. We introduce the thicket parameter of a graph, and prove it precisely measures the packing-covering ratio. It also approximately measures the primal and dual integrality gaps. The thicket number provides an upper bound of both integrality gaps. Moreover we show tha

Author

Nicolas Bousquet; Zhentao Li; Adrian Vetta

Publisher

ACM

Published

2015

Language

EN