Skip to content

Congestion Game

Introduced by Rosenthal in 1973

include

  • cost-sharing game
  • network congestion games
  • load balancing games

Definition

See here.

Omitted

Existence of NE

CG has potential function, therefore the existence of NE is guaranteed.

Omitted

PoS and PoA

Omitted

Some known results:

PoS PoA
Network cost sharing \(H_n\) on directed, \(2.245/H_n\) on undirected, \(1.862/O(\log n/\log\log n)\) on undirected multicasting, \(O(1)\) on undirected multicasting \(n\)
Linear congestion game \(1+1/\sqrt3\) \(5/2\)
Load balancing \(4/3\) \(5/2\)

Complexity of Computing NE

Local search problem!

NE is local optima.

Polynomially Local Search Class

Definition

A local search problem \(\pi\in PLS\) if the following polynomial time algorithm exist:

  1. Algorithm \(A\) which computes for every instance \(x\) of \(\pi\) an initial feasible solution
  2. Algorithm \(B\) which computes for every instance \(x\) of \(\pi\) and every feasible solution \(y\) the objective value \(c(y)\).
  3. Algorithm \(C\) which determines for every instance \(x\) of \(\pi\) and every feasible solution \(y\) whether \(y\) is a local optimum and in the negative case a better neighbor solution

(If the local search problem can be solved in polynomial time, we also need polynomial steps)

A typical PLS problem: Max Weighted Cut.

PLS-Reduction

A problem \(\pi\in PLS\) is \(PLS\)-reducible to a problem \(\pi'\in PLS\) if there are polynomial time computable function \(g\) and \(h\) s.t.

  • \(g\) maps instances \(x\) of \(\pi\) to instances \(x'=g(x)\) of \(\pi'\)
  • \(h\) maps pairs \((y',x)\) with \(y'\) being a solution of \(x'\) to solutions \(y\) of \(x\)
  • For all instances \(x\) of \(\pi\), if \(y'\) is a local optimum of \(x'\), then \(h(y',x)\) is a local optimum of \(x\)

PLS-Completeness

A local search problem \(\pi\) is \(PLS\)-complete if every problem in \(PLS\) is \(PLS\)-reducible to \(\pi\).

Conjecture: A polynomial time algorithm for computing local optima of a PLS-complete problem is not exist.

Theorem: Congestion Games are PLS-complete.

Proof by PLS-reduction from max weighted cut.

Negative Results on CG

PLS-completeness

  • Symmetric CGs
  • Asymmetric Network CGs with linear delays
  • Shapley Network cost sharing games

Positive Results on CG

Polynomial time computability: NE in Symmetric Network CGs with non-decreasing delay function (STOC 2004)

  • Reduction to Min-cost flow problem
  • The result can be also extended to network CGs in which all the players share the same source

There exist Symmetric Network CG in which any sequence of improving moves is exponentially long in \(n\)

Open Problem

Is it possible to compute in polynomial time a NE for symmetric CGs with linear delays, or is such a problem PLS-complete?

Approximability of NE

Fast convergence is guaranteed only for special classes of CGs

Question: What is the performance reached after a limited interaction of the selfish players?

After a small number of best responses, the selfish players are able to reach a solution \(S\) such that \(f(S)/f(S^*)\) is close to the performance at equilibrium, that is \(O(PoA)\).

Some Results

In any CG with polynomial delays, any sequence of fair best responses converges from any initial state to a state \(S\) s.t. \(f(S)/f(S^*)=O(PoA)\) in time \(\Theta(n\log\log n)\). (ICALP 2008)

  • Fair sequence means every player makes at least one best response every \(O(n)\) steps

There exists a CH with linear delays, an initial state \(S_0\) and a unfair sequence of best response starting from \(S_0\) of length exponential in \(n\) s.t. \(f(S)/f(S^*)=\Omega(\sqrt n/\log n)\), where \(S\) is the final state. (EC 2008)

Fair sequence are necessary in order to fast obtain good solution (2011)

In network CG with Shapley cost sharing function (2007)

  • After one round, \(f(S)/f(S^*)=O(n^2)\)
  • After two rounds, \(f(S)/f(S^*)=O(n^{3/2})\)
  • After \(k\) rounds, \(f(S)/f(S^*)=\Omega(n^{(k+1)/k})\)