Large Games

From Theory

Jump to: navigation, search

Scribe Aaron Elliott, Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

[edit]

Large Games (Games with many players)

N = # of players


A is set of actions A1xA2x...xAN where A_i \subseteq A and A \rightarrow [0, 1]


Utility u_i : A_1 x \Delta(A)\rightarrow [0,1]

anonymous ui(ai,a − i) = u(ai,π(a − i)) for all permutations of π

[edit]

Thereom 1

Take any mixed strategy NE σ, take \delta \in (0,1) with prob \geq(1-\delta) over draw a \in \sigma

\forall_{j} |v_j(a) - \bar\sigma_{i}| \leq \Delta = \sqrt{\frac{\log(\frac{2k}{\delta})}{N}}

\bar\sigma_j=E_a\in\sigma[v_j(a)]


2e^{-N\Delta^2}\leq\frac{\delta}{k}

|v_j(a)-\bar\sigma_j|\geq\Delta

rearranging we get |v(a)-\bar\sigma| \leq k\Delta

So for all j in support of σi, u_i(j, \bar\sigma_{-i}) is within δ of being a best response. \exists pure strategy N.E. within 2kΔ + δ of best response

[edit]

Thereom 2

In time O(Nk + 1), we can find a pure strategy ε − N.E..

STEP 1) For all possible v\in(\frac{O}{N},\frac{1}{N},...,\frac{N}{N})^k (\sum v_j=1)

STEP 1a) For each player i, let S_1=(a_i\in A_i|a_i is an ε - best response to (V_1 -\frac{1}{N}(0,0,...,1,0)\frac{N}{N-1})

STEP 2) Write LP 

 Also see these papers on Large Games. Large Robust Games (includes Bayesian)  Ex-Post Stability in Large Games
Retrieved from "http://wiki.cc.gatech.edu/theory/index.php/Large_Games"
Personal tools