The cooperative facility location game is a
cooperative game of
cost sharing In health care, cost sharing occurs when patients pay for a portion of health care costs not covered by health insurance. The "out-of-pocket" payment varies among healthcare plans and depends on whether or not the patient chooses to use a healthcare ...
. The goal is to share the cost of opening new facilities between the clients enjoying these facilities.
[Kamal Jain and Mohammad Mahdian, "Cost Sharing". Chapter 15 in ]
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
,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
Core or cores may refer to:
Science and technology
* Core (anatomy), everything except the appendages
* Core (manufacturing), used in casting and molding
* Core (optical fiber), the signal-carrying portion of an optical fiber
* Core, the centra ...
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 The Bondareva–Shapley theorem, in game theory, describes a necessary and sufficient condition for the non-emptiness of the core of a cooperative game in characteristic function form. Specifically, the game's core is non-empty if and only if th ...
, gives necessary and sufficient conditions for a game to have nonempty core.
See also
*
Facility location (optimization problem)
The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering fac ...
*
Facility location (competitive game)
*
Cost-sharing mechanism
In economics and mechanism design, a cost-sharing mechanism is a process by which several agents decide on the scope of a public product or service, and how much each agent should pay for it. Cost-sharing is easy when the marginal cost is constant: ...
References
{{reflist
Cooperative games