www.coalitiontheory.net
Published on www.coalitiontheory.net (http://coalitiontheory.net)

Home > Approximate Coalitional Equilibria in the Bipolar World

Approximate Coalitional Equilibria in the Bipolar World

Article
Author/s: 
Andrei Golman, Daniil Musatov
Editors: 
Evtushenko Y., Jaćimović M., Khachay M., Kochetov Y., Malkova V., Posypkin M.
OPTIMA 2018: Optimization and Applications (book)
Publisher: 
Springer
Year: 
2019
Journal pages: 
512-526
ISBN: 
978-3-030-10934-9
Book article [1]
We study a discrete model of jurisdiction formation in the spirit of Alesina and Spolaore. A finite number of agents live along a line. They can be divided into several groups. If a group is formed, then some facility is located at its median and every member x of a group S with a median m pays 1|S|+|x−m| . We consider the notion of coalitional stability: a partition is stable if no coalition wishes to form a new group decreasing the cost of all members. It was shown by Savvateev et al. [4] that no stable partition may exist even for 5 agents living at 2 points. We now study approximately stable partitions: no coalition wishes to form a new group decreasing all costs by at least ϵ . In this work, we define a relative measure of partition instability and consider bipolar worlds where all agents live in just 2 points. We prove that the maximum possible value of this measure is approximately 6.2% .
Tags: 
Coalition Formation Theory [2]

Source URL:http://coalitiontheory.net/content/approximate-coalitional-equilibria-bipolar-world

Links
[1] https://link.springer.com/chapter/10.1007/978-3-030-10934-9_36 [2] http://coalitiontheory.net/research-areas/coalition-formation-theory