# Approximate Coalitional Equilibria in the Bipolar World

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

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