Approximate Coalitional Equilibria in the Bipolar World

Printer-friendly version
Andrei Golman, Daniil Musatov
Evtushenko Y., Jaćimović M., Khachay M., Kochetov Y., Malkova V., Posypkin M.
OPTIMA 2018: Optimization and Applications (book)
Journal pages: 
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