diff options
| -rw-r--r-- | games/main.tex | 425 |
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} |