Cost Sharing

Motivation: dividing the bill for a shared service

A service provider connects a set $S$ of customers and incurs a cost $c(S)$ . Usually $c(S)$ is the optimum of a combinatorial problem, such as the cheapest network or the cheapest set of facilities. How should $c(S)$ be split? Any answer has to respect two pressures:

individual and group incentives: a coalition that is overcharged can walk away and serve itself;
fairness: identical agents should pay the same, free riders should pay nothing, and so on.

IntuitionThe central question

Is there a way to divide the cost of a joint service so that no group of agents would rather break away — and if so, can we find one efficiently, even build a truthful auction on top of it?

Cooperative games

A cooperative game abstracts away everything except which coalitions can form and what they can achieve. This is von Neumann–Morgenstern’s notion. It contrasts with noncooperative games, which model individual moves.

DefinitionNTU and TU cooperative games

NTU game (nontransferable utility): agents $A$ , $|A| = n$ , and for each coalition $S \subseteq A$ a set $V(S) \subseteq \mathbb{R}^S$ of achievable utility vectors.
TU game (transferable utility): value can be split arbitrarily, so a single number $v(S)$ suffices. Here $v : 2^A \to \mathbb{R}$ , $v(\emptyset) = 0$ , and $V(S) = \{x \in \mathbb{R}^S : \sum_{i \in S} x_i \le v(S)\}$ .

Values may be negative. Cost sharing is the all-nonpositive case, with $v = -c$ . The all-nonnegative case is called surplus sharing.

Model	When it fits	Example
TU	cost is money, divisible arbitrarily	provider’s network-building cost
NTU	”cost” is something that can’t be handed over	each customer’s delay under a network design; outcome set $C(S)$ of delay profiles

The chapter works almost entirely with TU games. “Cost-sharing game” means TU unless stated otherwise.

The running example: facility location

DefinitionDefinition 15.1 — facility location game

There are agents (cities) $A$ and facilities $F$ . Facility $i$ has opening cost $f_i$ , and $d_{ij}$ is a metric connection cost (symmetric, obeys the triangle inequality) on $A \cup F$ . The cost of $S \subseteq A$ is

c(S) = \min_{F' \subseteq F} \Big\{ \sum_{i \in F'} f_i + \sum_{j \in S} \min_{i \in F'} d_{ij} \Big\}.

Component	Detail
Signature	$c : 2^A \to \mathbb{R}_{\ge 0}$
Domain	a coalition of cities that want service
Codomain	the cheapest total bill (opening plus connection) to serve exactly them

Note that $c$ takes no allocation as input. It says what the coalition costs, not who pays.

ExampleExample 15.2 — Fig. 15.1

Cities $a, b, c$ ; facilities 1, 2 with $f_1 = f_2 = 2$ . Distances: $d_{a1} = 2$ , $d_{b1} = 2$ , $d_{b2} = 1$ , $d_{c2} = 1$ ; the rest follow by the triangle inequality (e.g. $d_{1c} = 2+1+1 = 4$ ).

$S$	$\{a\}$	$\{b\}$	$\{c\}$	$\{a,b\}$	$\{b,c\}$	$\{a,c\}$	$\{a,b,c\}$
$c(S)$	4	3	3	6	4	7	8

graph LR
  F1["Facility 1: open cost 2"] ---|"2"| A["city a"]
  F1 ---|"2"| B["city b"]
  B ---|"1"| F2["Facility 2: open cost 2"]
  F2 ---|"1"| C["city c"]

The core

The problem. We want to charge everyone in $A$ so that the grand coalition is stable: no subgroup can do better by serving itself.

DefinitionDefinition 15.3 — core of a TU cost-sharing game

A cost allocation $\alpha \in \mathbb{R}^A$ is in the core if:

Budget balance: $\sum_{j \in A} \alpha_j = c(A)$ ;
Core property: $\sum_{j \in S} \alpha_j \le c(S)$ for every $S \subseteq A$ .

IntuitionWhy these two conditions

Budget balance means the provider recovers its cost, no more and no less. The core property means no coalition is charged more than it would cost to serve itself. If it were, it would secede and the grand coalition would fall apart. Together they are the economic stability of full cooperation.

ExampleExample 15.4 — nonempty, non-unique, and then empty

In Fig. 15.1, both $(4,2,2)$ and $(4,1,3)$ are in the core. So the core need not be a single point.

Now add a facility with cost $3$ at distance $1$ from $a$ and $c$ . Then $c(\{a,c\}) = 5$ , and any core vector would need

\alpha_a + \alpha_b \le 6,\quad \alpha_b + \alpha_c \le 4,\quad \alpha_a + \alpha_c \le 5.

Adding these and halving gives $\sum \alpha \le 7.5 < 8 = c(A)$ . Budget balance is impossible, so the core is empty.

Bondareva–Shapley: when is the core nonempty?

The emptiness proof above averaged pair constraints with weight $\tfrac12$ . The theorem says that such weighted averages are the only obstruction.

DefinitionDefinition 15.5 — balanced collection of weights

$\lambda = (\lambda_S)_{S \subseteq A}$ with $\lambda_S \ge 0$ is balanced if $\sum_{S \ni j} \lambda_S = 1$ for every $j \in A$ .

IntuitionA fractional partition

A balanced collection is a fractional way of splitting $A$ into coalitions in which every agent is covered exactly once in total. An actual partition is the integral case.

TheoremTheorem 15.6 — Bondareva–Shapley

A TU cost-sharing game $(A, c)$ has a nonempty core iff, for every balanced collection of weights $\lambda$ , $\sum_{S \subseteq A} \lambda_S\, c(S) \ge c(A).$

ProofLP duality between allocations and fractional partitions

Step 1: Recast the core as an LP. Consider

\max \sum_{j\in A} \alpha_j \quad \text{s.t.}\quad \sum_{j \in S} \alpha_j \le c(S)\ \ \forall S \subseteq A. \tag{15.1}

Its value is at most $c(A)$ , by the $S = A$ constraint. The core is nonempty iff the value equals $c(A)$ : an optimal point then satisfies every core constraint and is budget-balanced.

Step 2: Take the dual. By strong LP duality, (15.1) has the same value as

\min \sum_{S \subseteq A} \lambda_S\, c(S) \quad \text{s.t.}\quad \sum_{S \ni j} \lambda_S = 1\ \ \forall j,\qquad \lambda_S \ge 0. \tag{15.2}

Step 3: Read off the dual’s feasible set. Feasible $\lambda$ are exactly the balanced collections. So the value is $c(A)$ iff every balanced collection has $\sum \lambda_S c(S) \ge c(A)$ .

∎

ExampleExample 15.4 as a Bondareva–Shapley certificate

$\lambda_{\{a,b\}} = \lambda_{\{b,c\}} = \lambda_{\{a,c\}} = \tfrac12$ , all others $0$ . This is balanced (each city is in two of the pairs), and $\sum \lambda_S c(S) = 7.5 < 8$ .

Approximate core

WarningThe exact core is often useless for hard problems

For most combinatorial games built on NP-hard problems, the core is often empty. Even deciding emptiness is intractable when $c$ is hard to compute. For facility location it is NP-complete (Goemans–Skutella, per the chapter notes).

The fix is to keep the core property, which is what prevents secession, and relax budget balance.

DefinitionDefinition 15.7 — $\gamma$ -approximate core

$\alpha$ is in the $\gamma$ -core if:

$\gamma$ -budget balance: $\gamma\, c(A) \le \sum_{j} \alpha_j \le c(A)$ ;
Core property: $\sum_{j \in S} \alpha_j \le c(S)$ for every $S$ .

ExampleThe three-facility game of Example 15.4

$(3.5, 2.5, 1.5)$ is in the $\tfrac{7.5}{8}$ -core: it sums to $7.5$ and meets all pair and singleton constraints. The averaging argument shows the $\gamma$ -core is empty for every $\gamma > 7.5/8$ .

TheoremTheorem 15.8 — approximate Bondareva–Shapley

For $\gamma \le 1$ , $(A,c)$ has a nonempty $\gamma$ -core iff for every balanced $\lambda$ , $\sum_S \lambda_S c(S) \ge \gamma\, c(A)$ .

ProofSame duality, relaxed threshold

The key step: by LP duality, the $\gamma$ -core is nonempty iff the value of (15.2), which equals that of (15.1), is at least $\gamma\,c(A)$ . An optimal $\alpha$ for (15.1) then satisfies the core constraints and sums to between $\gamma c(A)$ and $c(A)$ .

∎

CorollaryCorollary 15.9 — best $\gamma$ = integrality gap

If $c$ is subadditive ( $c(S_1 \cup S_2) \le c(S_1) + c(S_2)$ for disjoint $S_1, S_2$ ), then the largest $\gamma$ with a nonempty $\gamma$ -core equals the integrality gap of LP (15.2).

DerivationWhy subadditivity pins the integral optimum at

c(A)

Step 1: Integral feasible points of (15.2) are partitions. With $\lambda_S \in \{0,1\}$ and each $j$ covered exactly once, the chosen sets partition $A$ .

Step 2: Subadditivity says partitions never beat the grand coalition. $\sum_{\text{parts}} c(S) \ge c(A)$ , with equality at the partition $\{A\}$ . So the integral optimum is exactly $c(A)$ .

Step 3: Compare. By Theorem 15.8 the best $\gamma$ is $\mathrm{LP}(15.2)/c(A) = \mathrm{LP}/\mathrm{IP}$ , the integrality gap written as a ratio $\le 1$ .

Facility location: the core LP is the standard LP dual

For set cover, vertex cover and facility location, the exponential LP (15.2) is equivalent to the standard polynomial-size LP. Corollary 15.9 then becomes a statement about a well-studied integrality gap. For facility location, let $x_i$ indicate that facility $i$ is open and $y_{ij}$ that $j$ connects to $i$ :

\min \sum_{i\in F} f_i x_i + \sum_{i\in F}\sum_{j\in A} d_{ij} y_{ij} \quad\text{s.t.}\quad \sum_{i \in F} y_{ij} \ge 1\ \forall j,\quad x_i \ge y_{ij}\ \forall i,j,\quad x_i, y_{ij} \in \{0,1\}. \tag{15.3}

Relax to $x_i, y_{ij} \ge 0$ . The dual is

\max \sum_{j \in A} \alpha_j \quad\text{s.t.}\quad \beta_{ij} \ge \alpha_j - d_{ij},\quad \sum_{j \in A} \beta_{ij} \le f_i, \quad \alpha_j, \beta_{ij} \ge 0. \tag{15.4}

WLOG $\beta_{ij} = \max(0, \alpha_j - d_{ij})$ , so a dual solution is just $\alpha$ .

IntuitionReading the dual

$\alpha_j$ is city $j$ ‘s payment. $\beta_{ij}$ is the part of it left over after paying the trip to facility $i$ , which counts as $j$ ‘s contribution to opening $i$ . The constraint $\sum_j \beta_{ij} \le f_i$ says no facility is overpaid.

PropositionProposition 15.10 — dual feasibility ⇒ core property

For any feasible $(\alpha, \beta)$ of (15.4), $\alpha$ satisfies the core property of the facility location game.

ProofCharge each coalition’s optimal solution facility by facility

Step 1: One facility, any group. For facility $i$ and $R \subseteq A$ , add $\beta_{ij} \ge \alpha_j - d_{ij}$ over $j \in R$ and use $\sum_j \beta_{ij} \le f_i$ : $\sum_{j \in R} \alpha_j \le f_i + \sum_{j \in R} d_{ij}. \tag{15.5}$ Any group can collectively afford at most what it would cost to open $i$ and connect everyone to it.

Step 2: Decompose an optimal solution for $S$ . Let $i_1,\dots,i_k$ be its open facilities and $R_\ell$ the cities served by $i_\ell$ . Summing (15.5) over the pairs $(i_\ell, R_\ell)$ gives $\sum_{j \in S} \alpha_j \le c(S)$ .

∎

ImportantConsequence

The value of (15.4) equals the LP relaxation of (15.3), and also equals (15.1) and (15.2). The integral optimum of (15.3) is $c(A)$ . So the best budget-balance factor of any core-respecting allocation is the integrality gap of the standard facility location LP, known to lie between $1/1.52$ and $1/1.463$ .

Core of NTU games

DefinitionNTU core

$\alpha \in C(A)$ is in the core if there is no nonempty $S$ and $x \in C(S)$ with $x_j < \alpha_j$ for all $j \in S$ . With TU this reduces to Definition 15.3.

The support of $\lambda$ is $\{S : \lambda_S > 0\}$ .

TheoremTheorem 15.11 — Scarf

Suppose that for every balanced $\lambda$ and every $x \in \mathbb{R}^A$ : if $x|_S \in C(S)$ for every $S$ in the support of $\lambda$ , then $x \in C(A)$ . Then $(A, C)$ has a nonempty core.

NoteProof beyond scope; sufficient only

The chapter omits the proof. It adapts Lemke–Howson (see the Nash-computation chapter) and is exponential in $|A|$ in the worst case. Unlike Bondareva–Shapley, the condition is sufficient but not necessary. It also gives no polynomial algorithm, whereas the Bondareva–Shapley LP yields a core point in polynomial time given a suitable representation of $c$ (a separation oracle for (15.1), or a Proposition-15.10-style reduction).

Group-strategyproof mechanisms from cross-monotonic schemes

The problem. When demand is price-sensitive, the provider doesn’t know who wants service at what price. So it runs an auction: agents bid, and the mechanism picks who is served and what they pay. We want truthfulness robust to coalitions, not just individuals.

Setup. Agent $i$ has value $u_i$ for service. Utility is $u_i q_i - x_i$ , where $q_i \in \{0,1\}$ indicates service and $x_i$ is the payment. A cost-sharing mechanism maps bids $b$ to a served set $Q(b) \subseteq A$ and payments $p(b) \in \mathbb{R}^n$ .

Axiom	Statement	What it rules out
NPT (no positive transfer)	$p_i \ge 0$	paying agents to participate
VP (voluntary participation)	$p_i = 0$ for $i \notin Q$ ; $p_i \le b_i$ for $i \in Q$	charging the unserved, or charging above the bid
CS (consumer sovereignty)	some bid $b_i^*$ guarantees service whatever others bid	an agent being locked out regardless of willingness to pay

A mechanism is $\gamma$ -budget-balanced if $\gamma\,c(Q) \le \sum_{i \in Q} x_i \le c(Q)$ .

DefinitionGroup strategyproofness

Let $u$ be true values and $u'$ bids with $u'_i = u_i$ for $i \notin S$ , and let $(Q,p), (Q',p')$ be the outcomes. The mechanism is group strategyproof if, whenever $u_i q'_i - p'_i \ge u_i q_i - p_i$ for all $i \in S$ , equality holds for all $i \in S$ . That is, no coalition can misreport so that every member is at least as happy and one is strictly happier.

NoteNo side payments

Coalition members can’t pay each other. Collusion with side payments is a different model (Goldberg–Hartline).

DefinitionDefinition 15.12 — cost-sharing scheme

A function $\xi : A \times 2^A \to \mathbb{R}$ with $\xi(i,S) = 0$ for $i \notin S$ . It gives a cost allocation for every coalition, not just $A$ . It is $\gamma$ -budget-balanced if $\gamma\,c(S) \le \sum_{i\in S} \xi(i,S) \le c(S)$ for all $S$ .

DefinitionDefinition 15.13 — cross-monotonicity

$\xi$ is cross-monotone if $\xi(i, S) \ge \xi(i, S \cup T)$ for all $S, T \subseteq A$ and $i \in S$ .

IntuitionNobody is penalized when the group grows

Adding more customers can only lower or keep your share. This is what makes serving more people attractive to everyone already served.

PropositionProposition 15.14 — cross-monotone ⇒ approximate core

If $\xi$ is $\gamma$ -budget-balanced and cross-monotone, then $\xi(\cdot,A)$ is in the $\gamma$ -core.

ProofShrink to

S

, then use budget balance on

S

Budget balance on $A$ is given. For the core property,

\sum_{i \in S} \xi(i,A) \overset{(a)}{\le} \sum_{i\in S} \xi(i,S) \overset{(b)}{\le} c(S).

(a) Cross-monotonicity with $A = S \cup (A\setminus S)$ .
(b) Upper half of $\gamma$ -budget balance on $S$ .

∎

WarningThe core is about one allocation; cross-monotonicity is about all of them

A core allocation only constrains shares at $A$ . A mechanism that may serve any subset needs shares for every subset, consistent with each other. That is why the core alone doesn’t give a mechanism. Cross-monotonicity is strictly stronger; see Limits of cross-monotonicity: the probabilistic method.

Moulin’s mechanism

AlgorithmMechanism $M_\xi$ (Fig. 15.2)

$S \leftarrow A$ .
Repeat: $S \leftarrow \{ i \in S : b_i \ge \xi(i,S) \}$ , until $b_i \ge \xi(i,S)$ for all $i \in S$ .
Return $Q = S$ , $p_i = \xi(i,S)$ .

IntuitionPosted prices that only fall

Offer everyone their share at the current set. Anyone who won’t pay drops out. By cross-monotonicity, the survivors’ shares can only rise, so repeat. This is an ascending-price auction run backwards on the set.

PropositionProposition 15.15 — $M_\xi$ finds the unique maximal affordable set

For cross-monotone $\xi$ and bids $b_i \ge 0$ , there is a unique maximal $S$ with $b_i \ge \xi(i,S)$ for all $i \in S$ , and $M_\xi$ returns it.

ProofAffordable sets are closed under union

Step 1: Union of affordable sets is affordable. If $S_1, S_2$ are both affordable, then for $i \in S_1$ , $b_i \ge \xi(i,S_1) \ge \xi(i,S_1 \cup S_2)$ by cross-monotonicity, and similarly for $i\in S_2$ . So two distinct maximal sets can’t exist.

Step 2: $M_\xi$ never drops a member of $S^*$ . Take the first step at which some $i \in S^*$ is removed from the current $S \supseteq S^*$ . Then $b_i < \xi(i,S) \le \xi(i,S^*)$ by cross-monotonicity, contradicting $i \in S^*$ .

Step 3: Conclude. So $Q \supseteq S^*$ . $Q$ is affordable at termination, and $S^*$ is maximal, so $Q = S^*$ .

∎

TheoremTheorem 15.16 — Moulin

If $\xi$ is $\gamma$ -budget-balanced and cross-monotone, then $M_\xi$ is group strategyproof and $\gamma$ -budget-balanced.

ProofOverbidding can’t help; underbidding only raises prices

Budget balance is immediate, since payments are $\xi(\cdot,Q)$ . Suppose a coalition $T$ benefits by bidding $u'$ . Split $T$ into $T^+$ (bid above value) and $T^-$ (bid at or below value).

Step 1: WLOG $T^+ = \emptyset$ . Lower the bids of $T^+$ agents from $u'_i$ to $u_i$ one at a time. If some step changes the outcome, then by Proposition 15.15 agent $i$ wins at bid $u'_i$ and loses at $u_i$ , so $u'_i \ge \xi(i,S_i) > u_i$ , where $S_i$ is the winning set. Then $i$ pays more than her value under the collusive bids, so her utility is negative. Truthful play gives her at least $0$ by VP, contradicting “every member is at least as happy.” So each lowering leaves the outcome unchanged.

Step 2: Lower bids shrink the winning set. With all bids weakly lower, any set affordable under $u'$ is affordable under $u$ . By maximality (Proposition 15.15), $S' \subseteq S$ .

The key step: by cross-monotonicity, $S' \subseteq S$ means every agent served under $u'$ pays at least as much as under $u$ . Agents dropped from service go from $u_i - \xi(i,S) \ge 0$ to $0$ . So no one in $T$ is strictly happier.

∎

NoteThe converse fails

Some cost functions admit a group-strategyproof mechanism but no cross-monotonic scheme, unless $c$ is submodular (Moulin proves the converse there). Semi-cross-monotonicity gives a partial characterization. A full characterization is open.

RemarkSame argument as the multicast SH pruning

Proposition 15.15 is the “legal elimination orderings concatenate” argument from the Shapley multicast mechanism: affordable sets are closed under union, so the pruning order doesn’t matter.

Building cross-monotonic shares: the primal-dual schema

Section 15.2 found core allocations by solving an LP, where cost shares are dual variables. Primal-dual algorithms produce dual variables as a by-product of approximating the primal. The idea is to arrange that those duals are also cross-monotone.

AlgorithmThe primal-dual schema (generic)

Relax the problem to a primal LP. Its dual lower-bounds OPT.
Start all dual variables at $0$ and raise them gradually.
When a dual constraint goes tight, it names a primal object the dual has “paid for”. Add it to the primal solution and freeze the duals in that constraint.
Continue with the other duals until the primal is complete.
Analysis: show that primal and dual values are close, so both are near optimal.

A postprocessing step often reduces primal cost without touching the duals.

Submodular games: the schema works unmodified

DefinitionDefinition 15.17 — submodular (concave) game

$c(S) + c(T) \ge c(S \cup T) + c(S \cap T)$ for all $S, T \subseteq A$ . Equivalently, marginal cost is decreasing: for $S \subset A \setminus\{i,j\}$ , $c(S \cup \{i\}) - c(S) \ge c(S \cup \{i,j\}) - c(S \cup \{j\}).$

Multicast cost sharing (see distributed-algorithmic-mechanism-design) is a submodular game.

The roles flip. Take (15.2) as primal and (15.1) as dual. By submodularity the primal is trivial, with optimum $c(A)$ . The dual (15.1) is the interesting one: its optimal solutions are exactly the core. For feasible $\alpha$ , call $S$ tight if $\sum_{j\in S}\alpha_j = c(S)$ .

LemmaLemma 15.18 — tight sets are closed under union

If $\alpha$ is feasible for (15.1) and $S_1, S_2$ are tight, then $S_1 \cup S_2$ is tight.

ProofSubmodularity plus feasibility on the intersection

c(S_1 \cup S_2) \overset{(a)}{\le} c(S_1) + c(S_2) - c(S_1 \cap S_2) \overset{(b)}{\le} \sum_{S_1}\alpha_j + \sum_{S_2}\alpha_j - \sum_{S_1\cap S_2}\alpha_j = \sum_{S_1 \cup S_2} \alpha_j.

(a) Submodularity.
(b) Tightness of $S_1, S_2$ (equalities), and feasibility on $S_1 \cap S_2$ , which enters with a minus sign.

Feasibility gives the reverse inequality, so there is equality.

∎

CorollaryCorollary 15.19 — unique maximal tight set

The union of all tight sets is the unique maximal tight set.

AlgorithmSubmodularCostShare (Fig. 15.3)

Input: submodular $(A,c)$ and served set $T \subseteq A$ .

$\alpha_j \leftarrow 0$ for all $j$ ; $F \leftarrow \emptyset$ .
While $T \setminus F \ne \emptyset$ : raise all $\alpha_j$ , $j \in T\setminus F$ , at the same rate until a new set goes tight. Set $F \leftarrow$ the maximal tight set.
Output $\alpha_j$ for $j \in T$ .

Properties, all by Lemma 15.18:

the maximal tight set only grows, so a frozen agent stays frozen;
hence $\alpha_j$ is the time at which $j$ first freezes;
$\alpha$ never becomes infeasible, and the loop stops only when $T$ is tight. So the shares are budget-balanced and in the core (for the game restricted to $T$ ).

TheoremTheorem 15.20 — the Dutta–Ray shares are cross-monotone

The cost-sharing scheme defined by SubmodularCostShare is cross-monotone.

ProofRun both instances in lockstep; frozen sets nest

Step 1: Set up. Take $T_1 \subset T_2$ and run both at once. It suffices that at every time $t$ , the frozen sets satisfy $F_1 \subseteq F_2$ . Then each $i\in T_1$ freezes no later in the $T_2$ -run, so $\xi(i,T_2) \le \xi(i,T_1)$ . Write $\alpha^1, \alpha^2$ for the duals at time $t$ .

Step 2: Show $F_1 \cup F_2$ is tight for $\alpha^2$ .

c(F_1 \cup F_2) \overset{(a)}{\le} c(F_1) + c(F_2) - c(F_1\cap F_2) \overset{(b)}{\le} \sum_{F_1}\alpha^1_i + \sum_{F_2}\alpha^2_i - \sum_{F_1\cap F_2}\alpha^1_i = \sum_{F_1\setminus F_2}\alpha^1_i + \sum_{F_2}\alpha^2_i \overset{(c)}{\le} \sum_{F_1 \cup F_2} \alpha^2_i.

(a) Submodularity.
(b) Tightness of $F_\ell$ for $\alpha^\ell$ , and feasibility of $\alpha^1$ on $F_1 \cap F_2$ .
(c) For $i \in F_1 \setminus F_2$ : $i \in T_2$ and is still unfrozen in the $T_2$ -run, so $\alpha^2_i = t \ge \alpha^1_i$ .

The key step: $F_2$ is the maximal tight set for $\alpha^2$ , so $F_1 \cup F_2 = F_2$ , that is, $F_1 \subseteq F_2$ .

∎

Facility location: why the standard algorithm fails, and ghost duals

Standard primal-dual. Call $\max(0, \alpha_j - d_{ij})$ city $j$ ‘s contribution to facility $i$ . Facility $i$ is tight if $\sum_j \max(0,\alpha_j - d_{ij}) = f_i$ . Raise all $\alpha_j$ from $0$ until one of two events:

a facility goes tight: open it and freeze every city contributing positively to it;
a city $j$ reaches an already open facility, $\alpha_j = d_{ij}$ : freeze $j$ .

Continue until everyone is frozen.

ExampleFig. 15.1 under the standard algorithm

All three cities. At $t=2$ , $b$ and $c$ each contribute $1$ to facility 2 (cost $2$ ). It opens, and $b, c$ freeze at $2$ . City $a$ keeps rising alone and reaches $4$ , where it pays $2$ to facility 1 by itself. Result: $(4,2,2)$ , which is budget-balanced and in the core.
Only $a, b$ . Both rise to $3$ . Then $a$ and $b$ each give $1$ to facility 1 (tight), and $b$ gives $2$ to facility 2 (tight). Result: $\alpha_a = 3$ .

So $\xi(a,\{a,b\}) = 3 < 4 = \xi(a,\{a,b,c\})$ . Cross-monotonicity fails.

NoteBudget balance of the standard version

The chapter notes that, with a postprocessing step closing some facilities, the primal cost is always at most $3\times$ the shares. So the standard shares are $\tfrac13$ -budget-balanced. They just aren’t cross-monotone.

WarningWhy it fails: freezing withdraws help

Without $c$ , city $b$ helps $a$ pay for facility 1. With $c$ present, $c$ helps $b$ open facility 2. Then $b$ freezes and stops helping $a$ , so $a$ pays more. Adding an agent hurt an existing one through a chain of withdrawn contributions.

The fix: ghost duals. Let a frozen city keep growing a ghost share $\alpha'_j$ . It doesn’t count toward what $j$ pays, but it still contributes to opening facilities. Help is never withdrawn.

AlgorithmFLCostShare (Fig. 15.4, Pál–Tardos)

Input: facility location instance and served set $T$ .

$\alpha_j, \alpha'_j \leftarrow 0$ ; $F \leftarrow \emptyset$ (frozen cities).
While $T \setminus F \ne \emptyset$ $T ∖ F \neq = \emptyset$ : raise $\alpha_j$ $α_{j}$ for $j \in T \setminus F$ $j \in T ∖ F$ and $\alpha'_j$ $α_{j}^{'}$ for all $j \in T$ $j \in T$ at the same rate until:
- an unopened facility $i$ has $\sum_{j\in T}\max(0, \alpha'_j - d_{ij}) = f_i$ : open $i$ and add every city contributing positively to it to $F$ ; or
- an open facility $i$ and city $j$ have $\alpha'_j = d_{ij}$ : add $j$ to $F$ .

ExampleFig. 15.1 with ghosts

At $t=2$ , facility 2 opens and $b, c$ freeze at real share $2$ , but their ghosts keep growing. At $t=3$ , facility 1 gets $1$ from $a$ and $1$ from $b$ ‘s ghost, so it is tight and $a$ freezes at $3$ . Result: $(3,2,2)$ , matching $a$ ‘s share in $\{a,b\}$ .

NoteCross-monotonicity left as an exercise

The chapter calls cross-monotonicity of FLCostShare “an easy exercise.” The natural reason: ghost shares make every city’s growth independent of who is frozen, so adding cities only adds contributions and makes facilities open no later.

WarningGhosts could wreck budget balance

Ghosts pay toward opening facilities but aren’t collected as shares. In general that can leave the real shares recovering too little of the primal cost (the chapter points to Exercise 15.3). For facility location it doesn’t happen:

TheoremTheorem 15.21 — FLCostShare is $\tfrac13$ -budget-balanced

The shares computed by FLCostShare are $\tfrac13$ -budget-balanced.

ProofPrune open facilities greedily, then charge disjoint balls

It suffices to build a solution costing at most $3\sum_{j\in T}\alpha_j$ .

Step 1: Postprocess. Let $t_i$ be the time facility $i$ opens. Scan open facilities in increasing $t_i$ . Close $i$ if some earlier kept facility is within $2t_i$ of it; otherwise keep it. Let $F'$ be the kept set, and connect each city to its nearest facility in $F'$ .

Step 2: Balls around kept facilities are disjoint. Let $S_i = \{j : d_{ij} \le t_i\}$ . If $j \in S_i \cap S_{i'}$ with $i, i' \in F'$ , then $d_{ii'} \le t_i + t_{i'} \le 2\max(t_i,t_{i'})$ , so the later one would have been closed.

Step 3: Ghosts at time $t_i$ pay exactly for $i$ . Every ghost equals $t_i$ when $i$ opens, so $\sum_{j \in S_i}(t_i - d_{ij}) = f_i$ . If every $j \in S_i$ has $\alpha_j \ge t_i/3$ , then

\sum_{j\in S_i}\alpha_j \ge \tfrac13 \sum_{j \in S_i} t_i = \tfrac13\Big(f_i + \sum_{j \in S_i} d_{ij}\Big),

which covers a third of opening $i$ and connecting $S_i$ to it (and hence to its nearest kept facility).

Step 4 (the key step): $\alpha_j \ge t_i/3$ for $j\in S_i$ . Suppose $\alpha_j < t_i/3$ . Let $i_1$ be the facility whose event froze $j$ , so $t_{i_1} = \alpha_j$ and $d_{i_1 j} \le \alpha_j$ . Some $i_2 \in F'$ lies within $2t_{i_1}$ of $i_1$ ( $i_2 = i_1$ if $i_1$ was kept). Then $d_{i i_2} \le d_{ij} + d_{i_1 j} + 2t_{i_1} \le t_i + 3\alpha_j < 2t_i.$ Also $t_{i_2} \le t_{i_1} < t_i$ , so $i_2$ precedes $i$ , and $i$ should have been closed. Contradiction.

Step 5: Cities outside every ball. For $j \notin \bigcup_{i\in F'}S_i$ , let $i$ be the facility with $t_i = \alpha_j$ (so $d_{ij} \le \alpha_j$ ). Some $i' \in F'$ is within $2t_i$ of $i$ . So $j$ ‘s connection cost is at most $d_{ij} + 2t_i \le 3\alpha_j$ .

Step 6: Sum. The balls are disjoint (Step 2), so charges don’t overlap. Every opening and connection cost is covered at a rate of at least $1/3$ .

∎

NoteOnly the lower half is proved

The chapter proves $\sum \alpha_j \ge \tfrac13 c(T)$ . The upper half, $\sum\alpha_j \le c(T)$ (in fact the core property), is not argued explicitly. It follows if the real $\alpha$ is feasible for (15.4), by Proposition 15.10. That holds because $\alpha \le \alpha'$ , and a city’s real share stops growing once it contributes to, or reaches, an open facility. This justification is mine, not the chapter’s.

RemarkAlgorithms from cost sharing

The postprocessing here is Mettu–Plaxton’s algorithm. The cost-sharing view gives it a new primal-dual interpretation.

Limits of cross-monotonicity: the probabilistic method

Cross-monotone ⇒ core (Proposition 15.14). So integrality-gap instances already bound the budget-balance factor, and for facility location that bound is about $1/1.463$ . But cross-monotonicity is strictly stronger, so it can be bounded more tightly.

AlgorithmThe technique (Immorlica et al.)

Fix an arbitrary cross-monotone $\xi$ .
Build an instance and pick a random coalition $S$ from a designed distribution.
Show $\mathbb{E}[\text{recovered}]/c(S)$ is small, so some realization of $S$ is bad.
To bound recovered cost, use cross-monotonicity: bound $\xi(i,S)$ by $\xi(i,T_i)$ for a substructure $T_i \subseteq S$ .
Design the distribution so that, for every substructure $T$ , every $i \in T$ is equally likely to be the one with $T_i = T$ . Then $\mathbb{E}[\xi(i,T_i)] \le c(T_i)/|T_i|$ by budget balance on $T_i$ .

LemmaLemma 15.22 — a gadget recovering only a third

Instance $I$ : cities $a_1,\dots,a_m$ and $a'_1,\dots,a'_k$ ; facilities $f_1,\dots,f_m$ , each with cost $3$ . $d(f_i,a_i) = 1$ and $d(f_i, a'_j) = 1$ for all $i, j$ ; other distances by the metric. If $m = \omega(k)$ and $k \to \infty$ , then $\mathrm{OPT}(I) = 3m + o(m)$ .

ProofOpening more facilities never pays

Step 1: Upper bound. Open only $f_1$ : cost $3 + 1 + k + 3(m-1) = 3m + k + 1 = 3m + o(m)$ . Each $a_i$ with $i\ne 1$ travels $a_i \to f_i \to a'_1 \to f_1$ , a distance of $3$ .

Step 2: Any solution with $f$ open facilities. The first facility serves $k+1$ cities at distance $1$ . Each additional facility adds only one more distance-1 city (its own $a_i$ ). So $k + f$ cities pay $1$ and the other $m - f$ pay $3$ . Total: $3f + (k+f) + 3(m-f) = 3m + k + f \ge 3m + k + 1.$

∎

TheoremTheorem 15.23 — $\tfrac13$ is the limit for facility location

Every cross-monotonic cost-sharing scheme for facility location is at most $\tfrac13$ -budget-balanced.

ProofRandom copy of the gadget; symmetry caps each share

Step 1: The big instance. Groups $A_1,\dots,A_k$ of $m$ cities each, with $m = \omega(k)$ and $k = \omega(1)$ . For every transversal $B$ (one city from each $A_i$ ) there is a facility $f_B$ of cost $3$ at distance $1$ from each city of $B$ , and distance $3$ from cities outside $B$ .

Step 2: Random coalition. Pick $i \in \{1..k\}$ uniformly. For each $j \ne i$ , pick $a_j \in A_j$ uniformly. Let $T = \{a_j : j\ne i\}$ and $S = A_i \cup T$ . $S$ is essentially the gadget of Lemma 15.22, so $c(S) = 3m + o(m)$ .

Step 3: Split and shrink by cross-monotonicity.

\mathbb{E}\Big[\sum_{a \in S}\xi(a,S)\Big] = \mathbb{E}\Big[\sum_{a \in A_i}\xi(a,S)\Big] + \mathbb{E}\Big[\sum_{j\ne i}\xi(a_j,S)\Big] \overset{(a)}{\le} \mathbb{E}\Big[\sum_{a\in A_i}\xi(a,\{a\}\cup T)\Big] + \mathbb{E}\Big[\sum_{j \ne i}\xi(a_j,T)\Big].

(a) Cross-monotonicity: $\{a\}\cup T \subseteq S$ and $T \subseteq S$ .

Step 4: Second term. $T$ can be served for $3 + (k-1)$ , since one facility $f_B$ with $B\supseteq T$ reaches all of it. By budget balance the term is at most $k+2$ .

Step 5 (the key step): symmetry for the first term. The first term is $m\,\mathbb{E}[\xi(a, \{a\}\cup T)]$ for a uniform $a \in A_i$ . Equivalently: pick $a_j$ from every $A_j$ , then pick $i$ uniformly and set $a = a_i$ . Given the transversal $\{a_1..a_k\}$ , $a$ is a uniform member of it, so

\mathbb{E}[\xi(a,\{a\}\cup T)] = \frac1k \sum_{j=1}^k \xi(a_j,\{a_1,\dots,a_k\}) \le \frac{k+3}{k},

by budget balance, since $\{a_1..a_k\}$ costs $k+3$ .

Step 6: Assemble.

\mathbb{E}\Big[\sum_{a\in S}\xi(a,S)\Big] \le m\,\frac{k+3}{k} + (k+2) = m + o(m), \tag{15.6}

using $m/k = o(m)$ and $k = o(m)$ . Against $c(S) = 3m + o(m)$ , the recovered fraction tends to $\tfrac13$ . So some $S$ achieves at most that.

∎

ImportantCross-monotonicity is strictly stronger than the core

For facility location, core allocations can recover at least $1/1.52$ of the cost. Cross-monotone ones can recover at most $1/3$ , and FLCostShare achieves exactly $1/3$ . The gap is the price of having consistent shares for every subset, which is what Moulin’s mechanism needs.

The Shapley value

The problem. The core is often empty (useless) or large (needs a tie-breaker). We want a rule that returns one allocation for every game.

DefinitionIncremental cost sharing

Order the agents $a_1,\dots,a_n$ and charge each her marginal cost on arrival: $a_1$ pays $c(\{a_1\})$ , $a_2$ pays $c(\{a_1,a_2\}) - c(\{a_1\})$ , and so on. This is budget-balanced by telescoping.

WarningWhy a fixed order fails

It isn’t anonymous: the same agent pays different amounts depending on where she happens to be placed. Early arrivals pay stand-alone costs, and late arrivals ride on economies of scale.

The fix is to average over all $n!$ orders. The probability that exactly $S$ (with $|S| = s$ , $i \notin S$ ) precedes $i$ is $s!(n-1-s)!/n!$ .

FormulaShapley value

\phi_i(c) = \sum_{s=0}^{n-1} \frac{s!\,(n-1-s)!}{n!} \sum_{\substack{S \subseteq A\setminus\{i\}\\ |S| = s}} \big(c(S\cup\{i\}) - c(S)\big)

IntuitionExpected marginal cost

Let customers arrive in a uniformly random order. Each pays what her arrival adds to the bill. $\phi_i$ is her expected bill.

ExampleExample 15.24 — Shapley in Fig. 15.1

Weights: $\tfrac13$ for $S=\emptyset$ , $\tfrac16$ for each singleton, $\tfrac13$ for the pair.

Agent	$\emptyset$	first other	second other	both others	$\phi$
$a$	4	$+b$ : 3	$+c$ : 4	4	$23/6$
$b$	3	$+a$ : 2	$+c$ : 1	1	$11/6$
$c$	3	$+a$ : 3	$+b$ : 1	2	$7/3$

The shares sum to $48/6 = 8$ .

WarningShapley need not be in the core, even when the core is nonempty

$\phi_b + \phi_c = 25/6 > 4 = c(\{b,c\})$ , so $\{b,c\}$ would rather secede. Yet $(4,2,2)$ shows the core is nonempty. Fairness and stability can conflict.

TheoremShapley on submodular games

For submodular $c$ , every incremental sharing is in the core. So is the Shapley value, a convex combination of incremental sharings. Moreover, Shapley is cross-monotone there, so it plugs into Moulin’s mechanism. This is the SH multicast mechanism of distributed-algorithmic-mechanism-design.

NoteAsserted / exercise

“Incremental ⇒ core” for submodular games is stated as known (Shapley 1953). Cross-monotonicity is Exercise 15.2.

RemarkComputation

The formula touches exponentially many values of $c$ , so it is hard in general. For submodular $c$ , random sampling of orders approximates it to any accuracy (Mossel–Saberi).

Axiomatic characterization

DefinitionDefinition 15.25 — axioms for a value

A value maps each cost function $c$ on a fixed $A$ to $\phi(c) \in \mathbb{R}^n_{\ge 0}$ .

Anonymity: for any permutation $\pi$ , $\phi_{\pi i}(\pi(c)) = \phi_i(c)$ .
Dummy: if $c(S) = c(S\cup\{i\})$ for all $S \subset A\setminus\{i\}$ , then $\phi_i(c) = 0$ .
Additivity: $\phi(c_1 + c_2) = \phi(c_1) + \phi(c_2)$ .

Axiom	What it rules out
Anonymity	incremental sharing with a fixed order; any favouritism by name
Dummy	charging someone who never adds cost
Additivity	sharing a bill differently depending on whether it’s itemized: splitting $c_1 + c_2$ must equal splitting each part and adding

TheoremTheorem 15.26 — Shapley

The Shapley value is the unique value satisfying anonymity, dummy and additivity.

NoteProof omitted in the chapter

This is a classic of the axiomatic method: find, or rule out, the rules satisfying a set of axioms. Other examples are Nash bargaining (below), Arrow’s impossibility theorem, and the axiomatizations of PageRank.

RemarkThe multicast SH rule, read through the axioms

The multicast cost is a sum of per-link costs. On a single link, the agents not downstream are dummies and the downstream ones are symmetric, so the link’s cost is split equally among downstream agents. Additivity sums over links. That is exactly the SH rule. (This link is my gloss, not in the chapter.)

The Nash bargaining solution

The problem. Two parties must agree on one outcome, as in wage or trade negotiations. Either can walk away, which produces a disagreement outcome.

DefinitionTwo-player bargaining game

A set $X \subseteq \mathbb{R}^2$ of achievable utility pairs and a disagreement point $d \in X$ . Assumptions:

$d = (0,0)$ WLOG: shifting a player’s utility doesn’t change her preferences;
$X$ is convex (WLOG if lotteries over outcomes are allowed) and compact;
some point of $X$ is strictly positive in both coordinates, so both sides have a reason to negotiate.

RemarkRelation to NTU games

An NTU cooperative game extends bargaining. Bargaining specifies only what individuals get by leaving ( $d$ ). An NTU game also specifies what every group can get.

DefinitionDefinition 15.27 — axioms for a bargaining solution

A solution picks $\phi(X) \in X$ .

Pareto optimality: no $p \in X$ with $p > \phi(X)$ coordinatewise.
Symmetry: if $X$ is symmetric, then $\phi(X) = (u,u)$ .
Scale independence: rescaling player $i$ ‘s utilities by $\lambda_i$ rescales $\phi(X)_i$ by $\lambda_i$ .
Independence of irrelevant alternatives (IIA): if $Y \subset X$ and $\phi(X) \in Y$ , then $\phi(Y) = \phi(X)$ .

TheoremTheorem 15.28 — Nash

There is a unique solution satisfying all four axioms. It picks the point $(u_1,u_2) \in X$ maximizing $u_1 u_2$ .

NoteProof omitted

The chapter calls the proof simple and omits it. For more than two players, see Moulin (1988).

IntuitionWhy the product

Scale independence rules out adding utilities, because rescaling one player would tilt a sum. It also rules out the minimum, which isn’t scale-invariant either. A product is the aggregate whose maximizer survives independent rescaling of each coordinate.

Collective utility functions aggregate individual utilities into one number:

Name	Aggregate	Where it shows up
utilitarian	$\sum_i u_i$	nearly all of combinatorial optimization
egalitarian	$\min_i u_i$	the Santa Claus scheduling problem
Nash	$\prod_i u_i$	Nash bargaining; Eisenberg–Gale; Kelly’s proportional allocation

Dual-first thinking yields algorithms. The Theorem 15.21 postprocessing is Mettu–Plaxton’s algorithm with a new primal-dual reading. The search for cross-monotone shares for Steiner forest gave a new 2-approximation and a stronger LP.
LP (15.2) is at least as strong as the standard relaxation, and for some problems strictly stronger (apparently Steiner tree). Relaxing (15.2) into something polynomially solvable is a route to better relaxations. The Steiner tree case connects to the open bidirected-LP gap.
Axioms for heuristics (e.g. PageRank) and non-utilitarian objectives (egalitarian, Nash) are sources of new algorithmic problems.

Quick reference

Object	Statement	Note
TU / NTU game	$v : 2^A \to \mathbb{R}$ / $V(S) \subseteq \mathbb{R}^S$	cost sharing: $v = -c$
Facility location $c(S)$	$\min_{F'}\{\sum_{F'} f_i + \sum_{S}\min_{F'} d_{ij}\}$	metric $d$
Core (Def 15.3)	$\sum_A \alpha = c(A)$ ; $\sum_S \alpha \le c(S)$	may be empty or non-unique
Balanced weights (Def 15.5)	$\lambda \ge 0$ , $\sum_{S\ni j}\lambda_S = 1$	fractional partition
Bondareva–Shapley (Thm 15.6)	core $\ne\emptyset \iff \sum \lambda_S c(S) \ge c(A)$ for all balanced $\lambda$	LP duality (15.1)↔(15.2)
$\gamma$ -core (Def 15.7)	$\gamma c(A) \le \sum \alpha \le c(A)$ + core property
Thm 15.8	$\gamma$ -core $\ne \emptyset \iff \sum\lambda_S c(S) \ge \gamma c(A)$
Cor 15.9	subadditive ⇒ best $\gamma$ = integrality gap of (15.2)	integral (15.2) = partitions
Prop 15.10	feasible dual of FL LP ⇒ core property	FL: (15.2) ≡ standard LP
FL core factor	in $[1/1.52,\ 1/1.463]$	integrality gap of (15.3)
Scarf (Thm 15.11)	balancedness condition ⇒ NTU core $\ne\emptyset$	sufficient only; Lemke–Howson-style, exponential
NPT / VP / CS	$p\ge0$ ; unserved pay 0, served pay $\le$ bid; some bid guarantees service
Group strategyproof	no coalition misreport weakly helps all, strictly helps one	no side payments
Cross-monotone (Def 15.13)	$\xi(i,S) \ge \xi(i,S\cup T)$
Prop 15.14	cross-monotone + $\gamma$ -BB ⇒ $\xi(\cdot,A)$ in $\gamma$ -core
Moulin $M_\xi$	drop $i$ with $b_i < \xi(i,S)$ until stable
Prop 15.15	$M_\xi$ returns the unique maximal affordable set	affordable sets closed under $\cup$
Moulin (Thm 15.16)	cross-monotone $\gamma$ -BB $\xi$ ⇒ $M_\xi$ GSP, $\gamma$ -BB	converse false unless submodular
Submodular (Def 15.17)	$c(S)+c(T) \ge c(S\cup T) + c(S\cap T)$	decreasing marginal cost
Lemma 15.18	tight sets closed under $\cup$	⇒ unique maximal tight set
Thm 15.20	SubmodularCostShare is cross-monotone, BB, in core	$\alpha_j$ = freeze time
Standard FL primal-dual	$\tfrac13$ -BB but not cross-monotone	Fig. 15.1: $a$ pays 3 vs 4
FLCostShare (Thm 15.21)	ghost duals ⇒ cross-monotone, $\tfrac13$ -BB	prune within $2t_i$ ; disjoint balls
Lemma 15.22	gadget OPT $= 3m + k + 1$	extra facilities cover 1 extra city
Thm 15.23	any cross-monotone FL scheme is $\le \tfrac13$ -BB	probabilistic method
Shapley formula	$\phi_i = \sum_s \frac{s!(n-1-s)!}{n!}\sum_{	S
Example 15.24	$\phi = (23/6, 11/6, 7/3)$ , not in core	core nonempty
Shapley + submodular	in core, cross-monotone	⇒ SH multicast via Moulin
Thm 15.26	Shapley unique under anonymity, dummy, additivity	proof omitted
Thm 15.28	Nash bargaining: unique under Pareto, symmetry, scale, IIA; $\max u_1u_2$	proof omitted

Facts to keep to hand

Every existence result in the first half is LP duality. Core ↔ fractional partitions (Bondareva–Shapley), approximate core ↔ integrality gap, and FL core ↔ the FL dual. Cost shares are dual variables.
“Closed under union” does all the structural work. Affordable sets in Moulin’s mechanism, tight sets in the submodular algorithm, and legal pruning in multicast SH all are closed under union. So there is a unique maximal object, order doesn’t matter, and nesting arguments go through.
Hierarchy of stability notions: Shapley is fair but may leave the core; the core stabilizes one allocation; cross-monotonicity stabilizes all allocations consistently. For facility location the achievable factors are 1 (possible with Shapley, which ignores the core), $\ge 1/1.52$ (core), and exactly $1/3$ (cross-monotone).
Submodularity makes everything easy. Primal-dual shares are cross-monotone with no modification, Shapley is in the core and cross-monotone, and Moulin’s converse holds. Outside submodularity you need tricks (ghost duals) and lose budget balance.
Cross-monotonicity fails through withdrawn help. In standard primal-dual a frozen agent stops contributing, so adding an agent can starve a third party. Ghost duals keep contributions flowing but don’t collect them.
Lower bounds on $\gamma$ are budget-balance proofs; upper bounds are adversarial instances. For the core, the instance is an integrality-gap example. For cross-monotonicity, it is a random coalition plus a symmetry argument.
Uniqueness comes from axioms, not stability. Shapley and Nash each pick one point by axioms. Nash’s product is forced by scale independence, just as additivity forces Shapley’s link-by-link splitting.

References

Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 15 (Jain, Mahdian)

Related

Motivation: dividing the bill for a shared service

Cooperative games

The running example: facility location

The core

Bondareva–Shapley: when is the core nonempty?

Approximate core

Facility location: the core LP is the standard LP dual

Core of NTU games

Group-strategyproof mechanisms from cross-monotonic schemes

Moulin’s mechanism

Building cross-monotonic shares: the primal-dual schema

Submodular games: the schema works unmodified

Facility location: why the standard algorithm fails, and ghost duals

Limits of cross-monotonicity: the probabilistic method

The Shapley value

Axiomatic characterization

The Nash bargaining solution

Quick reference

References

Mentioned in

Related

Motivation: dividing the bill for a shared service

Cooperative games

The running example: facility location

The core

Bondareva–Shapley: when is the core nonempty?

Approximate core

Facility location: the core LP is the standard LP dual

Core of NTU games

Group-strategyproof mechanisms from cross-monotonic schemes

Cross-monotonic cost-sharing schemes

Moulin’s mechanism

Building cross-monotonic shares: the primal-dual schema

Submodular games: the schema works unmodified

Facility location: why the standard algorithm fails, and ghost duals

Limits of cross-monotonicity: the probabilistic method

The Shapley value

From incremental sharing to Shapley

Axiomatic characterization

The Nash bargaining solution

Directions: cost sharing feeding back into algorithms

Quick reference

References

Mentioned in