Error message

Deprecated function: Array and string offset access syntax with curly braces is deprecated in include_once() (line 20 of /mnt/web104/a0/07/510451407/htdocs/includes/file.phar.inc).

Approximate Coalitional Equilibria in the Bipolar World

Printer-friendly version
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
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% .
Developed by Paolo Gittoi