1 files changed, 425 insertions, 0 deletions
diff --git a/games/main.tex b/games/main.tex
new file mode 100644
index 0000000..71abda4
--- /dev/null
+++ b/games/main.tex
@@ -0,0 +1,425 @@
+\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}