Cooperative Game Theory, Combinatorial, and the Matching¶

Job: develop the cooperative (core / Shapley), the bargaining (Nash / Kalai–Smorodinsky), the matching (Gale–Shapley stable), and the combinatorial / algorithmic (Nisan / PPAD) — with the Gale–Shapley / Shapley value as the worked example.

Core¶

The cooperative and the core / Shapley¶

Cooperative / $(N,v)$ / core / Shapley	Description
Cooperative	$(N,v)$ the TU game, $v:2^N\to\mathbb{R}$ (the foundations)
Core	allocations $x$ with $\sum x_i=v(N)$, $\sum_{i\in S}x_i\ge v(S)$ (the foundations)
Shapley value	$\phi_i(v)=\sum\frac{

The bargaining and the Nash / Kalai¶

Bargaining / Nash / Kalai–Smorodinsky	Description
Nash bargaining	$\max\prod(u_i-d_i)$ s.t. feasibility (the optimization)
Kalai–Smorodinsky	the proportional, the optimization

The matching and the stable¶

Matching / Gale–Shapley / stable	Description
Matching	Gale–Shapley deferred acceptance (the discrete math)
Stable	no blocking pair (the discrete math)

The combinatorial and the algorithmic¶

Combinatorial / Nisan / algorithmic / PPAD	Description
Combinatorial GT	Nisan et al., the algorithmic (the discrete math)
PPAD	the Nash equilibrium complexity (the discrete math)

See it¶

Gale–Shapley stable matching and the Shapley value. The Gale–Shapley: the deferred acceptance (the men propose, women accept, the stable, the discrete math). The Shapley: the $\phi_i(v)=\sum\frac{|S|!(n-|S|-1)!}{n!}(v(S\cup i)-v(S))$ (the foundations). The key point: the Gale–Shapley the stable, the Shapley the marginal.

Check¶

Explain the Shapley value and the core, and the cooperative.

The cooperative: the $(N,v)$ the TU game (the $v:2^N\to\mathbb{R}$, the $v(\emptyset)=0$, the foundations). The core: the $x$ the allocation (the $\sum x_i=v(N)$, the $\sum_{i\in S}x_i\ge v(S)$ all $S$, the foundations). The Shapley: the $\phi_i=\sum_S\frac{|S|!(n-|S|-1)!}{n!}(v(S\cup i)-v(S))$ (the marginal contribution, the average, the Shapley 1953, the foundations). The Shapley the unique linear symmetric dummy-efficient. So the cooperative the $(N,v)$, the core the stable, the Shapley the marginal.

Explain the Gale–Shapley and the Nash bargaining, and the PPAD.

The Gale–Shapley: the deferred acceptance (the men propose, women accept the best, the stable, the discrete math). The Nash bargaining: the $\max\prod(u_i-d_i)$ (the Nash 1950, the axiomatic, the optimization). The Kalai–Smorodinsky: the proportional (the $\max\lambda$ s.t. $u_i=d_i+\lambda(\bar u_i-d_i)$, the optimization). The PPAD: the Nash equilibrium complexity (the Daskalakis–Goldberg–Papadimitriou the PPAD-complete, the discrete math). So the Gale–Shapley the stable, the Nash bargaining the $\max\prod$, the PPAD the complexity.

Pitfalls¶

The core the [foundations] (the $\sum x_i\ge v(S)$, the foundations) — the core the stable, the Shapley the marginal.
The Nash bargaining the [optimization] ($\max\prod$, the optimization) — the Nash bargaining the axiomatic, the Kalai the proportional.
The Gale–Shapley the [discrete math] (the deferred acceptance, the discrete math) — the Gale–Shapley the stable, the discrete math.
The PPAD the complexity (the Daskalakis, the discrete math) — the PPAD the Nash, the complexity.

Refs¶

Shapley, "A value for n-person games" (1953); the Shapley value
Gale–Shapley, "College admissions and stability of marriage" (1962); the matching
Nash, "The bargaining problem" (1950); the Nash bargaining
Daskalakis–Goldberg–Papadimitriou, "The complexity of computing a Nash equilibrium" (2009); the PPAD

Next¶

GT index · Foundations · Mechanism Design · Repeated & Folk · Learning & No-Regret · Optimization · Discrete math