path: root/games/main.tex

\documentclass[10pt, twocolumn]{article}
\usepackage[hmargin=3em,vmargin=3em, bmargin=5em,footskip=3em]{geometry}
\setlength{\columnsep}{2em}
%\documentclass{article}
\title{Non-atomic games}
\author{Thibaut Horel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath, amsfonts, amsthm}
\usepackage{times}
\usepackage{microtype}
\usepackage[pagebackref=true,breaklinks=true,colorlinks=true]{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{cor}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\newcommand{\set}[1]{\mathbf{#1}}
\newcommand{\gx}{\mathcal{X}}
\newcommand{\bx}{\boldsymbol{x}}
\newcommand{\fa}{\phi}
\newcommand{\R}{\mathbf{R}}
\newcommand*{\defeq}{\equiv}
\newcommand{\eps}{\varepsilon}
\let\P\relax
\DeclareMathOperator{\P}{\mathbb{P}}
\DeclareMathOperator{\E}{\mathbb{E}}
\begin{document}
\maketitle


\section{Non-atomic games}

\begin{definition}
    A \emph{non-atomic game} is a triplet $(I, A, C)$ where:

\begin{itemize}
    \item $I$ is an (infinite) measure space of agents.  Without
        ``much'' loss of generality, we will assume that $I=[0,1]$ endowed with
        the Lebesgue measure $\lambda$.
    \item $A$ is the set of actions, here assumed finite.
    \item $C:I\times A\times A^I\to\R$ is the cost function: given an agent $t$
        in $I$, an action $a\in A$ and a strategy profile $s:I\to A$ of what
        all agents are doing, $C(t, a, s)$ is the cost incurred by agent $t$ by
        playing $a$ against strategy profile $s$.
\end{itemize}
\end{definition}

Furthermore, we assume that $C$ is such that if $s=s'$ $\lambda$-a.e,
$C(t,a,s)=C(t,a,s')$ for any $t\in I$ and $a\in A$. In particular, if a single
agent deviates from the strategy profile $s$, the cost incurred by the other
agents does not change.


\paragraph{Anonymity.} We will focus on a specific kind of non-atomic games
called \emph{anonymous} in which the cost does not depend on the identity of
the agent but only on the action he plays. Furthermore, the cost does not
depend on the full strategy profile $s$, but only on the distribution it
induces on $A$ (how many agents play each action). This is justified by the
fact that every player is facing a continuum of players and does not reason
about each individual action but only about the actions in aggregate. This
leads to the following definition.

\begin{definition}
    A non-atomic game $(I, A, C)$ is \emph{anonymous} if there exist a function
    $c:A\times \Delta(A)\to \R$ such that:
    \begin{displaymath}
        \forall t\in I, \forall a\in A, \forall s\in A^I, C(t, a, s) = c(a,
        \nu_s)
    \end{displaymath}
    where $\Delta(A)$ denotes the set of distributions over $A$ and $\nu_s$
    denotes the pushforward of $\lambda$ through $s$: $\nu_s(a)
    = \lambda\big(s^{-1}(a)\big)$.
\end{definition}

\begin{definition}
    A strategy profile $s$ is a Cournot-Nash equilibrium (CNE) of an anonymous
    non-atomic game if:

    \begin{displaymath}
        \lambda\text{-a.e}\, t\in I, \forall a\in A, c(s(t), \nu_s)\leq c(a, \nu_s)
    \end{displaymath}

    Equivalently:

    \begin{displaymath}
        \forall (a_1,a_2)\in A^2, \nu_s(a_1)>0 \implies c(a_1,\nu_s) \leq
        c(a_2, \nu_s)
    \end{displaymath}
\end{definition}

\begin{remark}
It is clear from the definition, that a CNE is property of action distribution
    $\nu_s$ and not of the strategy profile $s$. We will abuse the language
    slightly and talk about $\nu\in\Delta(A)$ as being a CNE to mean that any
    $s\in A^I$ such that $\nu_s = \nu$ is a CNE.
    
    A consequence of the definition is also that all played actions ($a$ such
    that $\nu(a)>0$) have the same cost at equilibrium. Indeed, let $a_1$ and
    $a_2$ be two such action, then by definition of a CNE, we have
    $c(a_1,\nu)\leq c(a_2, \nu)$ and $c(a_2,\nu)\leq c(a_1,\nu)$. We will refer
    to this common cost as the \emph{cost of the equilibrium} and denote it by
    $c_\nu$.
\end{remark}

\section{Potential games}

In this section, we generalize the definition of potential games to non-atomic
games and give a characterization of them as well as of their CNEs.

\begin{definition}
    A non-atomic anonymous game $(I, A, c)$ is a \emph{potential game} if there
    exists a differentiable potential function $\Phi: \Delta(A)\to\mathbb{R}$
    such that:
    \begin{displaymath}
       \forall a\in A, \forall \nu\in\Delta(A), \partial_a \Phi(\nu) = c(a,
       \nu)
    \end{displaymath}
\end{definition}

The analogy with finite potential games is the following: assume that an $\eps$
fraction of the players move from action $a_1$ to action $a_2$. The first order
change in the value of the potential is then $\eps\big(\partial_{a_2} \Phi(\nu)
- \partial_{a_1}\Phi(\nu)\big)$. By definition, this is equal to
$\eps\big(c(a_2, \nu) - c(a_1,\nu)\big)$, \emph{i.e} the change in cost from
moving from $a_1$, to $a_2$.

\begin{definition}
    A game $(I, A, c)$ has \emph{symmetric externalities} if:
    \begin{displaymath}
        \forall \nu\in\Delta(A), \forall a_1\in A, \forall a_2\in A,
        \frac{\partial c(a_1,\nu)}{\partial \nu_{a_2}}
        = \frac{\partial c(a_2,\nu)}{\partial \nu_{a_1}}
    \end{displaymath}
   In other words, the externality imposed on players playing $a_1$ by players
   moving to $a_2$ is equal to the externality imposed on players playing $a_2$
   by players moving to $a_1$.
\end{definition}

\begin{theorem}
    \label{thm:equiv}
    Let us consider an anonymous game $\Gamma=(I, A, c)$, then the following two
    conditions are equivalent:
    \begin{enumerate}
        \item $\Gamma$ is a potential game.
        \item $\Gamma$ has symmetric externalities.
    \end{enumerate}
\end{theorem}

\begin{proof}
    This is simply a reformulation of Poincaré's lemma. 1. states that the
    differential form $\text{d}\Phi$ is exact, 2. states that $\text{d}\Phi$ is
    closed. Since $\Delta(A)$ is contractible, we conclude that the two are
    equivalent by Poincaré's lemma.
\end{proof}

\begin{remark}
    It is usually easier to prove symmetric externalities than to exhibit
    a potential function. However, Poincaré's lemma also gives us a way to
    construct a potential function given its partial derivatives: pick any
    point $\nu^*\in\Delta(A)$ and define
    \begin{equation}
        \label{eq:potential}
        \Phi(\nu) = \sum_{a\in A} \int_{0}^1 (\nu_a-\nu^*_a)c(a,
        \nu^*+\lambda\big(\nu-\nu^*)\big)\text{d}\lambda
    \end{equation}
\end{remark}

\begin{theorem}
    Let $\Gamma=(I, A, c)$ be a potential game, then $\Gamma$ admits a CNE.
\end{theorem}

\begin{proof}
    Let $\Phi$ be a potential for the game. Consider the following optimization
    problem:
    \begin{displaymath}
        \begin{split}
            \min &\;\Phi(\nu)\\
            \text{s.t}&\;\nu\in \Delta(A)
        \end{split}
    \end{displaymath}
    Potential $\Phi$ is differentiable hence continuous and the optimization
    domain is compact, so the minimum is well defined. Let us consider
    $\nu\in\Delta(A)$ realizing this minimum. Since the constraints of the
    optimization problem are linear, the KKT conditions are necessary
    conditions for optimality. Hence there exists $\lambda\in\R$ and
    $\mu\in\R_+^{|A|}$ such that:
    \begin{gather*}
        \forall a\in A, \partial_a \Phi(\nu) - \lambda - \mu_a = 0\\
        \forall a\in A, \mu_a\nu_a = 0
    \end{gather*}
    $\mu_a$ is the Lagrange multiplier associated with the constraint
    $\nu_a\geq 0$ and $\lambda$ is the Lagrange multiplier associated with the
    constraint $\sum_{a\in A} \nu_a = 1$.

    Using that $\partial_a\Phi(\nu) = c(a,\nu)$ and combining the KKT
    conditions, we obtain:
    \begin{enumerate}
        \item either $\nu_a>0$, in which case $c(a,\nu) = \lambda$
        \item or $\nu_a = 0$, in which case $c(a,\nu) \geq \lambda$
    \end{enumerate}
    which is simply a reformulation of the definition of $\nu$ being
    a CNE of cost $c_\nu=\lambda$.
\end{proof}

\begin{theorem}
    \label{thm:convex}
    Let $\Gamma = (I, A, c)$ be a potential game with potential $\Phi$. If
    $\Phi$ is convex, then $\nu$ is a CNE of $\Gamma$ iff $\nu$ is solution to:
    \begin{displaymath}
        \begin{split}
            \min &\;\Phi(\nu)\\
            \text{s.t}&\;\nu\in \Delta(A)
        \end{split}
    \end{displaymath}
    Furthermore, if the potential $\Phi$ is strictly convex, then $\Gamma$ has
    a unique CNE.
\end{theorem}

\begin{proof}
    We simply use that if $\Phi$ is convex, then the KKT conditions are
    necessary and sufficient for optimality. Furthermore, if $\Phi$ is strictly
    convex, then the minimum is unique.
\end{proof}

\section{Congestion games}

In this section, we study a specific kind of non-atomic anonymous games called
congestion games. We will show that congestion games are potential
games\footnote{In the atomic case, potential games are equivalent to congestion
games. In the non-atomic case it does not seem to be the case.} and further
characterize their CNEs.

In a congestion game, there is a finite set $E$ of resources.  The action set
$A$ of players is some subset of $2^E$, the power set of $E$. In other
words, an action $a\in A$ of a player is simply a subset of $E$\footnote{In
a routing game, $E$ are the edges of a graph, and $A$ is the set of paths from
origin to destination.}.

Associated with each resource $e\in E$ is a congestion function $c_e:\R_+\to\R$
quantifying the cost of using this resource as a function of how many players
use it. Specifically, for a strategy distribution $\nu\in\Delta(A)$, and
resource $e$, we define $\nu_e = \sum_{a\in A: e\in a}\nu_a$ the measure of
players using resource $e$. The cost of using resource $e$ is then given by
$c_e(\nu_e)$. The cost function $c:A\times \Delta(A)$ of the congestion game is
then given by:
\begin{displaymath}
    \forall a a\in A, \forall \nu\in\Delta(A),\;  c(a, \nu) = \sum_{e\in a}
    c_e(\nu_e)
\end{displaymath}

\begin{theorem}
    \label{thm:congestion}
    All congestion games are potential games.
\end{theorem}

\begin{proof}
    If we assume that the congestion functions are differentiable, then by
    Theorem~\ref{thm:equiv}, it is sufficient to verify the symmetry of
    externalities. Let us consider two actions $a_1$ and $a_2$ in $A$, and
    a strategy distribution $\nu\in\Delta(A)$:
    \begin{displaymath}
        \frac{\partial c(a_1,\nu)}{\partial \nu_{a_2}} = \sum_{e\in
        a_1}c_e'(\nu_e)\partial_{a_2}\nu_e
    \end{displaymath}
    but $\partial_{a_2}\nu_e$ is $1$ if $e\in a_2$ and $0$ otherwise, else:
    \begin{displaymath}
        \frac{\partial c(a_1,\nu)}{\partial \nu_{a_2}} = \sum_{e\in
        a_1\cap a_2}c_e'(\nu_e)
    \end{displaymath}
    Exchanging the role of $a_1$ and $a_2$ shows that the externalities are
    symmetric.
\end{proof}

\begin{remark}
    We can then obtain an expression of the potential of the game by using
    \eqref{eq:potential}:
    \begin{displaymath}
        \Phi(\nu) = \sum_{e\in E}\int_{0}^{\nu_e} c_e(x)\text{d}x
    \end{displaymath}
    It is then easy to verify by direct differentiation that this is indeed
    a potential of the game. This holds even without assuming that
    the congestion functions are differentiable.
\end{remark}

A consequence of Theorem~\ref{thm:congestion} is that a congestion game always
admits a CNE. We can then further characterize the CNEs of a congestion game
using Theorem~\ref{thm:convex}.

\begin{theorem}
    \label{thm:foo}
Let us consider a congestion game $\Gamma$ such that the congestion functions
    $c_e$ are non-decreasing. Then $\nu$ is a CNE of $\Gamma$ iff it is
    solution to:
    \begin{displaymath}
        \begin{split}
            \min &\;\sum_{e\in E}\int_{0}^{\nu_e}c_e(x)\text{d}x\\
            \text{s.t}&\;\nu\in \Delta(A)
        \end{split}
    \end{displaymath}
    Furthermore, all CNEs have the same cost. Finally, if all the congestion
    functions are strictly increasing, then there exists a unique CNE.
\end{theorem}

\begin{proof}
    Observe that if the cost functions are non-decreasing, then the potential
    is convex (sum of convex functions). The characterization of CNEs as
    solutions to the optimization problem then follows from
    Theorem~\ref{thm:convex}.
    
    The fact that all equilibria have the same cost is specific to congestion
    games and is proved as follows. Consider two CNEs $\nu^1$ and $\nu^2$, then
    by convexity the function $f(\lambda) = \Phi\big(\nu^1
    + \lambda(\nu^2-\nu^1)\big)$ is constant equal to the minimum of the
    optimization problem on $[0,1]$. Hence its derivative is constant equal to
    $0$ on $[0, 1]$:
    \begin{displaymath}
        \forall \lambda\in[0,1], f'(\lambda) = \sum_{e\in E} (\nu_e^2-\nu_e^1)c_e\big(\nu^1_e
        + \lambda(\nu^2_e-\nu^1_e)\big) = 0 
    \end{displaymath}
    In particular, writing $f'(1) = f'(0)$, we obtain:
    \begin{equation}
        \label{eq:foo}
        \sum_{e\in E} (\nu_e^2-\nu_e^1)c_e(\nu^1_e)
        = \sum_{e\in E} (\nu_e^2-\nu_e^1)c_e(\nu^2_e)
    \end{equation}
    Reordering:
    \begin{displaymath}
        \sum_{e\in E} (\nu_e^2-\nu_e^1)\big(c_e(\nu^2_e) - c_e(\nu^1_e)\big)
        = 0
    \end{displaymath}
    All functions $c_e$ are non-decreasing, so the above sum is a sum of
    non-negative terms. Since it is equal to $0$ all terms are $0$, \emph{i.e}
    $c_e(\nu_e^2) = c_e(\nu_e^1)$ for all $e\in E$. Remember that the cost of
    an equilibrium $\nu$ is given by:
    \begin{displaymath}
        c(\nu) = \sum_{e\in E: e\in a} c_e(\nu_e)
    \end{displaymath}
    for some action $a\in A$ such that $\nu_a>0$ (all played actions have the
    same cost). Since $c_e(\nu_e)$ does not depend on the chosen equilibrium,
    the cost of all equilibria is the same.

    Finally, if the congestions functions are non-decreasing, then the
    potential function is strictly convex, and the uniqueness of the CNE
    follows from Theorem~\ref{thm:convex} (it also directly follows from
    \eqref{eq:foo}).
\end{proof}

Finally, we show how the characterization of Theorem~\ref{thm:foo} can be used
to obtain a bound on the price of anarchy of a congestion game\footnote{The
bound is not tight, tight bounds are known, but obtaining them is a bit more
involved.}.

\begin{definition}
    Given an action distribution $\nu\in\Delta(A)$,  the \emph{social welfare}
    $W(\nu)$, is the sum of the costs of all players:
    \begin{displaymath}
        W(\nu) = \sum_{a\in A}\nu_a c(a,\nu) = \sum_{e\in E}\nu_e c_e(\nu_e)
    \end{displaymath}
    The \emph{price of anarchy} of the game is the largest ratio between the
    social welfare of a CNE and the social welfare of a social welfare optimal
    distribution $\nu$. Specifically, let us consider a social-welfare
    optimal distribution $\nu^*$,  solution to the following optimizing
    program:
    \begin{displaymath}
        \begin{split}
            \min &\;W(\nu)\\
            \text{s.t}&\;\nu\in \Delta(A)
        \end{split}
    \end{displaymath}
    Then the price of anarchy is defined by:
    \begin{displaymath}
        \rho = \max_{\nu\in CNE} \frac{W(\nu)}{W(\nu^*)}
    \end{displaymath}
    Note that we necessarily $\rho\geq 1$.
\end{definition}

The following theorem gives a simple necessary condition under which the price
of anarchy can be bounded.

\begin{theorem}
Consider a congestion game with non-decreasing congestion functions.
    Furthermore, assume that the congestion functions satisfy the following
    inequality:
    \begin{displaymath}
        \forall e\in E, \forall x\in\R_+, \int_{0}^{x} c_e(z)\text{d}z \geq
        \alpha\, x\cdot c_e(x)
    \end{displaymath}
    for some $\alpha\leq 1$. Then, the price of anarchy $\rho$ of the game
    satisfies  $\rho \leq \frac{1}{\alpha}$.
\end{theorem}

\begin{proof}
    The assumption of the theorem directly implies that $\Phi(\nu)\geq \alpha
    W(\nu)$ for all $\nu$. Furthermore, we have the trivial bound:
    \begin{displaymath}
        \int_0^x c_e(z)\text{d}z \leq x\cdot c_e(x)
    \end{displaymath}
    which implies $\Phi(\nu)\leq W(\nu)$. Let us now consider a CNE $\nu$ and
    a social welfare optimal distribution $\nu^*$:
    \begin{displaymath}
        W(\nu) \leq \frac{1}{\alpha} \Phi(\nu)\leq \frac{1}{\alpha}
        \Phi(\nu^*)\leq \frac{1}{\alpha} W(\nu^*)
    \end{displaymath}
    where the second inequality uses that $\nu$ is optimal for $\Phi$.
\end{proof}

\begin{cor}
    Let us consider a congestion game with affine congestion functions, then
    its price of anarchy is upper-bounded by $2$.
\end{cor}

\begin{proof}
    For affine functions, we have:
    \begin{displaymath}
        \int_0^x c_e(z)\text{d}z \leq \frac{1}{2}x\cdot c_e(x)\qedhere
    \end{displaymath}
\end{proof}
\end{document}