Facility location (cooperative game)

The cooperative facility location game is a cooperative game of cost sharing. The goal is to share the cost of opening new facilities between the clients enjoying these facilities.^[1]^: 386 The game has the following components:

There are several consumers who need a certain service, e.g, electricity connection.
There are several locations where facilities (e.g. power-stations) can be built.
For every pair of consumer (C) and location (L), there is a fixed cost of serving C from L (e.g, depending on the distance between the power station and the consumer's house). This cost is denoted Cost[C,L].
The cost of serving a group of consumers is lower than the sum of the cost of serving each consumer alone.

EXAMPLE:

There are two facilities, F1 which costs 2 and F2 which costs 2.
There are three consumers, Alice Bob and Carl.
Alice can be served only from F1, with cost 2. So the cost of serving her alone is 2+2=4.
Bob can be served from F1 with cost 2 or from F2 with cost 1. So the cost of serving him alone is 2+1=3.
Carl can be served only from F2, with cost 1. So the cost of serving him alone is 2+1=3.
The cost of serving Alice and Bob is 2+2+2=6 (by building only F1).
The cost of serving Bob and Carl is 2+1+1=4 (by building only F2).
The cost of serving Alice and Carl is 2+2+2+1=7 (by building F1 and F2).
The cost of serving all agents is 2+2+2+1+1=8.

The most socially-desirable outcome of the game is that all agents are served. The cost of this outcome (8 in the above example) can be shared among the agents. A cost-allocation is good if no sub-group of agents can deviate and get a lower cost for itself (such cost-allocation is said to be in the core of the game). In the above example:

The cost-vector (5,2,1) is not in the core, since Alice can deviate and get a cost of only 4. Similarly, the vector (3,3,2) is not in the core since Bob and Carl can deviate together and get a total cost of only 4.
The cost-vectors (4,2,2) and (4,1,3) are in the core.

A classic result in game-theory, the Bondareva–Shapley theorem, gives necessary and sufficient conditions for a game to have nonempty core.

References

^ Kamal Jain and Mohammad Mahdian, "Cost Sharing". Chapter 15 in Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.

[agt-1] Kamal Jain and Mohammad Mahdian, "Cost Sharing". Chapter 15 in Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.

[1]

See also

References