Zkouška

Normal-form games Nash equilibrium Zero-sum games Bimatrix games Other notions of equilibria Regret minimization Applications of regret minimization Games in extensive form Mechanism design Applications of mechanism design Survey questions

Normal-form games

Definition: Normal-form game
- hra v normální tvaru je trojice $(P,A,u)$
- $P$ … konečná množina $n$ hráčů
- $A=A_1\times\dots\times A_n$ $A = A_{1} \times \dots \times A_{n}$ je množina akčních profilů
  - $A_i$ … množina akcí $i$ -tého hráče
- $u=(u_1,\dots,u_n)$ , kde $u_i:A\to\mathbb R$ je užitková funkce $i$ -tého hráče
Definition: Strategies
- čistá (pure) strategie $s_i$ $s_{i}$ hráče $i$ $i$ je akce z $A_i$ $A_{i}$
  - profil čistých strategií je $n$ -tice čistých strategií (akcí) – za každého z $n$ hráčů je tam jedna
- smíšená (mixed) strategie $s_i$ $s_{i}$ hráče $i$ $i$ je pravděpodobnostní distribuce přes $A_i$ $A_{i}$
  - tedy $s_i(a_i)\in[0,1]$ a $\sum_{a_i\in A_i}s_i(a_i)=1$
  - profil smíšených strategií je $n$ -tice smíšených strategií
- každá čistá strategie je smíšená
Definition: Expected payoff
- ve hře $G=(P,A,u)$ je expected payoff (střední hodnota výplatní funkce) pro hráče $i$ z profilu smíšených strategií $s$ určena vzorcem $u_i(s)=\sum_{a\in A} u_i(a)\cdot \underbrace{\prod_{j=1}^n s_j(a_j)}_{P(a)}$
- platí linearita střední hodnoty výplatní funkce $u_i(s)=\sum_{a_i\in A_i} s_i(a_i)\cdot u_i(a_i;s_{-i})$
Example: Five basic games
- vězňovo dilema
- matching pennies
- battle of sexes
- game of chicken
- bitva o duši Gothamu

Nash equilibrium

Definition: Best response
- best response $i$ -tého hráče na strategický profil $s_{-i}$ je smíšená strategie $s_i^*$ taková, že $\forall s_i'\in S_i:u_i(s_i^*;s_{-i})\geq u_i(s_i';s_{-i})$
- kdyby hráč $i$ znal strategie ostatních, zvolil by si strategii $s_i^*$ , protože maximalizuje jeho očekávanou výplatu, pokud ostatní hrají $s_{-i}$
Definition: Nash equilibrium
- mějme hru $G=(P,A,u)$ v normální tvaru s $n$ hráči
- pak Nashovo ekvilibrium (NE) ve hře $G$ je strategický profil $(s_1,\dots,s_n)$ takový, že $s_i$ je best response hráče $i$ na $s_{-i}$ pro každé $i\in P$
- tedy žádný hráč by neměnil svou strategii, kdyby znal strategie ostatních
Theorem: Nash’s Theorem
- Nashova věta: každá hra v normálním tvaru má Nashovo ekvilibrium
- pomocné definice a tvrzení
  - $X\subseteq\mathbb R^d$ je kompaktní, pokud je uzavřená a omezená
  - $Y\subseteq\mathbb R^d$ je konvexní, pokud $(\forall x,y\in Y)(\forall\alpha\in [0,1]):\alpha x+(1-\alpha)y\in Y$
  - pro $n$ $n$ afinně nezávislých bodů $x_1,\dots,x_n\in\mathbb R^d$ $x_{1}, \dots, x_{n} \in R^{d}$ definujeme $(n-1)$ $(n - 1)$ -simplex $\Delta_n$ $Δ_{n}$ na $x_1,\dots,x_n$ $x_{1}, \dots, x_{n}$ jako množinu konvexních kombinací bodů $x_1,\dots,x_n$ $x_{1}, \dots, x_{n}$
    - každý simplex je kompaktní konvexní množina v $\mathbb R^d$
  - lemma: pokud $K_1,\dots,K_n$ jsou kompaktní množiny a $\forall i:K_i\subseteq\mathbb R^{d_i}$ , pak $K_1\times\dots\times K_n$ je kompaktní množina v $\mathbb R^{d_1+\dots+d_n}$
  - Brouwerova věta o pevném bodu: pokud $K\subseteq\mathbb R^d$ je neprázdná kompaktní konvexní množina a $f:K\to K$ je spojité zobrazení, pak existuje pevný bod $x_0\in K$ pro $f$ , tedy $f(x_0)=x_0$
- důkaz Nashovy věty
  - nechť $K=S_1\times\dots\times S_n$ $K = S_{1} \times \dots \times S_{n}$ je množina všech smíšených strategií
    - $S_i$ … množina smíšených strategií hráče $i$
    - každá množina $S_i$ je simplex, takže je kompaktní a konvexní
    - proto i $K$ je kompaktní
    - pro libovolné $s,s'\in K$ a $\alpha\in[0,1]$ je $\alpha s+(1-\alpha)s'$ také smíšený strategický profil v $K$ , tedy $K$ je konvexní
  - pro hráče $i\in S$ $i \in S$ a akci $a_i\in A$ $a_{i} \in A$ definujeme zobrazení $\varphi_{i,a_i}:K\to\mathbb R$ $φ_{i, a_{i}} : K \to R$ tak, že $\varphi_{i,a_i}(s)=\max\set{0,u_i(a_i;s_{-i})-u_i(s)}$ $φ_{i, a_{i}} (s) = max {0, u_{i} (a_{i}; s_{- i}) - u_{i} (s)}$
    - tato funkce vyjadřuje, o kolik by si hráč polepšil, kdyby místo $s_i$ hrál akci $a_i$ (pokud by si nepolepšil, je nulová)
    - z definice $u_i$ je toto zobrazení spojité
  - pro $s\in K$ $s \in K$ definujeme nový „vylepšený“ strategický profil $s'\in K$ $s^{'} \in K$ tak, že přidáme pravděpodobnost akcím, které jsou lepšími odpověďmi na $s_{-i}$ $s_{- i}$
    - $s'_i(a_i)=\frac{s_i(a_i)+\varphi_{i,a_i}(s)}{\sum_{b_i\in A_i}(s_i(b_i)+\varphi_{i,b_i}(s))}=\frac{s_i(a_i)+\varphi_{i,a_i}(s)}{1+\sum_{b_i\in A_i}\varphi_{i,b_i}(s)}$
    - ve jmenovateli je normalizační konstanta
  - pak definujeme $f:K\to K$ $f : K \to K$ tak, že nastavíme $f(s)=s'$ $f (s) = s^{'}$
    - $f$ je spojitá, protože $\varphi$ jsou spojité
    - podle Brouwerovy věty má $f$ pevný bod
  - pokud je $s\in K$ Nashovo ekvilibrium, pak všechny $\varphi$ jsou nulové a $f(s)=s$ , tedy $s$ je pevný bod funkce $f$
  - pokud je $s\in K$ $s \in K$ pevným bodem funkce $f$ $f$ …
    - zvolíme libovolného hráče $i\in P$
    - v supportu $s_i$ $s_{i}$ existuje akce $a_i'\in A_i$ $a_{i}^{'} \in A_{i}$ taková, že $u_i(a'_i;s_{-i})\leq u_i(s)$ $u_{i} (a_{i}^{'}; s_{- i}) \leq u_{i} (s)$
      - jinak by platilo $u_i(s)\lt\sum_{a_i}s_i(a_i)u_i(a_i;s_{-i})$ , což je spor s linearitou střední hodnoty výplatní funkce
      - support $s_i$ … akce $\in A_i$ , které $s_i$ nemapuje na nulu
    - pro tuto akci $a_i'$ nutně platí $\varphi_{i,a_i'}=0$ (díky té nerovnosti)
    - tak získáme $s'_i(a'_i)=\frac{s_i(a'_i)}{1+\sum_{b_i\in A_i}\varphi_{i,b_i}(s)}$
    - $s$ je pevný bod, proto $s_i'(a_i')=s_i(a_i')$ , tedy ve jmenovateli musí být jednička a suma bude nulová
    - proto $u_i(s)\geq u_i(b_i;s_{-i})$ pro každé $b_i\in A_i$
    - z toho vyplývá, že pro libovolnou smíšenou strategii $s_i''\in S_i$ $s_{i}^{''} \in S_{i}$ platí $u_i(s_i'';s_{-i})=\sum_{b_i\in A_i} s_i''(b_i)u_i(b_i;s_{-i})\leq\sum_{b_i\in A_i} s''_i(b_i)u_i(s)=u_i(s)$
      - levá rovnost z linearity, nerovnost z nerovnosti výše, pravá rovnost z jednotkového součtu pravděpodobností
    - tedy $s_i$ je best response hráče $i$ na $s_{-i}$ a $s$ je smíšené Nashovo ekvilibrium hry $G$
Definition: Pareto optimality
- strategický profil $s$ $s$ v $G$ $G$ Pareto dominuje $s'$ $s^{'}$ , píšeme $s'\prec s$ $s^{'} ≺ s$ , pokud…
  - $\forall i\in P:u_i(s)\geq u_i(s')$
  - $\exists j\in P:u_j(s)\gt u_j(s')$
- $\prec$ je částečná uspořádání množiny $S$ všech strategických profilů hry $G$
- za nejlepší výsledky $G$ se považují maxima $S$ podle $\prec$
- strategický profil $s\in S$ $s \in S$ je Pareto optimální, pokud neexistuje jiný profil, který ho dominuje
  - ve hrách nulového součtu jsou všechny strategické profily Pareto optimální
  - ne všechna Nashova ekvilibria jsou Pareto optimální (viz vězňovo dilema)

Zero-sum games

Definition: Zero-sum game and its representation
- $G=(P,A=A_1\times A_2,u)$
- $\forall a\in A:u_1(a)+u_2(a)=0$
- pokud $|A_1|=m$ a $|A_2|=n$ , pak můžeme $G$ reprezentovat pomocí výplatní matice $M\in\mathbb R^{m\times n}$ , kde $M_{ij}=u_1(i,j)=-u_2(i,j)$
- pro strategický profil $(s_1,s_2)$ uvažujeme vektory smíšených strategií $x,y$ takové, že $x_i=s_1(i)$ a podobně $y_i=s_2(j)$
- pak platí $u_1(s)=x^TMy=-u_2(s)$
Definition: Worst-case optimal strategies
- best response druhého hráče je vektor $y\in S_2$ , který minimalizuje $x^TMy$
- best response prvního hráče je vektor $x\in S_1$ , který maximalizuje $x^TMy$
- $\beta(x)=\min_{y\in S_2}x^TMy$ je nejlepší očekávaný payoff druhého hráče proti $x$
- $\alpha(y)=\max_{x\in S_1} x^TMy$ je nejlepší očekávaný payoff prvního hráče proti $y$
- strategický profil $(x,y)$ je NE, právě když $\beta(x)=x^TMy=\alpha(y)$
- pokud první hráč předpokládá, že druhý hráč vždy zvolí best response na každou jeho strategii, a snaží se maximalizovat payoff za tohoto předpokladu, zvolí strategii $\overline x\in S_1$ $\overline{x} \in S_{1}$
  - pro tuto „worst-case optimal strategy“ platí $\beta(\overline x)=\max_{x\in S_1}\beta(x)$
- podobně worst-case optimal strategy je taková strategie $\overline y\in S_2$ , že $\alpha(\overline y)=\min_{y\in S_2}\alpha(y)$
Theorem: Worst-case optimal strategies and NE
- lemma
  1. $(\forall x\in S_1)(\forall y\in S_2):\beta(x)\leq x^TMy\leq\alpha(y)$
  2. pokud je strategický profil $(x^*,y^*)$ Nashovým ekvilibriem, pak jsou obě strategie worst-case optimální
  3. libovolné strategie $x^*\in S_1$ a $y^*\in S_2$ splňující $\beta(x^*)=\alpha(y^*)$ tvoří Nashovo ekvilibrium $(x^*,y^*)$
- důkaz
  1. přímo z definice $\beta,\alpha$ (jedno definujeme jako minimum, druhé jako maximum)
  2. z (1) vyplývá $\forall x\in S_1:\beta(x)\leq\alpha(y^*)$ $\forall x \in S_{1} : β (x) \leq α (y^{*})$
    - $(x^*,y^*)$ je NE, proto $\beta(x^*)=\alpha(y^*)$
    - tedy $\forall x\in S_1:\beta(x)\leq \beta(x^*)$
    - proto $x^*$ je worst-case optimální pro prvního hráče, podobně $y^*$ pro druhého hráče
  3. pokud $\beta(x^*)=\alpha(y^*)$ , pak (1) implikuje $\beta(x^*)=(x^*)^TMy^*=\alpha(y^*)$
Theorem: The Duality Theorem
- lineární program $P$ lze vyjádřit v kanonickém tvaru jako maximalizaci $c^Tx$ při omezujících podmínkách $Ax\leq b$ a $x\geq 0$
- k primárnímu programu $P$ najdeme duální program $D$ , kde minimalizujeme $b^Ty$ při omezujících podmínkách $A^Ty\geq c$ a $y\geq 0$
- věta
  - pokud oba lineární programy $P,D$ mají přípustná řešení, pak mají oba optimální řešení
  - navíc, pokud $x^*$ a $y^*$ jsou optimální řešení pro $P$ a $D$ po řadě, pak $c^Tx^*=b^Ty^*$ , to znamená maximum $P$ se rovná minimu $D$
Theorem: The Minimax Theorem
- věta
  - pro každou hru s nulovým součtem platí, že worst-case optimální strategie pro oba hráče existují a mohou být efektivně spočteny
  - existuje číslo $v$ takové, že pro libovolné worst-case optimální strategie $x^*,y^*$ je strategický profil $(x^*,y^*)$ Nashovým ekvilibriem a $\beta(x^*)=(x^*)^TMy^*=\alpha(y^*)=v$
- důkaz
  - pro pevné $x\in S_1$ $x \in S_{1}$ určíme best response druhého hráče
    - použijeme lineární program $P$ $P$ s proměnnými $y_1,\dots,y_n$ $y_{1}, \dots, y_{n}$
      - minimalizuj $x^TMy$ za podmínek $\sum y_j=1$ a $y\geq 0$
    - jeho duál je $D$ $D$ s proměnnou $x_0$ $x_{0}$
      - maximalizuj $x_0$ za podmínky $1x_0\leq M^Tx$
    - podle věty o dualitě mají oba programy stejné optimum $\beta(x)$
    - z $x$ uděláme vektor proměnných $x_1,\dots,x_m$
    - tak získáme lineární program $D'$ $D^{'}$ s proměnnými $x_0,x_1,\dots,x_m$ $x_{0}, x_{1}, \dots, x_{m}$
      - maximalizuj $x_0$ za podmínek:
        
        $1x_0-M^Tx\leq 0$
        
        $\sum_{i=1}^mx_i=1$
        
        $x\geq 0$
    - optimum $x^*$ programu $D'$ je worst-case optimální strategie pro prvního hráče
  - podobně lze nalézt worst-case optimální strategii pro druhého hráče
    - minimalizuj $y_0$ $y_{0}$ za podmínek:
      - $1y_0-My\geq 0$
      - $\sum_{j=1}^ny_j=1$
      - $y\geq 0$
  - nyní zbývá ukázat, že $(x^*,y^*)$ je NE a $\beta(x^*)=(x^*)^TMy^*=\alpha(y^*)=v$
  - z věty o dualitě vidíme, že $P'$ a $D'$ mají stejné optimum $\beta(x^*)=x^*_0=y^*_0=\alpha(y^*)$ , což je požadované $v$
  - z části (3) lemmatu o worst-case optimálních strategiích vyplývá, že jsme našli NE a také rovnost $\beta(x^*)=(x^*)^TMy^*=\alpha(y^*)$

Bimatrix games

Definition: Bimatrix game, nondegenerate bimatrix game
- maticová hra (bimatrix game) je hra dvou hráčů v normálním tvaru
  - $G=(\set{1,2},A=A_1\times A_2,u)$
  - $|A_1|=m$ , $|A_2|=n$
  - výplatní funkce $u_1,u_2$ $u_{1}, u_{2}$ reprezentujeme maticemi $M,N\in\mathbb R^{m\times n}$ $M, N \in R^{m \times n}$
    - $M_{ij}=u_1(i,j)$
    - $N_{ij}=u_2(i,j)$
  - tedy akce prvního hráče odpovídají řádkům, akce druhého sloupcům
  - uvažujeme-li vektory smíšených strategií $x,y$ , pak platí $u_1(s)=x^TMy$ a $u_2(s)=x^TNy$
- maticová hra je nedegenerovaná, pokud ke každé smíšené strategii se supportem velikosti $k$ existuje nejvýše $k$ čistých best responses
Theorem: Best response condition
- definice: support (nosič) smíšené strategie $s_i$ je množina $\set{a_i\in A_i:s_i(a_i)\gt 0}$
- pozorování (best response condition): ve hře $G=(P,A,u)$ pro každého hráče platí, že smíšená strategie $s_i$ je best response na $s_{-i}$ , právě když všechny čisté strategie v supportu $s_i$ jsou best responses na $s_{-i}$
- důkaz $\impliedby$ $⟸$
  - nechť každé $a_i\in\text{Supp}(s_i)$ splňuje $u_i(a_i;s_{-i})\geq u_i(s_i';s_{-i})$ pro každé $s_i' \in S_i$
  - pak pro každé $s_i'\in S_i$ z linearity $u_i$ vyplývá $u_i(s)=\sum_{a_i\in\text{Supp}(s_i)}s_i(a_i)u_i(a_i;s_{-i})\geq \sum_{a_i\in\text{Supp}(s_i)}s_i(a_i)u_i(s_i';s_{-i})=u_i(s_i';s_{-i})$
- důkaz $\implies$ $⟹$ (sporem)
  - nechť $s_i$ je best response hráče $i$ na $s_{-i}$
  - předpokládejme, že existuje $\overline a_i\in\text{Supp}(s_i)$ , co není best response
  - pak existuje $s_i'\in S_i$ , kde $u_i(\overline a_i;s_{-i})\lt u_i(s_i';s_{-i})$
  - jelikož $s_i$ je best response na $s_{-i}$ , nutně $s_i(\overline a_i)\lt 1$
  - z linearity $u_i$ najdeme $\hat a_i\in\text{Supp}(s_i)$ , kde $u_i(\hat a_i;s_{-i})\gt u_i(\overline a_i;s_{-i})$
  - definujeme novou smíšenou strategii $s^*_i$ $s_{i}^{*}$
    - $s^*_i(\overline a_i)=0$
    - $s_i^*(\hat a_i)=s_i(\hat a_i)+s_i(\overline a_i)$
    - jinak $s^*_i(a_i)=s_i(a_i)$
  - z linearity $u_i$ $u_{i}$ dostaneme $u_i(s_i^*;s_{-i})=\sum_{a_i\in A_i}s^*_i(a_i)u_i(a_i;s_{-i})\gt \sum_{a_i\in A_i}s_i(a_i)u_i(a_i;s_{-i})=u_i(s)$
    - což je spor
Algorithm: Support enumeration
- best response condition (BRC) v maticových hrách
  - $u_1(s)=x^TMy,\;u_2(s)=x^TNy$
  - podle BRC je $x$ $x$ best response na $y$ $y$ , právě když $\forall i\in A_1:x_i\gt 0\implies M_{i,*}y=\max\set{M_{k,*}y\mid k\in A_1}$
    - pro každý support platí, že jeho čistá strategie je maximální z čistých strategií
  - podobně $y$ je best response na $x$ , právě když $\forall j\in A_2:y_j\gt 0\implies N^T_{j,*}x=\max\set{N^T_{k,*}x:k\in A_2}$
- hledáme NE v nedegenerované maticové hře $G$
- nechť $I\subseteq A_1$ a $J\subseteq A_2$ jsou supporty v $G$
- sestavíme soustavu rovnic o $|I|+|J|+2$ $∣ I ∣ + ∣ J ∣ + 2$ neznámých
  - $\sum_{i\in I} x_i=1$
  - $\sum_{j\in J} y_j=1$
  - $\forall j:N^T_{j,*}x=v$
  - $\forall i:M_{i,*}y=u$
- $u,v$ budou nabývat hodnot maxim plynoucích z BRC (viz výše)
- také požadujeme nezápornost proměnných
- pořád je ale nezbytné získat $I,J$ , to za nás provede algoritmus
- u nedegenerovaných her vyplývá přímo z BRC, že supporty strategií v Nashově ekvilibriu budou mít stejnou velikost
- tedy můžeme projít všechny možné supporty $I,J$ velikosti $k\in\set{1,\dots,\min\set{m,n}}$ a pro každou dvojici řešíme soustavu rovnic (pokud najdeme nezáporné řešení, máme NE)
- algoritmus běží přibližně v čase $4^n$ $4^{n}$ pro $m=n$ $m = n$
  - $m=|A_1|,\;n=|A_2|$
Definition: Best response polyhedra, best response polytope
- mějme strategický profil $s$ se smíšenými strategiemi $x,y$
- polyedr nejlepších odpovědí
  - pro prvního hráče: $\overline P=\set{(x,v)\in\mathbb R^m\times \mathbb R:x\geq 0\land 1^Tx=1\land N^Tx\leq 1v}$
  - pro druhého hráče: $\overline Q=\set{(y,u)\in\mathbb R^n\times\mathbb R:y\geq 0\land 1^Ty=1\land My\leq 1u}$
  - poslední nerovnice $My\leq 1u$ říká, že střední hodnota výplatní funkce $u_1(s)$ je nejvýše $u$ , jelikož $u_1(s)=x^TMy\leq x^T1u=u\sum x_i=u$ (podobné je to s nerovnicí $N^Tx\leq 1v$ )
  - definujeme labels
    - bod $(x,v)\in\overline P$ má label $i\in A_1\cup A_2$ , pokud buď $i\in A_1\land x_i=0$ , nebo $i\in A_2\land N^T_{i,*}x=v$ (tedy pokud $i\in A_1$ není v supportu nebo pokud $i\in A_2$ je best response na $x$ )
    - podobně (opačně) pro $(y,u)\in\overline Q$
    - každý bod může mít více labels
- (normalizovaný) polytop nejlepších odpovědí
  - předpokládám, že $M,N^T$ jsou nezáporné a nemají nulový sloupec (jednoduše přičteme velkou konstantu k výplatám)
  - každou nerovnost $N^T_{i,*}x\leq v$ vydělíme $v$
  - $x_i/v$ bude naše nová proměnná
  - podobně pro $\overline Q$
  - tak normalizujeme výplaty na jedničku a získáme (normalizované) polytopy nejlepších odpovědí
    - pro prvního hráče: $P=\set{x\in\mathbb R^m:x\geq 0\land N^Tx\leq 1}$
    - pro druhého hráče: $Q=\set{y\in\mathbb R^n:y\geq 0\land My\leq 1}$
  - nerovnosti mají stejné významy (co se týče supportu / best response)
  - z předpokladu na $M,N$ jsou polyedry $P,Q$ omezené (jsou to polytopy) a mají dimenze $m$ a $n$
  - nevýhoda: složky $x$ a $y$ se nesečtou na jedničku, takže je musíme přeškálovat
  - polytop $\overline P$ $\overline{P}$ odpovídá $P\setminus\set{0}$ $P ∖ {0}$ podle projektivní transformace $(x,v)\mapsto x/v$ $(x, v) \mapsto x / v$ (podobně $\overline Q$ $\overline{Q}$ odpovídá $P\setminus\set{0}$ $P ∖ {0}$ )
    - projektivní transformace zachovává incidence, tedy labels zůstávají stejné
Theorem: NE and Best response polyhedra/polytope
- tvrzení: strategický profil $s$ je NE, právě když je pár $((x,v),(y,u))\in\overline P\times\overline Q$ kompletně označen, tedy každý label $i\in A_1\cup A_2$ se objevuje jako label $(x,v)$ nebo $(y,u)$
- důkaz
  - podle best response condition je $s_i$ best response na $s_{-i}$ , právě když všechny čisté strategie supportu $s_i$ jsou best responses na $s_{-i}$
  - pokud chybí label $i$ , znamená to, že $i$ je v supportu, ale čistá strategie $i$ není best response
  - pokud má dvojice bodů dohromady všechny labely, pak $s_1$ a $s_2$ jsou navzájem best responses, jelikož každá čistá strategie je buď best response, nebo není v supportu
  - pak je $s$ Nashovo ekvilibrium
- důsledek pro polytop
  - strategický profil $s$ je NE, právě když je bod $(x/u_2(s),y/u_1(s))\in P\times Q\setminus\set{(0,0)}$ kompletně označen
Algorithm: Vertex enumeration
- z nedegenerovanosti $G$ víme, že každý bod $P$ má nejvýše $m$ labels, podobně každý bod $Q$ má nejvýše $n$ labels (pro $k$ prvků supportu je nejvýše $k$ best responses)
- labely odpovídají stěnám polytopu, proto pouze vrcholy můžou mít přesně $m$ a $n$ labels (je to prostý polytop, žádné body nemají víc než $m$ , respektive $n$ vrcholů)
- algoritmus
  - vstup: nedegenerovaná maticová hra $G$
  - výstup: všechna Nashova ekvilibria hry $G$
  - pro každou dvojici vrcholů $(x,y)$ $(x, y)$ z $(P\setminus\set{0})\times(Q\setminus\set{0})$ $(P ∖ {0}) \times (Q ∖ {0})$
    - pokud je $(x,y)$ kompletně označen, vrať $(x/(1^Tx),y/(1^Ty))$ jako Nashovo ekvilibrium
- všechny vrcholy prostého polytopu v $\mathbb R^d$ s $v$ vrcholy a $N$ popisujícími nerovnostmi mohou být nalezeny v čase $O(dNv)$
- ale pokud $m=n$ , polytopy nejlepších odpovědí mohou mít $c^n$ vrcholů pro nějakou konstantu $c\in(1,2.9)$
- hledání zrychlíme tak, že budeme sledoval labels (viz Lemke–Howson)
Algorithm: Lemke–Howson algorithm
- $P$ je prostý polytop dimenze $m$ , každému jeho vrcholu přiléhá $m$ hran a $m$ stěn
- každý vrchol polytopu $P$ má $m$ labels a každá hrana má $m-1$ labels
- když „upustíme“ label $\ell\in A_1\cup A_2$ z vrcholu $x$ polytopu $P$ , znamená to, že se přesouváme po hraně $P$ , která je incidentní s vrcholem $x$ a má stejné labely jako $x$ kromě $\ell$
- druhý konec hrany má stejné labels jako $x$ , akorát místo $\ell$ má jiný label, který „sebereme“
- podobně definujeme upouštění a sbírání labels v $Q$
- algoritmus
  - začínáme v $(0,0)$ a střídavě prochází po hranách v $P$ a $Q$
  - v prvním kroku vybereme (náhodný) label $k\in A_1\cup A_2$ a upustíme ho
  - pak sebereme nový label $\ell$
  - ten má duplikát ve druhém polytopu
  - v dalším kroku tento duplikát upustíme a sebereme nový label $\ell'$
  - takhle iterujeme pořád dál, zastavíme se v momentě, kdy $\ell'=k$
- duplikát buď odpovídá nové best response, která má kladnou pravděpodobnost, nebo čisté strategii, jejíž pravděpodobnost jsme vynulovali a přesouváme se směrem od její best response stěny
- algoritmus vrací jedno Nashovo ekvilibrium v $G$ , funguje pro nedegenerované maticové hry
- správnost
  - věta: algoritmus zastaví po konečném počtu kroků a vrátí vektory smíšených strategií NE
  - nechť $k$ je label vybraný v prvním kroku
  - sestavíme konfigurační graf $\mathcal G$ , kde jsou vrcholy tvořeny páry $(x,y)$ vrcholů z $P\times Q$ , které jsou $k$ -téměř kompletně označené (každý label z $A_1\cup A_2\setminus\set{k}$ je labelem $x$ nebo $y$ )
  - mezi vrcholy v $\mathcal G$ vede hrana, právě když se mezi dvojicí párů dá projít v jednom kroku algoritmu (jeden vrchol dvojice se nemění, druhý vrchol změníme průchodem po hraně polytopu)
  - $\mathcal G$ je zjevně konečný
  - $\mathcal G$ $G$ má vrcholy stupně 1 nebo 2 (tedy je to disjunktní sjednocení cest a cyklů)
    - pokud má $(x,y)$ všechny labels z $A_1\cup A_2$ , pak je připojen k právě jednomu vrcholu, jelikož právě jeden z vrcholů $x,y$ má $k$ a můžeme ho upustit jenom z tohoto vrcholu
    - jinak $x,y$ sdílejí jeden label a $(x,y)$ je incidentní se dvěma hranami, jelikož duplikát můžeme upustit z vrcholu $x$ nebo z vrcholu $y$
  - Lemke–Howson začíná v listu $(0,0)$ , prochází po cestě a do žádného vrcholu se nevrací, skončí na konci cesty v listu $(x^*,y^*)$
- poznámka: v $\mathcal G$ jsou všechna Nashova ekvilibria, z každého z nich můžeme odebrat $k$ , takže jsou vždy na konci cest
- součet vrcholů stupně 1 musí být sudý, jeden z nich je $(0,0)$ $(0, 0)$ , ostatní jsou NE, z čehož vyplývá, že v nedegerované maticové hře je lichý počet NE
  - Lemke–Howson vždy najde jedno NE
  - degenerované hry můžou mít nekonečně mnoho NE
- algoritmus lze implementovat pomocí komplementárního pivotování
- může běžet exponenciálně dlouho ( $O(2^n)$ $O (2^{n})$ kroků pro $n=m$ $n = m$ )
  - v praxi je dostatečně rychlý (polynomiální čas na uniformně náhodných hrách)
Theorem: Computational complexity of NASH
- NASH = problém nalezení NE v maticových hrách
- NASH není NP-úplný, protože víme, že NE vždycky existuje
- třída FNP
  - vstupem FNP problému je instance problému z NP, algoritmus nám vrátí řešení, pokud existuje, jinak vrátí „ne“
  - NASH patří do FNP, protože ověření NE lze provést pomocí best response condition
  - ale NASH pravděpodobně není FNP-úplný, protože kdyby byl, NP = coNP
- strukturu NASH lze zachytit jako hledání konce cesty v grafu stupně nejvýše 2 (viz důkaz korektnosti Lemke–Howsonova algoritmu)
  - problém END-OF-THE-LINE = pro orientovaný graf $G$ $G$ , kde má každý vrchol nejvýše jednoho předchůdce a jednoho následníka, a zadaný vrchol $s$ $s$ bez předchůdce najdi vrchol $t\neq s$ $t \neq = s$ bez předchůdce nebo následníka
    - $G$ je specifikován tak, že funkce $f(v)$ , co běží v polynomiálním čase, vrací předchůdce a následníka $v$ , pokud existují
    - tedy $G$ může být exponenciálně velký vůči velikosti vstupu
  - PPAD je složitostní třída, kam spadají problémy, které lze v polynomiálním čase převést na END-OF-THE-LINE
- NASH je PPAD-úplný (dokázáno v roce 2009)
- pravděpodobně neexistuje polynomiální algoritmus pro NASH
- hledání aproximace NE ve hrách s aspoň třemi hráči náleží PPAD, ale ten problém se zdá ostře těžší než PPAD
- když upravíme NASH tak, aby jeho existence nebyla zaručena, výsledný problém se často stane NP-úplný
Example: Problems from PPAD
- end-of-the-line
- NASH (bimatrix, non-degenerate)
- Sperner's lemma
- ham sandwich theorem
- Borsuk–Ulam theorem

Other notions of equilibria

Definition: $\varepsilon$ $ε$ -Nash equilibrium
- pro $\epsilon\gt 0$ $ϵ > 0$ je strategický profil $s$ $s$ ve hře $G=(P,A,u)$ $G = (P, A, u)$ $\varepsilon$ $ε$ -Nashovým ekvilibriem, pokud pro každého hráče $i\in P$ $i \in P$ a každou $s_i'\in S_i$ $s_{i}^{'} \in S_{i}$ platí $u_i(s_i;s_{-i})\geq u_i(s_i';s_{-i})-\varepsilon$ $u_{i} (s_{i}; s_{- i}) \geq u_{i} (s_{i}^{'}; s_{- i}) - ε$
  - tedy žádná jiná strategie hráči nezlepší payoff o více než $\varepsilon$
  - pro $\varepsilon=0$ bychom získali klasické NE
- výhody
  - jednoduchá definice
  - $\varepsilon$ -NE vždycky existuje podle Nashovy věty (každé NE je $\varepsilon$ -NE)
  - pokud použijeme $\varepsilon$ jako „přesnost počítače“, nemusíme počítat s iracionálními čísly
- nevýhody
  - existují $\varepsilon$ -NE, která nejsou blízko žádným NE
  - pořád je dost těžké najít $\varepsilon$ -NE
Theorem: Algorithmic aspects of $\varepsilon$ $ε$ -Nash equilibria
- nemáme FPTAS (fully polynomial-time approximation scheme) ani PTAS (polynomial-time approximation scheme)
  - FPTAS ani nemůže existovat, pokud neplatí, že $PPAD\subseteq FP$
- ale máme kvazi-polynomiální algoritmus
- věta: nechť $G$ je hra dvou hráčů v normálním tvaru, každý z hráčů má $m$ akcí takových, že výplatní matice obsahují hodnoty v intervalu $[0,1]$ , pak pro každé $\varepsilon\gt 0$ existuje algoritmus, který spočítá $\varepsilon$ -NE hry $G$ v čase $m^{O(\log m/\varepsilon^2)}$
Definition: Correlated equilibrium (CE)
- ve hře $G=(P,A,u)$ $G = (P, A, u)$ nechť $p$ $p$ je pravděpodobnostní distribuce na $A$ $A$
  - tedy $p(a)\geq 0$ pro každé $a\in A$ a $\sum p(a)=1$
- distribuce $p$ je korelované ekvilibrium (CE) v $G$ , pokud $(\forall i\in P)(\forall a_i,a_i'\in A_i):\sum_{a_{-i}\in A_{-i}}u_i(a_i;a_{-i})p(a_i;a_{-i})\geq \sum_{a_{-i}\in A_{-i}}u_i(a'_i;a_{-i})p(a_i;a_{-i})$
- možný pohled
  - jako by důvěryhodná třetí strana samplovala $a\in A$ podle známého rozdělení $p$ a soukromě by doporučila každému hráči $i$ strategii $a_i$
  - každý hráč se doporučením může, ale nemusí řídit
  - $p$ je CE, pokud každý hráč maximalizuje střední hodnotu užitku tak, že se řídí doporučením
Theorem: Properties of correlated equilibria
- každé NE je CE, takže CE vždy existuje
- každé NE $s$ je CE s distribucí $p=\prod_{i=1}^n s_i$ , takže CE může dávat lepší payoffs než NE
- CE lze spočítat v polynomiálním čase pomocí lineárního programování, jako proměnné použijeme $(p(a))_{a\in A}$

Regret minimization

Definition: Regret minimization model
- máme agenta $A$ v nepřátelském prostředí
- agent $A$ má $N$ dostupných akcí z množiny $X=\set{1,\dots,N}$
- v každém kroku $t=1,\dots,T$ $t = 1, \dots, T$
  - agent $A$ $A$ zvolí pravděpodobnostní rozdělení $p^t=(p_1^t,\dots,p_N^t)$ $p^{t} = (p_{1}^{t}, \dots, p_{N}^{t})$ nad $X$ $X$
    - $p_i^t$ … pravděpodobnost, že $A$ zvolí $i$ v kroku $t$
  - pak nepřítel zvolí ztrátový vektor $\ell^t=(\ell_1^t,\dots,\ell_n^t)$ $ℓ^{t} = (ℓ_{1}^{t}, \dots, ℓ_{n}^{t})$
    - $\ell_i^t\in[-1,1]$ … ztráta (loss) akce $i$ v kroku $t$
  - agent $A$ $A$ pak prodělá ztrátu $\ell_A^t=\sum_{i=1}^N p_i^t\ell_i^t$ $ℓ_{A}^{t} = \sum_{i = 1}^{N} p_{i}^{t} ℓ_{i}^{t}$
    - to je střední hodnota ztráty agenta $A$ v kroku $t$
- kumulativní ztráta akce $i$ po $T$ krocích … $L_i^T=\sum_{t=1}^T\ell_i^t$
- kumulativní ztráta agenta $A$ … $L_A^T=\sum_{t=1}^T\ell^t_A$
- pro zjednodušení budeme často uvažovat pouze ztrátové vektory $\in\set{0,1}^N$ , ale vše lze zobecnit
Definition: External regret
- uvažujme třídu agentů $\mathcal A_X=\set{A_i:i\in X}$ $A_{X} = {A_{i} : i \in X}$
  - $A_i$ … agent, který vždy zvolí akci $i$
- external regret agenta $A$ $A$ … $R_A^T=L_A^T-\min\set{L_B^T\mid B\in \mathcal A_X}$ $R_{A}^{T} = L_{A}^{T} - min {L_{B}^{T} ∣ B \in A_{X}}$
  - tedy $R_A^T=L_A^T-\min\set{L_i^T\mid i\in X}$
Theorem: External regret as a suitable metric
- mohlo by se zdát, že $\mathcal A_X$ obsahuje příliš jednoduché agenty, ale lze ukázat, že velké comparison classes vedou k velkému regretu
- uvažujme $\mathcal A_\text{all}$ třídu agentů, kteří v každém kroku zvolí náhodou akci z $X$ (přiřadí jí pravděpodobnost 1)
- pozorování: pro libovolného agenta $A$ $A$ a každé $T\in\mathbb N$ $T \in N$ existují posloupnost $T$ $T$ ztrátových vektorů a agent $B\in\mathcal A_\text{all}$ $B \in A_{all}$ takoví, že $L_A^T-L_B^T\geq T(1-1/N)$ $L_{A}^{T} - L_{B}^{T} \geq T (1 - 1/ N)$
  - horší už to pomalu ani být nemůže
- důkaz
  - pro každé $t$ $t$ ať $i_t$ $i_{t}$ je akce s nejmenší pravděpodobností $p^t_i$ $p_{i}^{t}$
    - $p_{i_t}^t$ bude nejvýše $1/N$ (kdyby měly všechny akce stejnou pravděpodobnost)
  - nastavíme $\ell_{i_t}^t=0$ a $\ell_i^t=1$ každému $i\neq i_t$
  - $p_{i_t}^t\leq 1/N\implies\ell_A^t\geq 1-1/N\implies L_A^T\geq T(1-1/N)$
  - algoritmus $B\in\mathcal A_\text{all}$ , který v kroku $t$ zvolí akci $i_t$ s pravděpodobností 1 bude mít kumulativní ztrátu $L_B^T=0$
Algorithm: Greedy algorithm
- budeme vybírat akci s nejmenší kumulativní ztrátou $L_i^{t-1}$ v kroku $t-1$
- nejprve zvolíme první akci (s pravděpodobností 1), pak vždycky vezmeme první z akcí s minimální kumulativní ztrátou (s pravděpodobností 1)
  - $S^{t-1}$ … množina akcí s minimální kumulativní ztrátou (v kroku $t-1$ )
- tvrzení: pro libovolnou posloupnost ztrátových vektorů z $\set{0,1}^N$ ${0, 1}^{N}$ bude kumulativní ztráta hladového (greedy) algoritmu v čase $T\in\mathbb N$ $T \in N$ splňovat $L_\text{Greedy}^T\leq N\cdot L_\text{min}^T+(N-1)$ $L_{Greedy}^{T} \leq N \cdot L_{min}^{T} + (N - 1)$
  - přičemž $L^T_\text{min}=\min\set{L_i^T\mid i\in X}$
- důkaz
  - v každém kroku $t$ $t$
    - pokud hladový algoritmus prodělá ztrátu 1 a $L_\text{min}^t$ se nezvýší, pak alespoň jedna akce zmizí z $S^t$ v dalším kroku
    - to se stane nejvýše $N$ -krát a pak se $L_\text{min}^t$ zvýší o 1
  - tedy mezi dvěma zvýšeními $L_\text{min}^t$ prodělá algoritmus ztrátu nejvýše $N$
  - z toho vyplývá $L^T_\text{Greedy}\leq N\cdot L^T_\text{min}+N-|S^T|\leq N\cdot L_\text{min}^T+(N-1)$
- to je docela slabé, protože $A$ $A$ tak může být přibližně $N$ $N$ -krát horší než nejlepší akce
  - ale žádný deterministický algoritmus nemůže být o moc lepší
Algorithm: Randomized greedy algorithm
- přidáme „náhodu“ – uniformně náhodně vybereme z těch s minimální kumulativní ztrátou
- $p^1$ tentokrát nastavíme na $(1/N,\dots,1/N)$
- v dalších krocích vždy všem prvkům množiny $S^{t-1}$ $S^{t - 1}$ nastavíme pravděpodobnost na $1/|S^{t-1}|$ $1/∣ S^{t - 1} ∣$ (ostatní budou mít nulovou)
  - $S^{t-1}$ … množina akcí s minimální kumulativní ztrátou (v kroku $t-1$ )
- tvrzení: pro libovolnou posloupnost ztrátových vektorů z $\set{0,1}^N$ bude kumulativní ztráta $L_{RG}^T$ randomizovaného hladového algoritmu v čase $T\in\mathbb N$ splňovat $L_{RG}^T\leq (1+\ln N)\cdot L_\text{min}^T+\ln N$
- důkaz
  - postupujeme jako v důkazu hladového algoritmu
  - jakou ztrátu algoritmus nasbírá mezi zvýšeními $L_\text{min}^t$ ?
  - pokud se $S^t$ v určitém kroku (který je někde mezi dvěma zvýšeními $L_\text{min}^t$ ) zmenší o $k$ , znamená to, že ztráta algoritmu v tomhle kroku byla $k/n'$ (kde $n'$ je původní velikost $S^t$ )
  - zjevně $k/n'=k\cdot\frac 1{n'}\leq\underbrace{\frac1{n'}+\frac1{n'-1}+\dots+\frac1{n'-k+1}}_k$
  - mezi dvěma zvýšeními $L_\text{min}^t$ se $S^t$ může zmenšit z velikosti $N$ na 1, takže za tu dobu může být ztráta nejvýše $\frac1N+\frac1{N-1}+\dots+\frac11\leq 1+\ln N$
  - proto $L_{RG}^T\leq (1+\ln N)\cdot L_\text{min}^T+\frac1N+\frac1{N-1}+\dots+\frac1{|S^T|+1}\leq (1+\ln N)\cdot L_\text{min}^T+\ln N$
Algorithm: Polynomial weights algorithm
- vstup: množina akcí $X=\set{1,\dots,N}$ , $T\in\mathbb N$ a $\eta\in(0,\frac12]$
- výstup: pravděpodobnostní distribuce $p^t$ pro každé $t\in\set{1,\dots,T}$
- algoritmus
  - $\forall i\in X:w_i^1\leftarrow 1$
  - $p^1\leftarrow(1/N,\dots,1/N)$
  - pro $t=2,\dots,T$ $t = 2, \dots, T$
    - $\forall i\in X:w_i^t\leftarrow w_i^{t-1}(1-\eta\ell_i^{t-1})$
    - $\forall i\in X:p_i^t\leftarrow w_i^t/W^t$ $\forall i \in X : p_{i}^{t} \leftarrow w_{i}^{t} / W^{t}$
      - kde $W^t=\sum_j w_j^t$ (normalizační konstanta)
- věta
  - pro $\eta\in(0,\frac12]$ , libovolnou posloupnost ztrátových vektorů z $[-1,1]^N$ a libovolnou akci $k\in X$ platí, že kumulativní ztráta $L_{PW}^T$ algoritmu polynomiálních vah splňuje $L^T_{PW}\leq L_k^T+\eta Q_k^T+\ln N/\eta$
  - přičemž $Q_k^T=\sum_{t=1}^T(\ell_k^t)^2$
  - zejména pokud $T\geq 4\ln N$ , pak volbou $\eta=\sqrt{\ln N/T}$ a přihlédnutím k $Q_k^T\leq T$ získáme $L_{PW}^T\leq L_\text{min}^T+2\sqrt{T\ln N}$
- důkaz
  - pro krok $t$ máme $\ell_{PW}^t=\sum_{i=1}^N w_i^t\ell_i^t/W^t$
  - váha $w_i^t$ každé akce $i$ se násobí $(1-\eta\ell^{t-1}_i)$ v kroku $t$ , proto $W^{t+1}=W^t-\sum_{i=1}^N\eta w_i^t\ell_i^t=W^t(1-\eta\ell_{PW}^t)$
  - zjevně $W^1=\sum_i w^1_i=N$
  - použijeme $\forall z\in\mathbb R:1-z\leq e^{-z}$ $W^{T+1}=W^1\prod_{t=1}^T(1-\eta\ell_{PW}^t)\leq N\prod_{t=1}^Te^{-\eta\ell_{PW}^t}=Ne^{-\eta\sum_{t=1}^T\ell^t_{PW}}$
  - zlogaritmujeme $\ln W^{T+1}\leq\ln N-\eta\sum_{t=1}^T\ell_{PW}^t=\ln N-\eta L_{PW}^T$
  - pro horní odhad máme $W^{T+1}\geq w_k^{T+1}$
  - také platí $w_k^{T+1}=\prod_{t=1}^T(1-\eta\ell_k^t)$
  - použijeme $\forall z\leq\frac12:\ln(1-z)\geq -z-z^2$ $\ln W^{T+1}\geq \ln w_k^{T+1}=\sum_{t=1}^T\ln(1-\eta\ell_k^t)\geq-\eta L_k^T-\eta^2Q_k^T$
  - oba odhady zkombinujeme $-\eta L_k^T-\eta^2Q_k^t\leq \ln N-\eta L_{PW}^T$
- poznámky
  - tenhle algoritmus produkuje velmi dobrý external regret – time-averaged external regret jde k nule
  - odhad $L_{PW}^T\leq L_\text{min}^T+2\sqrt{T\ln N}$ je v podstatě optimální
  - tvrzení: pro $N$ a $T\lt\lfloor\log_2 N\rfloor$ existuje stochastické generování ztrát takové, že pro každý online algoritmus $A$ máme $\mathbb E[L_A^T]\geq T/2$ , a přesto $L_\text{min}^T=0$
  - tvrzení: v případě $N=2$ akcí existuje stochastické generování ztrát takové, že pro každý online algoritmus $A$ máme $\mathbb E[L_A^T-L_\text{min}^T]\geq\Omega(\sqrt{T})$
Algorithm: No-regret dynamics
- hráči ve hře v normálním tvaru můžou hrát proti sobě tak, že vybírají akce podle algoritmu polynomiálních vah
- vstup: $G=(P,A,C)$ $G = (P, A, C)$ hra $n$ $n$ hráčů, $T\in\mathbb N$ $T \in N$ a $\varepsilon\gt 0$ $ε > 0$
  - místo užitku používáme cost funkci $C$
- výstup: pravděpodobnostní rozdělení $p_i^t$ na $A_i$ pro každé $i\in P$ a $t\in\set{1,\dots,T}$
- pro každý krok $t=1,\dots,T$ $t = 1, \dots, T$
  - každý hráč $i\in P$ nezávisle vybere smíšenou strategii $p_i^t$ pomocí algoritmu s průměrným regretem nejvýše $\varepsilon$ (kde akce odpovídají čistým strategiím)
  - každý hráč $i\in P$ získá ztrátový vektor $\ell_i^t$ , kde $\ell_i^t(a_i)=\mathop{\mathbb E}_{a_{-i}^t\sim p_{-i}^t}[C_i(a_i;a_{-i}^t)]$ pro rozdělení $p_{-i}^t=\prod_{j\neq i}p_j^t$

Applications of regret minimization

Theorem: Modern proof of the Minimax Theorem
- mějme hru s nulovým součtem $G=(\set{1,2},A,C)$ , kde $A_1=\set{a_1,\dots,a_m}$ , $A_2=\set{b_1,\dots,b_n}$
- hra je reprezentována maticí $M$ s rozměry $m\times n$ , kde $M_{ij}=-C_1(a_i,b_j)=C_2(a_i,b_j)\in[-1,1]$
- střední hodnota ceny $C_2(s)$ pro druhého hráče se rovná $x^TMy$ , kde $x,y$ jsou vektory smíšených strategií
- minimaxová věta říká $\max_{x\in S_1}\min_{y\in S_2}x^TMy=\min_{y\in S_2}\max_{x\in S_1}x^TMy$
- důkaz
  - nerovnost $\max_x\min_y x^TMy\leq \min_y\max_x x^TMy$ je snadná, protože je horší být druhý na tahu
  - nyní dokažme $\max_x\min_y x^TMy\geq \min_y\max_x x^TMy$
  - zvolíme parametr $\varepsilon\in (0,1]$ a spustíme no-regret dynamics pro dostatečný počet kroků $T$ , aby oba hráči měli průměrný expected external regret nejvýše $\varepsilon$
  - s algoritmem polynomiálních vah můžeme nastavit $T=4\ln(\max\set{m,n})/\varepsilon^2$ $T = 4 ln (max {m, n}) / ε^{2}$
    - jelikož $L_{PW}^T\leq L_\text{min}^T+2\sqrt{T\ln N}$
    - tedy regret za jeden časový krok je $2\sqrt{\ln N/T}=2\sqrt{\ln(\max\set{m,n})/T}$
  - $p^1,\dots,p^T$ jsou strategie prvního hráče, $q^1,\dots,q^T$ druhého
  - jako $\overline x=\frac1T\sum_t p^t$ a $\overline y=\frac1T\sum_tq^t$ označíme time-averaged strategie hráčů
  - time-averaged expected payoff prvního hráče je $v=\frac1T\sum_t (p^t)^TMq^t$
  - jako $e_i$ $e_{i}$ označíme vektor čisté strategie $a_i$ $a_{i}$
    - $e_i=(0,\dots,0,1,0,\dots,0)$
  - jelikož external regret prvního hráče je nejvýše $\varepsilon$ , získáme $e_i^TM\overline y=\frac1T\sum_{t=1}^Te_i^TMq^t\leq\frac1T\sum_{t=1}^T(p^t)^TMq^t+\varepsilon=v+\varepsilon$
  - každá strategie $x\in S_1$ je konvexní kombinace vektorů $e_i$ , takže z linearity střední hodnoty získáme $x^TM\overline y\leq v+\varepsilon$ , podobně $(\overline x)^TMy\geq v-\varepsilon$ pro každé $y\in S_2$
  - když to všechno poskládáme, získáme $\max_x\min_y x^TMy\geq \min_y(\overline x)^TMy\geq v-\varepsilon\geq\max_x x^TM\overline y-2\varepsilon\geq\min_y\max_xx^TMy-2\varepsilon$
  - pro $T\to\infty$ získáme $\varepsilon\to 0$ , čímž dosáhneme požadované nerovnosti
Definition: Coarse correlated equilibrium (CCE)
- hrubé korelované ekvilibrium (CCE) $(\forall i\in P)(\forall a'_i\in A_i):\sum_{a\in A}C_i(a)p(a)\leq\sum_{a\in A}C_i(a'_i;a_{-i})p(a)$
  - jinak také $(\forall i\in P)(\forall a_i'\in A_i):\mathop{\mathbb E}_{a\sim p}[C_i(a)]\leq\mathop{\mathbb E}_{a\sim p}[C_i(a_i';a_{-i})]$
- pro srovnání: korelované ekvilibrium (CE) $(\forall i\in P)(\forall a_i,a_i'\in A_i):\sum_{a_{-i}\in A_{-i}}C_i(a_i;a_{-i})p(a_i;a_{-i})\leq \sum_{a_{-i}\in A_{-i}}C_i(a'_i;a_{-i})p(a_i;a_{-i})$
  - jinak také $(\forall i\in P)(\forall a_i,a_i'\in A_i):\mathop{\mathbb E}_{a\sim p}[C_i(a)\mid a_i]\leq\mathop{\mathbb E}_{a\sim p}[C_i(a_i';a_{-i})\mid a_i]$
- rozdíl mezi CCE a CE
  - u CE řešíme, jestli je pro hráče výhodné řídit se doporučením poté, co se doporučení dozví
  - u CCE se hráč musí rozhodnout už předtím, než se doporučení dozví, jestli bude ochotný hrát podle něj
- pro $\varepsilon\gt 0$ , pravděpodobnostní distribuce $p$ na $A$ je $\varepsilon$ -hrubé korelované ekvilibrium ( $\varepsilon$ -CCE), pokud $\mathbb E_{a\sim p}[C_i(a)]\leq \mathbb E_{a\sim p}[C_i(a_i';a_{-i})]+\varepsilon$
Theorem: Converging to CCE
- věta
  - mějme libovolné $G=(P,A,C)$ , $\varepsilon\gt 0$ a $T=T(\varepsilon)\in\mathbb N$
  - pokud má po $T$ krocích no-regret dynamics každý hráč $i\in P$ time-averaged expected regret nejvýše $\varepsilon$ , pak $p$ je $\varepsilon$ -CCE
  - přičemž $p^t=\prod_{i=1}^np_i^t$ (součin přes všechny hráče) a $p=\frac1T\sum_{t=1}^T p^t$
- důkaz
  - chceme ukázat $\mathbb E_{a\sim p}[C_i(a)]\leq \mathbb E_{a\sim p}[C_i(a_i';a_{-i})]+\varepsilon$
  - z definice $p$ $p$ rozepíšeme
    - $\mathbb E_{a\sim p}[C_i(a)]=\frac1T\sum_t \mathbb E_{a\sim p^t}[C_i(a)]$
    - $\mathbb E_{a\sim p}[C_i(a_i';a_{-i})]=\frac1T\sum_t\mathbb E_{a\sim p^t}[C_i(a_i';a_{-i})]$
  - pravé strany jsou time-averaged expected costs hráče $i$ (když hraje podle algoritmu nebo když hraje vždycky $a_i'$ )
  - každý hráč má regret nejvýše $\varepsilon$ , proto $\frac1T\sum_t \mathbb E_{a\sim p^t}[C_i(a)]\leq\frac1T\sum_t \mathbb E_{a\sim p^t}[C_i(a_i';a_{-i})]+\varepsilon$
  - to ověřuje $\varepsilon$ -CCE podmínku pro $p=\frac1T\sum_{t=1}^T p_t$
Definition: Internal and swap regret
- modifikační pravidlo je funkce $F:X\to X$ $F : X \to X$
  - budeme modifikovat posloupnost $(p^t)_{t=1}^T$ $(p^{t})_{t = 1}^{T}$ pomocí $F$ $F$
    - modifikovaný agent bude hrát $F(i)$ , kdykoliv původní agent hrál $i$
    - posloupnost $(p^t)$ nahradíme posloupností $(f^t)$ , kde $f^t_i=\sum_{j:F(j)=i}p_j^t$
  - kumulativní ztráta agenta $A$ modifikovaného pravidlem $F$ bude $L_{A,F}^T=\sum_{t=1}^T\sum_{i=1}^N f_i^t\ell_i^t$
  - pro danou množinu modifikačních pravidel $\mathcal F$ můžeme srovnat agenta $A$ s jeho modifikacemi pravidly z $\mathcal F$ , tím dostaneme další pohledy na regret
- external regret
  - $\mathcal F^{ex}=\set{F_i\mid i\in X}$ , kde $F_i$ mapuje vše na $i$
  - $R^T_{A,\mathcal F^{ex}}=\max_{F\in\mathcal F^{ex}}\set{L_A^T-L_{A,F}^T}=\max_{j\in X}\set{\sum_t((\sum_{i\in X}p_i^t\ell_i^t)-\ell_j^t)}$
- internal regret
  - $\mathcal F^{in}=\set{F_{ij}\mid (i,j)\in X^2\land i\neq j}$ $F^{in} = {F_{ij} ∣ (i, j) \in X^{2} \land i \neq = j}$
    - $F_{ij}(i)=j$
    - $\forall i'\neq i:F_{ij}(i')=i'$
  - $R^T_{A,\mathcal F^{in}}=\max_{i,j\in X}\set{\sum_t p_i^t(\ell_i^t-\ell_j^t)}$
- swap regret
  - $\mathcal F^{sw}$ … množina všech modifikačních pravidel
  - $R^T_{A,\mathcal F^{sw}}=\sum_{i=1}^N\max_{j\in X}\set{\sum_t p_i^t(\ell_i^t-\ell_j^t)}$
- jelikož $\mathcal F^{ex}\subseteq\mathcal F^{sw}$ a $\mathcal F^{in}\subseteq\mathcal F^{sw}$ , tak external a internal regret budou nutně menší nebo rovny swap regretu
Theorem: Reduction from external regret to swap regret
- máme algoritmus polynomiálních vah, který umí zajistit libovolně malý external regret
- pro swap regret takový algoritmus zkonstruujeme pomocí black-box redukce
- definice: $R$ -external regret algoritmus $A$ garantuje, že pro každou posloupnost ztrátových vektorů $(\ell^t)_{t=1}^t$ a pro každou akci $j\in X$ budeme mít $L_A^T=\sum_t\ell_A^t\leq \sum_t\ell_j^t+R=L_j^T+R$
- věta
  - pro každý $R$ -external regret algoritmus $A$ existuje algoritmus $M=M(A)$ takový, že pro každé $F:X\to X$ a $T\in\mathbb N$ platí $L_M^T\leq L_{M,F}^T+NR$
  - tedy že swap regret algoritmu $M$ je nejvýše $NR$
- důkaz
  - mějme $N$ $N$ kopií algoritmu $A$ $A$ , označíme je jako $A_1,\dots,A_N$ $A_{1}, \dots, A_{N}$
    - algoritmus $M$ konstruujeme jako jejich kombinaci
  - v každém kroku $k$ $k$ každý $A_i$ $A_{i}$ vrací pravděpodobností rozdělení $q_i^t$ $q_{i}^{t}$
    - přičemž $q^t_{i,j}$ je pravděpodobnost, kterou $A_i$ přiřazuje akci $j\in X$
    - nechť $Q^t$ je matice $N\times N$ taková, že $Q_{ij}^t=q_{i,j}^t$
  - zkonstruujeme pravděpodobnostní rozdělení $p^t$ $p^{t}$ takové, že $(p^t)^T=(p^t)^TQ^t$ $(p^{t})^{T} = (p^{t})^{T} Q^{t}$
    - tedy $\forall j:p_j^t=\sum_{i=1}^Np_i^tq_{i,j}^t$
    - lze ukázat, že $p^t$ existuje a lze ho efektivně spočítat (je to stacionární distribuce markovského řetězce)
    - díky téhle volbě můžeme volbu akcí uvažovat dvěma způsoby – buď akci zvolíme s pravděpodobností $p^t_j$ nebo nejprve zvolíme algoritmus $A_i$ s pravděpodobností $p_i^t$ a pak použijeme algoritmus $A_i$ , aby zvolil $j$ s pravděpodobností $q^t_{i,j}$
  - když získáme ztrátový vektor $\ell^t$ $ℓ^{t}$ , pro každé $i\in X$ $i \in X$ přiřadíme algoritmu $A_i$ $A_{i}$ ztrátový vektor $p_i^t\ell^t$ $p_{i}^{t} ℓ^{t}$
    - tak $A_i$ prodělá ztrátu $(p_i^t\ell^t)\cdot q_i^t=p_i^t(q_i^t\cdot\ell^t)$
    - jelikož $A_i$ je $R$ -external regret algoritmus, platí $\forall j\in X:\sum_{t=1}^T p_i^t(q_i^t\cdot \ell^t)\leq\sum_t p_i^t\ell_j^t+R$
  - když posčítáme ztráty všech algoritmů v kroku $t$ $t$ , dostaneme celkovou ztrátu $\sum_{i=1}^N p_i^t(q_i^t\cdot\ell^t)=(p^t)^TQ^t\ell^t$ $\sum_{i = 1}^{N} p_{i}^{t} (q_{i}^{t} \cdot ℓ^{t}) = (p^{t})^{T} Q^{t} ℓ^{t}$
    - díky volbě $p^t$ máme $(p^t)^T=(p^t)^TQ^t$
    - proto se celková ztráta v kroku $t$ rovná $p^t\cdot\ell^t$ , což je reálná ztráta algoritmu $M$ v kroku $t$
  - nyní posčítáme za celou dobu běhu (z $R$ $R$ -external regret) přes všechny algoritmy $L_M^T=\sum_{i=1}^N\sum_{t=1}^T p_i^t(q_i^t\cdot \ell^t)\leq\sum_{i=1}^N\sum_{t=1}^T p_i^t\ell_{F(i)}^t+NR=L_{M,F}^T+NR$
    - kde $F$ je libovolná funkce $F:X\to X$ (v definici $R$ -external regret je tam libovolné $j$ )
  - použijeme-li algoritmus polynomiálních vah jako $A$ $A$ , získáme algoritmus se swap regret nejvýše $O(N\sqrt{T\log N})$ $O (N T lo g N)$
    - tedy průměrný swap regret jde k nule s $T\to\infty$
Algorithm: No-swap-regret dynamics
- jako no-regret, akorát je tam swap regret
- vstup: $G=(P,A,C)$ hra $n$ hráčů, $T\in\mathbb N$ a $\varepsilon\gt 0$
- výstup: pravděpodobnostní rozdělení $p_i^t$ na $A_i$ pro každé $i\in P$ a $t\in\set{1,\dots,T}$
- pro každý krok $t=1,\dots,T$ $t = 1, \dots, T$
  - každý hráč $i\in P$ nezávisle vybere smíšenou strategii $p_i^t$ pomocí algoritmu s průměrným swap regretem nejvýše $\varepsilon$ (kde akce odpovídají čistým strategiím)
  - každý hráč $i\in P$ získá ztrátový vektor $\ell_i^t$ , kde $\ell_i^t(a_i)=\mathop{\mathbb E}_{a_{-i}^t\sim p_{-i}^t}[C_i(a_i;a_{-i}^t)]$ pro rozdělení $p_{-i}^t=\prod_{j\neq i}p_j^t$
Theorem: Converging to CE
- věta
  - mějme libovolné $G=(P,A,C)$ , $\varepsilon\gt 0$ a $T=T(\varepsilon)\in\mathbb N$
  - pokud má po $T$ krocích no-swap-regret dynamics každý hráč $i\in P$ time-averaged expected regret nejvýše $\varepsilon$ , pak $p$ je $\varepsilon$ -CE
  - přičemž $p^t=\prod_{i=1}^np_i^t$ (součin přes všechny hráče) a $p=\frac1T\sum_{t=1}^T p^t$
- důkaz
  - chceme ukázat $\mathbb E_{a\sim p}[C_i(a)]\leq \mathbb E_{a\sim p}[C_i(F(a_i);a_{-i})]+\varepsilon$
  - z definice $p$ $p$ rozepíšeme
    - $\mathbb E_{a\sim p}[C_i(a)]=\frac1T\sum_t \mathbb E_{a\sim p^t}[C_i(a)]$
    - $\mathbb E_{a\sim p}[C_i(F(a_i);a_{-i})]=\frac1T\sum_t \mathbb E_{a\sim p^t}[C_i(F(a_i);a_{-i})]$
  - pravé strany jsou time-averaged expected costs hráče $i$ (když hraje podle algoritmu nebo když hraje vždycky $F(a_i)$ místo $a_i$ )
  - každý hráč má regret nejvýše $\varepsilon$ , proto $\frac1T\sum_t \mathbb E_{a\sim p^t}[C_i(a)]\leq\frac1T\sum_t \mathbb E_{a\sim p^t}[C_i(F(a_i);a_{-i})]+\varepsilon$
  - to ověřuje $\varepsilon$ -CE podmínku pro $p=\frac1T\sum_{t=1}^T p_t$

Games in extensive form

Definition: Extensive game, (im)perfect-information game
- hra v rozšířené (explicitní) formě
  - odpovídá orientovanému stromu, jehož vrcholy představují stavy hry
  - strom kóduje celou historii hry
  - hra začíná v kořeni stromu a končí v listu, kde každý hráč získá výplatu
  - hrana stromu odpovídá tomu, že se jeden hráč přesouvá z jednoho stavu hry do druhého
  - vrcholy, které nejsou listy, se označují jako rozhodovací uzly
  - tahy, které hráč v daném stavu může provést, odpovídají výstupním hranám daného rozhodovacího uzlu
- hra s dokonalou informací – všichni hráči vědí, v jakém jsou stavu
- hra s nedokonalou informací – hráči mají jenom částečnou znalost stavu hry
  - rozdělíme rozhodovací uzly na informační množiny
    - uzly v jedné informační množině patří stejnému hráči a mají stejné tahy
    - hráč ví, v jaké informační množině se nachází, ale nedokáže určit, v jakém je uzlu
  - množina informačních množin hráče $i$ se označuje jako $H_i$
  - pro $h\in H_i$ nechť $C_h$ je množina možných tahů z $h$
Definition: Strategies in extensive games
- čistá (pure) strategie hráče $i$ $i$
  - přesný popis, jakou akci zvolit v každé informační množině hráče $i$
  - pomocí čistých strategií můžeme hru $G$ v rozšířené formě převést na hru $G'$ v normálním tvaru – prostě uděláme tabulku všech čistých strategií
- smíšená (mixed) strategie
  - smíšené strategie $G$ odpovídají smíšeným strategiím $G'$
  - je to pravděpodobnostní distribuce nad vektory
- behaviorální strategie hráče $i$ $i$
  - je to pravděpodobnostní distribuce na $C_h$ pro každé $h\in H_i$
  - je to vektor pravděpodobnostních distribucí
  - hráč se v každé informační množině rozhoduje nezávisle
  - na rozdíl od smíšené strategie se hráč může rozhodnout různě, když do $h$ $h$ přijde vícekrát
    - ve hře s dokonalou pamětí hráč nemůže do jedné $h$ přijít vícekrát, proto tam pojmy smíšené a behaviorální strategie splývají (viz Kuhnova věta)
Definition: Games of perfect recall, Kuhn’s theorem
- posloupnost $\sigma_i(t)$ $σ_{i} (t)$ tahů hráče $i$ $i$ do uzlu $t$ $t$ je posloupnost jeho tahů (nehledě na tahy ostatních hráčů) po jedinečné cestě z kořene stromu do $t$ $t$
  - prázdná posloupnost se značí $\emptyset$
- hráč $i$ $i$ má dokonalou paměť (perfect recall), právě když pro každé $h\in H_i$ $h \in H_{i}$ a libovolné $t,t'\in h$ $t, t^{'} \in h$ platí $\sigma_i(t)=\sigma_i(t')$ $σ_{i} (t) = σ_{i} (t^{'})$
  - v takovém případě používáme $\sigma_h$ k označení jedinečné posloupnosti vedoucí do libovolného uzlu $t\in h$
  - kdyby rovnost neplatila a hráč by si pamatoval historii, byl by schopen rozhodnout, zda se nachází v $t$ $t$ nebo v $t'$ $t^{'}$
    - podle definice dané hry jsou ale $t,t'$ ve stejné informační množině, tedy je hráč nedovede rozlišit
    - proto zjevně nemá dokonalou paměť – je to ale vlastnost designu hry, ne hráče
- $G$ $G$ je hra s dokonalou pamětí, pokud má každý hráč dokonalou paměť
  - žádný hráč nezapomíná informace, které znal o svých dosavadních tazích
  - každá hra s dokonalou informací je hra s dokonalou pamětí
- Kuhnova věta
  - ve hře s dokonalou pamětí může být každá smíšená strategie daného hráče nahrazena ekvivalentní behaviorální strategií a libovolná behaviorální strategie může být nahrazena ekvivalentní smíšenou strategií
Definition: Sequence form
- sekvenční forma (reprezentace posloupnostmi) je čtveřice $(P,S,u,\mathcal C)$
- $P$ … množina $n$ hráčů
- $S=(S_1,\dots,S_n)$ , kde $S_i$ je množina posloupností $i$ -tého hráče
- $u=(u_1,\dots,u_n)$ , kde $u_i:S\to \mathbb R$ je výplatní funkce $i$ -tého hráče
- $\mathcal C=(\mathcal C_1,\dots,\mathcal C_n)$ , kde $\mathcal C_i$ je množina lineárních omezujících podmínek nad realizačními parvděpodobnostmi $i$ -tého hráče
- posloupnosti $S_i$ $S_{i}$
  - libovolná posloupnost z $S_i$ je buď prázdná $\emptyset$ , nebo je jednoznačně určena posledním tahem $c$ v informační množině $h$
  - $S_i=\set\emptyset\cup\set{\sigma_hc\mid h\in H_i,\,c\in C_h}$
  - $|S_i|=1+\sum_{h\in H_i}|C_h|$ , což je lineární vzhledem k velikosti stromu
- výplatní funkce $u_i$ $u_{i}$
  - mějme hráče $i$ a posloupnosti $\sigma=(\sigma_1,\dots,\sigma_n)\in S$
  - pokud se po tom, co každý hráč $j$ zahraje svou sekvenci $\sigma_j$ , hra dostane do listu $\ell$ , rovná se výplatní funkce $u_i(\sigma)$ hodnotě $u_i(\ell)$
  - jinak $u_i(\sigma)=0$
  - výplatní funkce lze popisovat (řídkými) maticemi – pokud jsou hráči dva, používají se matice $A,B$
- realizační plán behaviorální strategie $\beta_i$ $β_{i}$ pro hráče $i$ $i$ je zobrazení $x:S_i\to [0,1]$ $x : S_{i} \to [0, 1]$ , definované jako $x(\sigma_i)=\prod_{c\in\sigma_i}\beta_i(c)$ $x (σ_{i}) = \prod_{c \in σ_{i}} β_{i} (c)$
  - realizační plán je pravděpodobnost, že hráč zahraje určitou posloupnost, pokud hraje danou behaviorální strategii
  - ekvivalentně můžeme použít lineární rovnice
    - realizační plán hráče $i$ je zobrazení $x: S_i\to[0,1]$ splňující $x(\emptyset)=1$ a $\sum_{c\in C_h}x(\sigma_hc)=x(\sigma_h)$ pro každé $h\in H_i$
    - $\mathcal C_i$ je množina těchto rovnic
- omezující podmínky $\mathcal C_i$ $C_{i}$
  - lze je zapsat jako $Ex=e,\;x\geq 0$
  - $E$ má $1+|H_i|$ řádků
  - první řádek rovnice $Ex=e$ odpovídá $x(\emptyset)=1$
  - další řádky odpovídají $-x(\sigma_h)+\sum_{c\in C_h}x(\sigma_hc)=0$ pro každé $h\in H_i$
- realizační plán lze převést na behaviorální strategii tak, že $\beta_i(h,c)=\frac{x(\sigma_hc)}{x(\sigma_h)}$
Theorem: Using the sequence form to find NE
- mohli bychom $G$ převést na $G'$ v normálním tvaru a použít Lemke–Howsonův algoritmus, ale počet akcí v $G'$ je exponenciální vůči velikosti $G$ , takže by byl počet kroků algoritmu dvojitě exponenciální → proto jsme si definovali sekvenční formu
- best responses
  - pro pevný realizační plán $y$ druhého hráče spočítáme best response $x$ prvního hráče
  - $x$ $x$ je řešení lineárního programu $P$ $P$
    - $\max x^TAy$ za podmínek $Ex=e,\;x\geq 0$
  - duál $D$ $D$ má tvar
    - $\min e^Tu$ za podmínky $E^Tu\geq Ay$
- hry s nulovým součtem
  - použijeme větu o dualitě na $P$ a $D$ , tím dostaneme lineární program pro nalezení NE
  - druhý hráč chce minimalizovat $x^TAy$ , což se z duality rovná $e^Tu$ , pokud první hráč maximalizuje svůj payoff $x^TAy$
  - věta: Nashova ekvilibria hry dvou hráčů v rozšířené formě s nulovým součtem s dokonalou pamětí jsou řešení lineárního programu
    - $\min_{u,y}e^Tu$ za podmínek $Fy=f,\;E^Tu-Ay\geq 0,\;y\geq 0$
  - duál k tomuto programu najde realizační plán $x$ pro prvního hráče
  - počet nenulových položek v maticích $E,F,A$ je lineární vůči velikosti stromu, takže lineární programy lze vyřešit v polynomiálním čase vůči velikosti hry → to je exponenciální zlepšení
- hry dvou hráčů
  - věta: dvojice $(x,y)$ realizačních plánů ve hře dvou hráčů v extenzivní formě s dokonalou pamětí je Nashovo ekvilibrium, právě když existují vektory $u,v$ takové, že $\begin{aligned}x^T(E^Tu-Ay)=0,\quad& y^T(F^Tv-B^Tx)=0 \\ Ex=e,\;x\geq 0,\quad& Fy=f,\;y\geq 0 \\ E^Tu-Ay\geq 0,\quad& F^Tv-B^Tx\geq 0\end{aligned}$
  - to není lineární program, ale problém lineární komplementarity (linear complementarity problem, LCP)
  - lze ho řešit pomocí Lemkeho algoritmu, který má exponenciálně mnoho kroků, ale je exponenciálně rychlejší, než kdybychom použili Lemke–Howsonův algoritmus na indukované hře v normálním tvaru

Mechanism design

Definition: Single item auction
- v jednopoložkové aukci nabízí prodejce jeden kus zboží $n$ zájemcům
- každý zájemce $i$ má svou tajnou valuaci $v_i$ , kterou je ochoten zaplatit za zboží
- každý zájemce prodejci tajně sdělí svou nabídku (bid) $b_i$
- prodejce se rozhodne, který zájemce (jestli nějaký) obdrží zboží a jakou bude muset zaplatit prodejní cenu $p$
- pokud zájemce (bidder) prohraje aukci, jeho užitek $u_i$ je nulový, pokud vyhraje aukci, jeho užitek se rovná $u_i=v_i-p$
- chceme navrhnout mechanismus, který zajistí, že přidělení položky zájemci nemůže být strategicky manipulováno
Definition: Dominant strategy, social surplus, awesome auction
- dominantní strategie zájemce $i$ je strategie, která maximalizuje jeho užitek nehledě na to, co dělají ostatní zájemci
- sociální zisk (social surplus) je $\sum_{i=1}^nv_ix_i$ , kde $x_i$ je indikátor toho, zda zájemce $i$ vyhrál
- chceme, aby naše aukce byla úžasná, tedy aby garantovala:
  - DSIC (dominant-strategy incentive compatible)
    1. dominantní strategie každého zájemce je bidovat pravdivě (zvolit $b_i=v_i$ )
    2. užitek každého pravdivě bidujícího zájemce bude vždy nezáporný
  - maximalizaci sociálního zisku – pokud zájemci bidují pravdivě
  - výpočetní efektivitu – aukce by měla jít „spočítat“ v polynomiálním čase
- proč to chceme?
  - DSIC – aby mohli zájemci snadno určit bid a aby mohl prodejce při práci s výsledkem aukce předpokládat, že zájemci bidovali pravdivě
  - sociální zisk – jenom DSIC by nám nestačilo, chceme identifikovat zájemce s největší valuací
  - výpočetní efektivita je prostě praktická
Theorem: Vickrey’s auction is awesome
- DSIC
  - uvažujme hráče $i$
  - dokážeme, že jeho užitek je maximalizován pro $b_i=v_i$
  - nechť $B=\max_{j\in\set{1,\dots,n}\setminus\set{i}} b_j$
  - pokud $b_i\lt B$ , pak $i$ prohrává a jeho užitek je 0
  - pokud $b_i\geq B$ , pak $i$ vyhrává a získá užitek $v_i-B$
  - pokud $v_i\lt B$ , pak může získat nejvýše $\max\set{0,v_i-B}=0$
  - pokud $v_i\geq B$ , pak může získat nejvýše $\max\set{0,v_i-B}=v_i-B\geq 0$
  - těchto užitků dosáhne, pokud biduje pravdivě
- sociální zisk – pokud všichni bidují pravdivě, vyhraje hráč s největší valuací
- efektivita – aukce běží v lineárním čase
Definition: Single parameter environment
- $n$ zájemců, každý má soukromou valuaci $v_i$ , což je hodnota „za jednotku zboží“
- $X\subseteq\mathbb R^n$ $X \subseteq R^{n}$ … přípustná množina (množina přípustných výsledků)
  - prvky $X$ jsou vektory $x=(x_1,\dots,x_n)$ , kde $x_i$ označuje část výsledku, která se týká $i$ -tého zájemce
- sealed-bid aukce v jednoparametrovém prostředí probíhá ve třech krocích
  - vybereme nabídky $b=(b_1,\dots,b_n)$
  - alokační pravidlo
    - zvolíme přípustnou alokaci výsledku $x=x(b)$ z $X$ jako funkci nabídek $b$
  - platební pravidlo
    - zvolíme platby $p(b)=(p_1(b),\dots,p_n(b))\in\mathbb R^n$ jako funkci nabídek $b$
- dvojice $(x,p)$ tvoří mechanismus
- užitek $u_i(b)$ zájemce $i$ je $u_i(b)=v_i\cdot x_i(b)-p_i(b)$
- budeme uvažovat jenom platby $p_i(b)\in[0,b_i\cdot x_i(b)]$ $p_{i} (b) \in [0, b_{i} \cdot x_{i} (b)]$
  - nikdy nebudeme platit zájemcům
  - zájemce nikdy nebude platit vyšší jednotkovou cenu, než byla jeho nabídka (tedy pravdivě bidující bude mít nezáporný užitek)
- budeme maximalizovat sociální zisk $\sum_{i=1}^n v_i\cdot x_i(b)$
Example: Some single parameter environments
- jednopoložkové aukce
  - $X=\set{(x_1,\dots,x_n)\in\set{0,1}^n:\sum_i x_i\leq 1}$
- sponzorované hledání
  - pro $n$ zájemců máme $k$ dostupných pozic
  - každá pozice $j$ má click-through-rate $\alpha_j$ , přičemž $\alpha_1\gt\dots\gt\alpha_k\gt 0$
  - $X$ se skládá z vektorů $(x_1,\dots,x_n)$ , přičemž $x_i\in\set{\alpha_1,\dots,\alpha_k,0}$ a pokud $x_i=x_j$ , pak jsou obě nulová
  - takže hodnota slotu $j$ pro zájemce $i$ je $v_i\alpha_j$
Definition: Implementable allocation rule, monotone allocation rule
- alokační pravidlo $x$ $x$ pro jednoparametrové prostředí je implementovatelné, pokud existuje platební pravidlo $p$ $p$ takové, že $(x,p)$ $(x, p)$ je DSIC
  - alokační pravidlo „dej položku zájemci s nejvyšší nabídkou“ je v jednopoložkových aukcích implementovatelné, protože platební pravidlo „ať zaplatí druhou nejvyšší cenu“ zajišťuje DSIC
- alokační pravidlo $x$ $x$ je monotónní, pokud pro každého zájemce $i$ $i$ a všechny nabídky ostatních zájemců $b_{-i}$ $b_{- i}$ je alokace $x_i(z;b_{-i})$ $x_{i} (z; b_{- i})$ hráči $i$ $i$ neklesající vzhledem k jeho nabídce $z$ $z$
  - alokační pravidlo „dej položku zájemci s nejvyšší nabídkou“ je monotónní, alokační pravidlo „dej položku zájemci s druhou nejvyšší nabídkou“ už není
Theorem: Myerson’s lemma
- Myersonovo lemma: v jednoparametrovém prostředí platí následující tři výroky
  1. alokační pravidlo je implementovatelné, právě když je monotónní
  2. pokud je alokační pravidlo $x$ $x$ monotónní, pak existuje unikátní platební pravidlo $p$ $p$ takové, že mechanismus $(x,p)$ $(x, p)$ je DSIC
    - za předpokladu, že $b_i=0\implies p_i(b)=0$
  3. platební pravidlo $p$ je $\forall i:p_i(b_i;b_{-i})=\int_{0}^{b_i}z\cdot\frac {\text d}{\text dz} x_i(z;b_{-i})\text{ d}z$
- důkaz
  - nechť $x$ je alokační pravidlo a $p$ je platební pravidlo takové, že $(x,p)$ je DSIC
  - dokážeme všechny tři výroky naráz pomocí chytrého prohození
  - DSIC vlastnost říká, že $\forall z:u_i(z;b_{-i})=v_i\cdot x_i(z;b_{-i})-p_i(z;b_{-i})\leq v_i\cdot x_i(v_i;b_{-i})-p_i(v_i;b_{-i})$
  - mějme dvě nabídky $y,z$ $y, z$ takové, že $0\leq y\lt z$ $0 \leq y < z$
    - zájemce $i$ může mít soukromou valuaci $z$ a nepravdivě bidovat $y$
    - dosadíme do DSIC: $u_i(y;b_{-i})=z\cdot x_i(y;b_{-i})-p_i(y;b_{-i})\leq z\cdot x_i(z;b_{-i})-p_i(z;b_{-i})=u_i(z;b_{-i})$
    - taky by to mohlo být naopak, že by zájemce přestřelil svou valuaci
      - tedy $v_i=y$ a $b_i=z$
    - $u_i(z;b_{-i})=y\cdot x_i(z;b_{-i})-p_i(z;b_{-i})\leq y\cdot x_i(y;b_{-i})-p_i(y;b_{-i})=u_i(y;b_{-i})$
  - když dáme tyhle nerovnosti dohromady, získáme payment difference sandwich
    - $z\cdot (x_i(y;b_{-i})-x_i(z;b_{-i}))$ $z \cdot (x_{i} (y; b_{- i}) - x_{i} (z; b_{- i}))$
      - $\leq p_i(y;b_{-i})-p_i(z;b_{-i})$
      - $\leq y\cdot (x_i(y;b_{-i})-x_i(z;b_{-i}))$
    - takže $z\cdot\alpha\leq y\cdot\alpha$ , přičemž $y\lt z$
    - proto $\alpha=x_i(y;b_{-i})-x_i(z;b_{-i})$ musí být menší nebo rovno nule
    - tudíž $x_i(y;b_{-i})\leq x_i(z;b_{-i})$
    - proto pokud je $(x,p)$ DSIC, pak je $x$ monotónní
  - dále budeme předpokládat, že je $x$ monotónní
  - zafixujeme $i,b_{-i}$ , takže $x_i,p_i$ budou funkce $z$
  - budeme předpokládat, že $x_i$ $x_{i}$ je piecewise konstantní
    - takže se skládá z konečného počtu intervalů se „skoky“ mezi nimi
    - velikost skoku funkce $x_i$ v bodě $t$ označíme jako $\text{jump}(f,t)$
  - zafixujeme $z$ $z$ v payment difference sendviči a budeme $y$ $y$ přibližovat k $z$ $z$ (zespodu)
    - pokud $x_i$ nemá skok v $z$ , obě strany se vynulují
    - pokud $\text{jump}(x_i,z)=h\gt 0$ , obě strany půjdou k $z\cdot h$
  - tedy má-li $(x,p)$ $(x, p)$ být DISC, musí pro každé $z$ $z$ platit následující omezující podmínka funkce $p$ $p$
    - $\text{jump}(p_i,z)=z\cdot\text{jump}(x_i,z)$
  - zkombinujeme-li tuhle podmínku s původní podmínkou $p_i(0;b_{-i})=0$ $p_{i} (0; b_{- i}) = 0$ , získáme vzorec $p_i(b_i;b_{-i})=\sum_{j=1}^\ell z_j\cdot\text{jump}(x_i(\bullet;b_{-i}),z_j)$
    - kde $z_1,\dots,z_\ell$ jsou zlomy alokační funkce $x_i(\bullet;b_{-i})$ v intervalu $[0,b_i]$
    - tenhle argument by se dal zobecnit pro obecné monotónní funkce $x_i$ , ale k tomu bychom potřebovali matematickou analýzu
  - je potřeba ukázat, že pokud je $x$ $x$ monotónní, pak je $(x,p)$ $(x, p)$ opravdu DSIC
    - ukážeme to pro piecewise konstantní funkce, ale fungovalo by to i obecně
    - platba $p_i(b_i;b_{-i})$ se zjevně rovná ploše nalevo od křivky $x_i(\bullet;b_{-i})$ v intervalu $[0,b_i]$
    - připomeňme, že užitek $u_i(b_i;b_{-i})=v_i\cdot x_i(b_i;b_{-i})-p_i(b_i;b_{-i})$ $u_{i} (b_{i}; b_{- i}) = v_{i} \cdot x_{i} (b_{i}; b_{- i}) - p_{i} (b_{i}; b_{- i})$
      - tedy užitek odpovídá rozdílu obdélníku „valuace × alokováno“ a platby (tedy plochy nalevo od křivky)
    - DSIC nahlédneme rozborem případů (viz obrázek, jeho autorem je Martin Balko)

Applications of mechanism design

Definition: Bayesian model
- součástí bayesovského modelu jsou
  - jednoparametrové prostředí $(x,p)$
  - pravděpodobnostní distribuce $F_1,\dots,F_n$ $F_{1}, \dots, F_{n}$
    - $F_i$ … distribuce určující soukromou valuaci $i$ tého hráče
    - support $F_i$ je obsažen v $[0,v_\text{max}]$
    - $F_i$ má hustotní funkci $f_i$
    - jednotlivé $F_i$ jsou nezávislé, ale ne nutně stejné
- distribuce $F_1,\dots,F_n$ jsou známy návrháři mechanismu, zájemci je neznají, ale ani je znát nepotřebují, neboť uvažujeme pouze DSIC aukce a oni mají dominantní strategie
- cílem je maximalizovat střední hodnotu zisku (revenue) $\sum_{i=1}^n p_i(v)$ $\sum_{i = 1}^{n} p_{i} (v)$
  - přičemž středí hodnotu počítáme podle distribucí valuací hráčů
- to se obvykle dělá tak, že zvolíme minimální cenu
  - té se říká monopoly price
Theorem: Maximizing expected revenue
- věta
  - nechť $(x,p)$ je DSIC mechanismus v jednoparametrovém prostředí tvořící bayesovský model s $n$ zájemci a distribucemi $F_1,\dots,F_n$ , nechť $F=F_1\times\dots\times F_n$
  - pak $\mathop{\mathbb E}_{v\sim F}\left[\sum_{i=1}^np_i(v)\right]=\mathop{\mathbb E}_{v\sim F}\left[\sum_{i=1}^n \varphi_i(v_i)\cdot x_i(v) \right]$
  - kde $\varphi_i(v_i)=v_i-\frac{1-F_i(v_i)}{f_i(v_i)}$ $φ_{i} (v_{i}) = v_{i} - \frac{1 - F _{i} ( v _{i} )}{f _{i} ( v _{i} )}$ je virtuální valuace zájemce $i$ $i$
    - $f_i$ … hustota rozdělení $F_i$
    - $F_i$ … distribuční funkce (CDF) rozdělení $F_i$
- poznámky
  - tedy bychom místo maximalizace (našeho) zisku mohli maximalizovat virtuální sociální zisk
  - virtuální valuace může být i záporná, závisí jenom na $v_i$ a $F_i$ , ne na parametrech ostatních hráčů
  - jakási intuice pro virtuální valuaci
    - $v_i$ … maximální zisk, který můžeme získat od zájemce
    - $\frac{1-F_i(v_i)}{f_i(v_i)}$ … ztráta způsobená tím, že $v_i$ neznáme
- důkaz
  - $(x,p)$ je DSIC, takže budeme předpokládat $b_i=v_i$ pro každého zájemce $i$
  - podle Myersonova lemmatu $p_i(b_i;b_{-i})=\int_{0}^{b_i}z\cdot\frac {\text d}{\text dz} x_i(z;b_{-i})\text{ d}z$
  - zafixujeme zájemce $i$ $i$ a nabídky ostatních $v_{-i}$ $v_{- i}$
    - $\mathbb E[p_i(v)]=\int_0^{v_\text{max}}p_i(v)f_i(v_i)\text{ d}v_i$
  - dosadíme $p_i$ , dostaneme $\mathbb E[p_i(v)]=\int_0^{v_\text{max}}\left(\int_{0}^{v_i}z\cdot\frac {\text d}{\text dz} x_i(z;v_{-i})\text{ d}z\right) f_i(v_i)\text{ d}v_i$
  - použijeme Fubiniovu větu a obrátíme pořadí integrování $\mathbb E[p_i(v)]=\int_0^{v_\text{max}}\left(\int_{z}^{v_\text{max}}f_i(v_i)\text{ d}v_i\right) z\cdot\frac {\text d}{\text dz} x_i(z;v_{-i})\text{ d}z$
    - změnili jsme meze integrálu (?), u toho jsme použili, že $z\leq v_i$
  - $f_i$ je hustota, takže to zjednodušíme na $\mathbb E[p_i(v)]=\int_0^{v_\text{max}}(1-F_i(z))\cdot z\cdot\frac {\text d}{\text dz} x_i(z;v_{-i})\text{ d}z$
  - provedeme integraci per partes
    - $\int fg'=fg-\int f'g$
    - $f(z)=(1-F_i(z))\cdot z$
    - $g'(z)=\frac d{dz} x_i(z;v_{-i})$
  - dostaneme $[(1-F_i(z))\cdot z\cdot x_i(z;v_{-i})]_0^{v_\text{max}}-\int_0^{v_\text{max}} x_i(z;v_{-i})\cdot(1-F_i(z)-zf_i(z))\text{ d}z$ $[(1 - F_{i} (z)) \cdot z \cdot x_{i} (z; v_{- i})]_{0}^{v_{max}} - \int_{0}^{v_{max}} x_{i} (z; v_{- i}) \cdot (1 - F_{i} (z) - z f_{i} (z)) d z$
    - první člen je nulový (pro obě meze)
  - druhý člen přepíšeme na $\int_0^{v_\text{max}} (z-\frac{1-F_i(z)}{f_i(z)})x_i(z;v_{-i})f_i(z)\text{ d}z$
  - což se rovná $\int_0^{v_\text{max}} \varphi_i(z)x_i(z;v_{-i})f_i(z)\text{ d}z$
  - takže $\mathbb E[p_i(v_i;v_{-i})]=\mathbb E[\varphi_i(v_i)\cdot x_i(v_i;v_{-i})]$
  - z linearity střední hodnoty dostaneme požadovanou rovnost
Theorem: Vickrey with reserve price is optimal
- tvrzení
  - nechť $F$ je regulární pravděpodobnostní rozdělení s hustotou $f$ a valuací $\varphi$ a nechť $F_1,\dots,F_n$ jsou nezávislé pravděpodobnostní rozdělení na valuacích $n$ zájemců taková, že $F=F_1=\dots=F_n$ (a tedy $\varphi=\varphi_1=\dots=\varphi_n$ )
  - pak Vickreyho aukce s rezervní cenou $\varphi^{-1}(0)$ maximalizuje střední hodnotu zisku
- poznámky
  - $F$ je regulární, pokud $\varphi(v)$ je ostře rostoucí podle $v$
  - Vickreyho aukce s rezervní cenou $r$ $r$
    - položka se přidělí zájemci s nejvyšší nabídkou, pokud tato nabídka je větší nebo rovna $r$
    - pokud jsou všechny nabídky menší než $r$ , nikdo položku nezíská
    - vítěz musí zaplatit druhou nejvyšší nabídku nebo $r$
- důkaz
  - podle předchozí věty budeme maximalizovat střední hodnotu virtuálního sociálního zisku
  - položku dáme zájemci s nejvyšší virtuální valuací
  - pokud mají všichni zápornou virtuální valuaci, nedáme ji nikomu
  - z regularity $F$ je $\varphi$ ostře rostoucí → alokační pravidlo je monotónní → z Myersonova lemmatu máme DSIC aukci $(x,p)$
Theorem: The Bulow–Klemperer theorem
- věta
  - nechť $F$ je regulární pravděpodobnostní rozdělení
  - pak $\mathbb E_{v_1,\dots,v_{n+1}\sim F}[\text{Rev}(VA_{n+1})]\geq \mathbb E_{v_1,\dots,v_n\sim F}[\text{Rev}(OPT_{F,n})]$
  - kde $\text{Rev}(VA_{n+1})$ $Rev (V A_{n + 1})$ je zisk z Vickreyho aukce s $n+1$ $n + 1$ zájemci bez rezervy
    - tedy nezávisí na $F$
  - a $\text{Rev}(OPT_{F,n})$ $Rev (OP T_{F, n})$ je zisk z optimální aukce pro $F$ $F$ s $n$ $n$ zájemci
    - tedy Vickreyho aukce s rezervou $\varphi^{-1}(0)$
    - závisí na $F$
- důkaz
  - budeme uvažovat aukci $A$ $A$ s $n+1$ $n + 1$ zájemci
    - bude simulovat $OPT_{F,n}$ na zájemcích $1,\dots,n$
    - pokud položka nebyla nikomu přidělena, dáme ji zdarma zájemci $n+1$
  - takže $A$ z definice vždy přidělí položku a střední hodnota zisku se rovná optimální aukci na $n$ zájemcích
  - budeme chtít ukázat, že Vickreyho aukce maximalizuje střední hodnotu zisku přes všechny aukce, které přidělí položku
  - uvažujme optimální aukci (maximalizující zisk), která vždy přidělí položku
    - taková aukce ji vždy dá zájemci s nejvyšší virtuální valuací
    - z regularity a rovnosti distribucí plyne, že to bude rovněž zájemce s nejvyšší valuací
    - takovému zájemci ji dá právě Vickreyho aukce $VA_{n+1}$
  - tedy Vickreyho aukce má střední hodnotu zisku aspoň takovou jako libovolná aukce, která vždycky přidělí položku (což je třeba $A$ $A$ )
    - $\mathbb E[\text{Rev}(VA_{n+1})]\geq \mathbb E[\text{Rev}(A)]= \mathbb E[\text{Rev}(OPT_{F,n})]$
- důsledek
  - střední hodnota zisku z $VA_n$ je aspoň $\frac{n-1}{n}$ násobek střední hodnoty zisku z $OPT_{F,n}$
  - lze to dokázat podobně jako BK větu, zkonstruujeme aukci, kde budeme jednoho hráče ignorovat (pravděpodobnost, že by ji vyhrál je $\frac1n=\frac{n-1}n$ → zisk bude přibližně tolikrát menší)
Definition: Knapsack auction
- každý z $n$ zájemců má veřejně známou velikost $w_i\geq 0$ a soukromou valuaci $v_i\geq 0$
- prodejce má kapacitu $W\geq 0$
- přípustná množina $X$ $X$ se skládá z vektorů $(x_1,\dots,x_n)\in\set{0,1}^n$ $(x_{1}, \dots, x_{n}) \in {0, 1}^{n}$ takových, že $\sum_{i=1}^n x_iw_i\leq W$ $\sum_{i = 1}^{n} x_{i} w_{i} \leq W$
  - $x_i$ je indikátor toho, že zájemce $i$ vyhrál
- jak zkonstruovat úžasný mechanismus?
  - zvolíme alokaci $x(b)$ tak, abychom maximalizovali $\sum_i b_ix_i$ , tak by se při pravdivém bidování maximalizoval sociální zisk
  - alokační pravidlo je monotónní, proto nám Myersonovo lemma dá $p$ takové, že $(x,p)$ je DSIC
  - třetí podmínku úžasných aukcí ale nesplníme, protože $x$ řeší NP-těžký problém batohu
- co s tím?
  - kolidují nám druhá a třetí podmínka
  - to vyřešíme tak, že tu druhou trochu uvolníme, čímž získáme polynomiální algoritmus
  - použijeme FPTAS
Theorem: 2-approximation for knapsack auctions
- hladové alokační pravidlo
  - předpokládáme, že $\forall i: w_i\leq W$
  - nechť jsou zájemci seřazeni tak, že $\frac{b_1}{w_1}\geq\dots\geq\frac{b_n}{w_n}$
  - nejprve se budeme snažit v tomto pořadí „batoh“ naplnit co nejvíce – dokud se tam zájemci vejdou → tak získáme možné řešení
  - vrátíme buď nalezené řešení nebo zájemce s největší nabídkou – podle toho, z čeho bude větší sociální zisk
- věta: pokud jsou nabídky pravdivé (podle valuace), sociální zisk hladového alokačního pravidla je aspoň polovina maximálního možného sociálního zisku
- důkaz
  - uvažujme relaxaci problému, kde můžeme použít zlomek zájemce
  - hladové pravidlo upravíme tak, že použijeme kousek zájemce, který už by se nám nevešel
  - tak určitě najdeme optimální řešení, protože jsme si zájemce seřadili podle „hustoty“ – libovolné jiné řešení by bylo horší (formálnější důkaz ve skriptech)
  - vybrané zájemce si označíme $1,\dots,k$ , přičemž z $k$ -tého jsme použili jenom kousek
  - několik pozorování
    - sociální zisk z prvního kroku hladového pravidla (nezlomkového) je $\sum_{i=1}^{k-1}v_i$
    - sociální zisk z druhého kroku je aspoň $v_k$ (vybíráme ze maximální $v_i$ ze zájemců, které jsme nepoužili, $v_k$ patří do této množiny)
    - $(\sum_{i=1}^{k-1}v_i)+v_k\gt$ optimum
  - výsledný sociální zisk bude $\max\set{v_k,\sum_{i=1}^{k-1}v_i}$
  - to bude nutně aspoň polovina optima (to vyplývá z pozorování – celek se nedá rozdělit na dvě části menší než polovina)
Definition: Multi-parameter mechanism design
- $n$ zájemců
- konečná množina $\Omega$ výsledků
- každý zájemce $i$ má soukromou valuaci $v_i(\omega)\geq 0$ pro každý výsledek $\omega\in \Omega$
- každý zájemce $i$ odevzdá své nabídky $b_i(\omega)\geq 0$ pro každou $\omega\in\Omega$
- našim cílem je navrhnout algoritmus, který vybere výsledek $\omega\in\Omega$ , aby maximalizoval sociální zisk $\sum_i v_i(\omega)$
Theorem: VCG mechanism
- věta: v každém prostředí multi-parameter mechanism designu existuje DSIC mechanismus maximalizující sociální zisk
- idea důkazu
  - jakou ztrátu sociálního zisku způsobuje $i$ $i$ -tý zájemce ostatním?
    - třeba v jednopoložkových aukcích způsobuje vítěz ostatním ztrátu rovnou druhé nejvyšší nabídce
  - definujeme platby tak, aby se zájemci museli zajímat o ostatní
  - alokační pravidlo bude $x(b)=\text{argmax}_{\omega\in\Omega}\sum_{i=1}^n b_i(\omega)$
  - platební vzorec bude $p_i(b)=\max_{\omega\in\Omega}\left\lbrace\sum_{\substack{j=1 \\ j\neq i}}^n b_j(\omega)\right\rbrace-\sum_{\substack{j=1 \\ j\neq i}}^n b_j(\omega^*)$
    - přičemž $\omega^*=x(b)$ , tedy výsledek vybraný naším alokačním pravidlem
- důkaz
  - předpokládejme, že zájemci budou bidovat pravdivě → jaký výsledek zvolit?
  - maximalizujeme sociální zisk, takže definujeme alokační pravidlo jako $x(b)=\text{argmax}_{\omega\in\Omega}\sum_{i=1}^n b_i(\omega)$
  - teď zajistíme, aby měli zájemci motivaci bidovat pravdivě (DSIC) – zvolíme vhodné platební pravidlo
  - nechť $p_i(b)=\max_{\omega\in\Omega}\left\lbrace\sum_{\substack{j=1 \\ j\neq i}}^n b_j(\omega)\right\rbrace-\sum_{\substack{j=1 \\ j\neq i}}^n b_j(\omega^*)$ $p_{i} (b) = max_{ω \in Ω} {\sum_{j = 1 j \neq = i}^{n} b_{j} (ω)} - \sum_{j = 1 j \neq = i}^{n} b_{j} (ω^{*})$
    - „social surplus ostatních v aukci bez $i$ “ $-$ „social surplus ostatních v této aukci“
    - tedy vlastně „o kolik si ostatní pohoršili účastí $i$ “
  - lze ukázat, že $0\leq p_i(b)\leq b_i(\omega^*)$ , takže pravdiví zájemci mají garantovaný nezáporný užitek
  - zafixujeme $i$ a nabídky ostatních zájemců $b_{-i}$
  - pokud $x(b)=\omega^*$ pak se užitek $i$ -tého zájemce rovná $v_i(\omega^*)-p_i(b)$
  - což se rovná $\left(v_i(\omega^*)+\sum_{j\neq i} b_j(\omega^*)\right)-\left(\max_{\omega\in\Omega}\left\lbrace\sum_{j\neq i}b_j(\omega)\right\rbrace\right)$
  - pravý člen je nezávislý na $b_i$ , takže zájemce $i$ musí maximalizovat levý člen, pokud chce maximalizovat svůj užitek
  - zájemce $i$ ale nemůže přímo ovlivnit $\omega^*$ , jelikož ho volí mechanismus tak, aby byl součet nabídek maximální
  - zájemce $i$ chce, aby mechanismus vybral $\text{argmax}_\omega\set{v_i(\omega)+\sum_{j\neq i} b_j(\omega)}$
  - pokud $i$ biduje pravdivě, tak to přesně odpovídá naší volbě $x$ , takže pravdivé bidování maximalizuje utilitu $i$
Theorem: Revelation principle
- DSIC můžeme rozdělit na dvě části
  - každý hráč má dominantní strategii
  - dominantní strategie je přímé odhalení valuace $v_i$
- dává smysl zbavit se druhé části?
  - ne, důležitá je ta první
  - druhou část dostaneme zdarma
- věta: pro každý multi-parameter mechanismus $M$ , v němž má každý zájemce dominantní strategii nehledě na jeho soukromou valuaci, existuje ekvivalentní mechanismus $M'$ , kde má každý zájemce dominantní strategii, která přímo odhaluje jeho valuaci
- důkaz
  - použijeme simulační argument
  - pro každého zájemce $i$ mějme jeho valuace $v_i(\omega)_{\omega\in\Omega}$
  - pro každého zájemce $i$ ať $s_i(v_i(\omega)_\omega)$ je jeho dominantní strategie v mechanismu $M$
  - zkonstruujeme $M'$ $M^{'}$
    - $M'$ přijme zapečetěné nabídky $b_1(\omega)_{\omega\in\Omega},\dots,b_n(\omega)_{\omega\in\Omega}$ od všech zájemců
    - $M'$ odešle nabídky $s_1(b_1(\omega)_{\omega\in\Omega}),\dots,s_n(b_n(\omega)_{\omega\in\Omega})$ do mechanismu $M$
    - $M'$ vrátí stejný výsledek jako $M$
  - kdyby zájemce $i$ do $M'$ odevzdal jiné nabídky než $v_i(\omega)_\omega$ , hrozilo by, že bude hrát jinou strategii než $s_i(v_i(\omega)_\omega)$ , což by mu mohlo jedině snížit užitek
  - proto je přímé odhalení valuací dominantní strategie v $M'$
- příklad
  - uvažujme jednopoložkovou aukci, kde prodávající přijme nabídky $(b_1,\dots,b_n)$ a následně provede Vickreyho aukci na nabídkách $(2b_1,\dots,2b_n)$
  - dominantní strategie je zde nabídnout polovinu své hodnoty
  - z důkazu věty vyplývá, že bychom mohli zkonstruovat $M'$ , který bude nabídky hráčů půlit → pro tento $M'$ už by bylo dominantní strategií bidovat pravdivě

Survey questions

Survey: Nash equilibria
- Normal-form games
  - Normal-form game
  - Strategies
  - Expected payoff
  - Five basic games
- Nash equilibrium
  - Best response
  - Nash equilibrium
  - Nash’s Theorem
  - Pareto optimality
  - ε-Nash equilibrium
- Zero-sum games
  - Zero-sum game and its representation
  - Worst-case optimal strategies
  - Worst-case optimal strategies and NE
  - The Duality Theorem
  - The Minimax Theorem
  - Modern proof of the Minimax Theorem
- Bimatrix games
  - Bimatrix game, nondegenerate bimatrix game
  - Best response condition
  - Support enumeration
  - Best response polyhedra, best response polytope
  - NE and Best response polyhedra/polytope
  - Vertex enumeration
  - Lemke–Howson algorithm
  - Computational complexity of NASH
  - Problems from PPAD
Survey: Correlated equilibria
- Correlated equilibrium (CE)
- Properties of correlated equilibria
- Polynomial weights algorithm
- No-regret dynamics
- Coarse correlated equilibrium (CCE)
- Converging to CCE
- Internal and swap regret
- Reduction from external regret to swap regret
- No-swap-regret dynamics
- Converging to CE
Survey: Regret minimization
- Regret minimization model
- External regret
- External regret as a suitable metric
- Greedy algorithm
- Randomized greedy algorithm
- Polynomial weights algorithm
- No-regret dynamics
- Modern proof of the Minimax Theorem
- Coarse correlated equilibrium (CCE)
- Converging to CCE
- Internal and swap regret
- Reduction from external regret to swap regret
- No-swap-regret dynamics
- Converging to CE
Survey: Games in extensive form
- Extensive game, (im)perfect-information game
- Strategies in extensive games
- Games of perfect recall, Kuhn’s theorem
- Sequence form
- Using the sequence form to find NE
Survey: Mechanism design
- Single item auction
- Dominant strategy, social surplus, awesome auction
- Vickrey’s auction is awesome
- Single parameter environment
- Some single parameter environments
- Implementable allocation rule, monotone allocation rule
- Myerson’s lemma
- Bayesian model
- Maximizing expected revenue
- Vickrey with reserve price is optimal
- The Bulow–Klemperer theorem
- Knapsack auction
- 2-approximation for knapsack auctions
- Multi-parameter mechanism design
- VCG mechanism
- Revelation principle