Algorithmic Game Theory

we want to mathematically model the interactions between rational agents

• $P$ … finite set of $n$ players
• $A=A_1\times\dots\times A_n$ … set of action profiles
  • $A$ … set of all possible states of the game
  • $A_i$ … set of actions available to player $i$
• $u=(u_1,\dots,u_n)$
  • $u_i:A\to\mathbb R$ … utility function for player $i$
  • assigns happiness of each player to every possible state of the game
  • sometimes is used cost function instead, $c_i=-u_i$
• knowing the utility function, every player $i$ choose an action $a_i$ from $A_i$ (all players at the same time)

• prescription how player $i$ chooses his actions from $A_i$
• pure strategy $s_i$ of player $i$ is an action from $A_i$
  • "select a single action and play it"
  • pure-strategy profile … $(s_1,\dots,s_n)$ where $s_i\in A_i$ for each player $i$
• mixed strategy $s_i$ of player $i$ is a probability distribution over $A_i$
  • $\forall a_i\in A_i:s_i(a_i)\in[0,1]$ so that $\sum_{a_i\in A_i} s_i(a_i)=1$
  • $s_i(a_i)$ … probability that $i$ chooses $a_i$ as their action
  • $S_i$ … set of all mixed strategies of player $i$
  • mixed-strategy profile … $(s_1,\dots,s_n)$ where $s_i\in S_i$ for each player $i$
• every pure strategy is a special case of a mixed strategy

in $G=(P,A,u)$, the expected payoff for player $i$ of the mixed-strategy profile $s=(s_1,\dots,s_n)$ is $$u_i(s)=\sum_{a=(a_1,\dots,a_n)\in A}u_i(a)\cdot \prod_{j=1}^n s_j(a_j)$$

• $u_i(s)=\sum_{a_i\in A_i}s_i(a_i)\cdot u_i(a_i;s_{-i})$
• notation
  • $s_{-i}=(s_1,\dots,s_{i-1},s_{i+1},\dots,s_n)$
  • $(s'_i;s_{-i})=(s_1,\dots,s_{i-1},s'_i,s_{i+1},\dots,s_n)$

• games for two players
• bimatrix games – we can use two matrices to express utilities
• prisoner's dilemma – testify × remain silent
  • paradoxically, the only stable solution is when both testify
• matching pennies
  • each player chooses heads or tails
  • if pennies match, player 1 wins, otherwise player 2 wins
  • zero-sum game (as well as rock-paper-scissors)
• battle of sexes (manželský spor)
  • (husband, wife)
  • football × opera
  • if they disagree → (0,0)
    • they attend the events separately
  • if they agree
    • (football, football) → (2,1)
    • (opera, opera) → (1,2)
  • there's not a best outcome/solution
• game of chicken (hra na zbabělce)
  • two drives drive towards each other on a collision course
  • turn × go straight
  • (turn, turn) → (0,0)
  • (turn, go straight) → (1,-1)
  • (go straight, turn) → (1,-1)
  • (go straight, go straight) → (-10,-10)
    • both die

• mixed strategy $s^*_{i}$ such that $u_i(s_i^*;s_{-i})\geq u_i(s'_i;s_{-i})$ for each $s_i'\in S_i$
• if player $i$ knew the strategies of other players, the player would choose this one
• it maximizes his expected payoff if others play $s_{-i}$

• a solution concept
• for a normal-form game $G=(P,A,u)$ of $n$ players, a Nash equilibrium (NE) in $G$ is a strategy profile (…)

• neither best responses nor Nash equilibria are determined uniquely
• rock-paper-scissors – unique mixed Nash equilibrium (both players play everything with probability 1/3)
• battle of sexes – three Nash equilibria, two pure and one mixed
• in every game, there is a Nash equilibrium

• the proof is essentially topological
• we need Brouwer fixed-point theorem
• df: for $d\in\mathbb N$, a subset $X$ of $\mathbb R^d$ is compact $\equiv$ $X$ is closed and bounded
• df: $Y\subseteq\mathbb R^d$ is convex $\equiv$ every line segment containing two points from $Y$ is fully contained in $Y$
  • formally: $(\forall x,y\in Y)(\forall t\in[0,1]):tx+(1-t)y\in Y$
• df: for $n$ affinely independent point s $x_1,\dots,x_n\in\mathbb R^d$, an $(n-1)$-simplex $\Delta_n$ on $x_1,\dots,x_n$ is the set of convex combinations of the points $x_1,\dots,x_n$
  • each simplex is a compact convex set in $\mathbb R^d$
• lemma
  • (…)
  • “you cannot mess up compactness by using cartesian product”
• Brouwer's Fixed Point Theorem
  • $\forall d\in\mathbb N$, let $K$ be a non-empty compact convex set in $\mathbb R^d$ and $f:K\to K$ be a continuous mapping
  • then, there exists a fixed point $x_0\in K$ for $f$, that is, $f(x_0)=x_0$
  • https://www.youtube.com/watch?v=csInNn6pfT4&t=268s

• let $G=(P,A,u)$ be a normal-form game of $n$ players
• $S_i$ … set of mixed strategies of player $i$
• we want to apply Brouwser's theorem, thus we need to find a suitable compact convex body $K$ and a continuous mapping $f:K\to K$ whose fixed points are NE in $G$
• we start with $K$, let $K=S_1\times\dots\times S_n$ be the set of all mixed strategies
  • we verify that $K$ is compact and convex
  • by definition, each $S_i$ is a simplex which is compact and convex
  • by lemma, the set $K$ is compact
  • for any strategy profiles $s\in K$ and $s'\in K$ and a number $t\in [0,1]$
  • …
• …

consider 2-player game “who guesses larger number wins”

• how to find NE efficiently?
• proofs of Brouwer's fixed point theorem are non-constructive as well

• another solution concept
• we want to capture “the best” state of a game, it might be difficult (as in battle of sexes)
• a strategy profile $s$ in $G$ Pareto dominates $s'$, written $s'\prec s$ if, for every player $i$, $u_i(s)\geq u_i(s')$ and there exists a player $j$ such that $u_j(s)\gt u_j(s')$
  • …
• a strategy profile $s\in S$ is Pareto optimal if there does not exist another strategy profile $s'\in S$ that Pareto dominates $s$
  • in zero-sum games, all strategy profiles are Pareto-optimal
  • not all NE are Pareto-optimal (the NE in Prisoner's dilemma)
• Vilfredo Pareto
  • Pareto principle: for many outcomes, roughly 80% of consequences come from 20% of the causes

• let's start with two-player zero-sum games
  • rock paper scissors, chess, table tennis
• let $G=(P,A=A_1\times A_2,u)$ be a zero-sum game
  • that is $u_1(a)+u_2(a)=0$ for every $a\in A$
  • we can use one payoff matrix $M$ where $M_{ij}=u_1(i,j)=-u_2(i,j)$
  • for a strategy profile $(s_1,s_2)$, we write $x_i=s_1(i)$ and $y_j=s_2(j)$ representing $(s_1,s_2)$ with mixed strategy vectors $x=(x_1,\dots,x_m)$ and $y=(y_1,\dots,y_n)$ that satisfy $\sum x_i=1$ and $\sum y_j=1$
  • the expected payoff of player 1 then equals $u_1(s)=\sum_{a=(i,j)\in A}u_1(a)s_1(i)s_2(j)=\sum_{i}\sum_j M_{ij} x_iy_j=x^TMy=-u_2(s)$
• player's 2 best response to a strategy $x$ of 1 is a vector $y\in S_2$ that minimizes $x^TMy$
  • $\beta(x)=\min_y x^TMy$ … best expected payoff of 2
• player's 1 best response to a strategy $y$ of 2 is a vector $x\in S_1$ that maximizes $x^TMy$
  • $\alpha(y)=\max_x x^TMy$
• …
• the minimax theorem
  • for every zero-sum game, worst-case optimal strategies for both players exist and can be efficiently computed
  • there is a number $v$ such that, for any worst-case optimal strategies $x^*$ and $y^*$, the strategy profile $(x^*,y^*)$ is a Nash equilibrium and $\beta(x^*)=(x^*)^TMy^*=\alpha(y^*)=v$
• remarks
  • it was proved by John von Neuman
  • it tells us everything about zero-sum games
  • there are no secrets in zero-sum games – each player can always choose the worst-case optimal strategy
  • original proof uses Brouwer's theorem, we will use linear programming
• proof of the minimax theorem
  • geometry preliminaries
    • hyperplane
    • halfspace
    • polyhedron – intersection of finitely many halfspaces
    • polytope – bounded polyhedron
    • $d$-dimensional polytope is simple … all its vertices are adjacent to exactly $d$ edges
  • linear programming preliminaries
    • constraints, objective function
    • Simplex method, Ellipsoid method
    • duality
  • the proof
    • we'll use the duality
    • first, we find the best response, actually the worst-case best response
    • …
• bimatrix games
  • example: Prisoner's dilemma, collaborative projects
  • brute force algorithm (to find NE)
    • best response condition
  • best response polyhedra
    • labels
  • analysis of the NASH problem (finding nash equilibria in bimatrix games)
    • as a decision problem it is trivial – there always exists a Nash equilibrium
      • so it is not NP complete
    • FNP complexity class (“functional NP”)
    • clearly, NASH belongs to FNP
      • checking whether a strategy profile is NE can be done using the best response condition
    • theorem: if NASH is FNP-complete, then NP = coNP
      • proof is in the lecutre notes (it is not required)
    • therefore, it is unlikely that NASH is FNP-complete
    • new complexity class
    • END-OF-THE-LINE problem
      • the graph can be exponentially large with respect to the input size
    • class PPAD

• $\varepsilon$-NE
• correlated equilibrium
  • linear program
    • any feasible solution will be a correlated equilibrium
    • we can construct the objective function to maximize the general wellbeing

• we have an agent $A$ in an adversary environment
• there are $N$ available actions for $A$ in the set $X=\set{1,\dots,N}$
• at each step $t=1,\dots,T$
  • our agent selects a probability distribution corresponding to the probability of choosing each action $a\in A$
  • adversary chooses a loss vector, loss $\in [-1,1]$
• to be able to tell how well is our agent doing, we compare his loss to the loss of the best agent for some comparison class $\mathcal A$
  • we will mostly consider the class $\mathcal A_X=\set{A_i:i\in X}$, where an agent $A_i$ always chooses action $i$
• external regret … $R^T_A=L^T_A-\min\set{L_B^T:B\in\mathcal A_X}=L_A^T-\min\set{L^T_i:i\in X}$
• for now, we will consider loss $\in\set{0,1}$
• it might seem that the class $\mathcal A_X$ contains too simple agents
  • however, we show that large comparison classes lead to a very large regret
  • let $\mathcal A_\text{all}$ be the set of agents that assign probability 1 to an arbitrary action from $X$ in every step
  • …
• algorithms
  • greedy
  • randomized greedy
  • polynomial weights
• no-regret dynamics
• modern proof of the minimax theorem
• coarse correlated equilibrium
  • CE is always CCE
  • but CCE does not imply CE
• hierarchy of Nash equilibria
• converging to CCE
• regrets
  • external regret
    • we compare to agents playing only one action
  • internal regret
    • we compare to agents that play the same actions as my agent (with same probabilities), only replacing one action by some other one
  • swap regret
    • the same as internal but we allow to replace multiple actions (while keeping the probabilities)
• we have polynomial weights algorithm for external regret
  • how to construct algorithm for swap regret?
  • we will use black-box reduction

• chess … extensive form = tree of the game
• in perfect-information game, all players know the node they are in
• in imperfect-information game, they don't
  • we partition decision nodes into information sets where all nodes belong to the same player and have the same moves
• we can convert any normal-form game of two players to an imperfect-information game in extensive form
• pure, mixed and behavioral strategies
  • mixed strategy = probability distribution over vectors
  • behavioral strategy = vector of probability distributions
• in general, the expressive power of behavioral strategies and mixed strategies are incomparable – but there is a class of extensive games for which the two definitions coincide
  • games of perfect recall
• finding NE in extensive games
• sequence form

• seller
• $n$ bidders
  • each has valuation $v_i$
  • each privately communicates a bid $b_i$ to the seller
• seller decides
  • who receives the item (if anyone)
  • the selling price $p$
• bidders' utility
  • $u_i=0$ … if the bidder lost the auction
  • $u_i=v_i-p$ … if the bidder won
    • we will eventually assume that $p\leq v_i$
• design
  • selling the item for free to the bidder with the highest bid
    • not a good idea
    • “who can name the highest number”
  • selling the item to the bidder with the highest bid for the price equal to the bid
    • does not work that well
    • what should be the bid? the bidder does not know what to do
  • dominant strategy for bidder $i$ … strategy that maximizes $u_i$ no matter what the other bidders do
  • social surplus … $\sum_i v_ix_i$
    • $x_i$ is the indicator of the bidder winning the auction
    • to maximize the social surplus for single item auction, we need the bidder with the highest valuation to win
  • an auction is awesome if it satisifies…
    • strong incentive guarantees
      • DSIC
    • strong performance guarantees
    • computational efficiency
  • there exists an awesome auction!
    • Vickrey's auction
    • the winner pays the second highest bid

$v_i$ … valuation “per unit of the goods”

• $\varphi_i(x)=x-\frac{1-F}{f_i(x)}$
• where $\frac{1-F}{f_i(x)}$ can be regarded as the loss of not knowing the exact valuation

• $n$ bidders
• each bidder has
  • public size $w_i\geq 0$
  • private valuation $v_i\geq 0$
• seller has a capacity $W\geq 0$
• feasible set $X$ … 0/1-vectors such that$\sum_ix_iw_i\leq W$
• we cannot be awesome :(

• $n$ bidders
• $\Omega$ … finite set of outcomes
• $\forall \omega\in\Omega:$ each bidder has a private valuation $v_i(\omega)\geq 0$
• $\forall\omega\in\Omega:$ each bidder submits his bids $b_i(\omega)\geq 0$
• our goal is to design a mechanism that selects an outcome $\omega\in\Omega$ so that it maximizes the social surplus $\sum_iv_i(\omega)$
• bidder A winning and bidder B winning are two separate outcomes → bidders can have opinions about each other bidder winning the item as well
• example: single-item auction
  • $\Omega=\set{\omega_1,\dots,\omega_n,\omega_\emptyset}$
• VCG mechanism
  • states that we can do DSIC social surplus maximization
• note: allocation rule can assume that the bidders bid truthfully if we consider DSIC – but the payment formula has to provide DSIC

• payment difference sandwich
  • $y,z$ are not functions but only coefficients (bids)
  • $x_i(y;b_{-i})-x_i(z;b_{-i})$ has to be non-positive
    • because $z\cdot()\leq y\cdot()$ and $y\lt z$

• is DSIC too restrictive?
• if there is a dominant strategy, we can assume that it is truthtelling