Article
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% .
