\documentclass{article}
%
% \usepackage{pdfsync} % Used in Mac OSX
\usepackage[mathcal,mathbf]{euler}
\usepackage{theorem,amsmath,enumerate,fancyhdr,amssymb,amsfonts}
% \usepackage{graphicx} %Used in Mac OSX
% \usepackage[pdftex]{graphics} %Might be needed in non Mac OSX systems
\usepackage{myDefs}
\usepackage[all,poly]{xy}
\usepackage{graphicx}
% In order to be consistent use the following notation in your notes:
\title
{
CMSC 858F: Algorithmic Game Theory\\
Fall 2010\\
Introduction to Algorithmic Game Theory % 1 or 2 or 3 etc
}
\author
{
{\bf Instructor:} Mohammad T. Hajiaghayi\\
{\bf Scribe:} Ateeq Sharfuddin
}
\date{September 1, 2010} % put the date of the lecture here NOT the date the note was written
\begin{document}
\pagestyle{fancy}
\lhead{{\bf Scribe:}{ Ateeq Sharfuddin }
\\{\bf Lecture 1b } } % insert lecture number
\rhead{{\bf Date: }09/01/2010} % enter lecture date NOT today's date
\maketitle
%
\medskip
% my stuff....
% end of my stuff...
\section{Overview} % give a one paragraph short description of the topics
In this lecture, we delve into some basics about Game Theory and Algorithmic Game Theory. In particular, we introduce one-shot simultaneous move games, stable solutions, dominant strategy solutions, pure strategy Nash equilibria, mixed-strategy Nash equilibria, and ``price of anarchy" (PoA).
\section {Algorithmic Game Theory}
\emph{Game Theory} is an attempt to study systems by modeling them as \emph{games}. A game can be defined as a situation where a set of \emph{agents} interact or affect each other's outcomes.
\emph{Algorithmic Game Theory} is slightly newer than general Game Theory, and is primarily concerned with smart, selfish agents who are interested in maximizing their own utility. Algorithmic Game Theory is an attempt at making Game Theory more ``algorithmic," by coordinating the agents with \emph{Mechanism Design} to socialize so that they may generate something good for the society as a whole \cite{hajiaghayi2010}.
The goal of Mechanism Design is to design and impose rewarding rules to encourage selfish agents to change their strategy and behave socially. With Mechanism Design, we try to get an approximate optimal \emph{solution}.
A solution is an outcome of a game. Typically, we are interested with stable solutions or \emph{equilibria} (or equilibrium points).
\begin{definition}
An equilibrium point or just equilibrium is a state in which no person involved in the game wants any change. More precisely, an equilibrium is simply a state of the world where economic forces are balanced and in the absence of external influences, the (equilibrium) values of economic variables will not change.\cite{hajiaghayi2010}
\end{definition}
The existence of equilibrium is a subject of study in economics. The performance of output (or approximation factor) is studied in both computer science and economics. And convergence (running time) or non-convergence is a subject of study in computer science.
For computer science, we are also interested in concepts (some of which we will cover in class) such as: the lack of coordination in networks and equilibrium concepts, market equilibria and its applications (e.g., in wireless networks), ``price of anarchy" or ``price of stability" in load balancing games, selfish routing games, congestion games, market sharing games, network creation games and network formation games, interdomain routing and stable paths problems, Gao-Rexford conditions, auctions, VCG, truthfulness, sponsored search auctions, online auctions, cost sharing, and privacy and complexity (hardness).
In this course, we will cover two important classes of equilibria: Nash equilibrium, and Market equilibrium. For this lecture, we considered \emph{one-shot simultaneous move games}-- games in which all players simultaneously chose an action from their set of possible \emph{strategies}, where a strategy can be defined as a predetermined “programme of play” that tells an agent what actions to take in response to every possible strategy any other agent playing the game might use \cite{ross2010}.
A simultaneous move game consists of a set of \emph{n} players, \{1, 2, 3, \ldots, \emph{n}\}, where each player \emph{i} has his own set of possible strategies, $\emph{S}_\emph{i}$. Each player \emph{i} selects a strategy $\emph{s}_\emph{i} \in \emph{S}_\emph{i}$. We use $\emph{s} = (\emph{s}_1, \emph{s}_2, ..., \emph{s}_\emph{n})$ to denote the vector of strategies selected by the players and $\emph{S} = \times _\emph{i} \emph{S}_\emph{i}$ to denote the set of all possible ways in which players can pick strategies.
The vector of strategies $\emph{s} \in \emph{S}$ selected by the players determine the outcome for each player. We use $\emph{s}_\emph{i}$ to denote the strategy played by player $\emph{i}$ and $\emph{s}_{-\emph{i}}$ to denote the ($\emph{n}$ - 1)-dimensional vector of strategies played by all other players. We use $\emph{u}_\emph{i}(\emph{s})$ to denote the utility (payoff) incurred by player \emph{i}. We also denote utility using $\emph{u}_\emph{i}(\emph{s}_\emph{i}, \emph{s}_{\emph{-i}})$ \cite{nisan2007}.
\section {Dominant Strategy Solution}
We say that a game has a \emph{dominant strategy solution} if each player in the game has a best strategy, independent of the strategies played by the other players \cite{nisan2007}.
\begin{definition}
A strategy vector $\emph{s} \in \emph{S}$ is a dominant strategy solution if for each player \emph{i} and each alternate strategy vector $\emph{s}^\prime \in \emph{S}$, we have $\emph{u}_\emph{i}(\emph{s}_\emph{i}, \emph{s}^\prime _{-\emph{i}}) \geq \emph{u}_\emph{i}(\emph{s}^\prime _\emph{i}, \emph{s}^\prime _{-\emph{i}})$.
\end{definition}
\section {Prisoners' dilemma}
Two prisoners are on trial for a crime and each face the choice of confessing to the crime or remaining silent. If they both remain silent, the authorities will not be able to charge them for this particular crime, and they will both face two years in prison for minor offenses. If one of them confesses, his term will be reduced to one year, but he will have to bear witness against the other, who will be sentenced to five years. If they both confess, they will both get a small break and be sentenced to four years in prison (rather than five).
We can summarize the four outcomes and the utility with the following \emph{cost matrix}:\\
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(6,6)
\put(1,2){\makebox(0,0){$Silent$}}
\put(1,4){\makebox(0,0){$Confess$}}
\put (1.2,5){\makebox(0,0){$P1$}}
\put (1.7,5.7){\makebox(0,0){$P2$}}
\put (3,5.5){\makebox(0,0){$Confess$}}
\put (5,5.5){\makebox(0,0){$Silent$}} %
\put (3.5,4.5){\makebox(0,0){4}}
\put (5.5,4.5){\makebox(0,0){5}}
\put (2.5,3.5){\makebox(0,0){4}}
\put (4.5,3.5){\makebox(0,0){1}}%
\put (3.5,2.5){\makebox(0,0){1}}
\put (5.5,2.5){\makebox(0,0){2}}
\put (2.5,1.5){\makebox(0,0){5}}
\put (4.5,1.5){\makebox(0,0){2}}%
\put(2, 1){\line(0,1){4}}
\put(4, 1){\line(0,1){4}}
\put(6, 1){\line(0,1){4}}
\put(2, 1){\line(1,0){4}}
\put(2, 3){\line(1,0){4}}
\put(2, 5){\line(1,0){4}}
\put(1, 6){\line(1, -1){1}}
\end{picture}\\
\end{center}
The only \emph{stable solution} in this game is when both confess. In each of the other three outcomes, a prisoner can switch from being silent to confessing in order to improve his own payoff. The social optimum in this case is when both remain silent; however, this outcome is not stable. In this game, there is a unique optimal selfish strategy for each player, independent of what other players do. One way to specify a game in algorithmic game theory is to explicitly list all possible strategies and utilities of all players. Expressing the game in this form is called the \emph{standard form} or matrix form, and it is convenient to represent two-player games with a few strategies in this form, as demonstrated for the Prisoner's dilemma game \cite{nisan2007}.
\section {Battle of the sexes}
Battle of the sexes is an example of a \emph{coordination game}. In this game, there are multiple stable outcomes. Consider two players, a boy and a girl, who are deciding on how to spend the evening. They both consider two possibilities: going to a baseball game or going to a softball game. The boy prefers baseball, whereas the girl prefers softball, but they would prefer to spend the evening together instead of being separate. We express their preferences using the following cost matrix:\\
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(6,6)
\put(1,2){\makebox(0,0){$S$}}
\put(1,4){\makebox(0,0){$B$}}
\put (1.2,5){\makebox(0,0){$Girl$}}
\put (1.7,5.7){\makebox(0,0){$Boy$}}
\put (3,5.5){\makebox(0,0){$B$}}
\put (5,5.5){\makebox(0,0){$S$}} %
\put (3.5,4.5){\makebox(0,0){6}}
\put (5.5,4.5){\makebox(0,0){1}}
\put (2.5,3.5){\makebox(0,0){5}}
\put (4.5,3.5){\makebox(0,0){1}}%
\put (3.5,2.5){\makebox(0,0){2}}
\put (5.5,2.5){\makebox(0,0){5}}
\put (2.5,1.5){\makebox(0,0){2}}
\put (4.5,1.5){\makebox(0,0){6}}%
\put(2, 1){\line(0,1){4}}
\put(4, 1){\line(0,1){4}}
\put(6, 1){\line(0,1){4}}
\put(2, 1){\line(1,0){4}}
\put(2, 3){\line(1,0){4}}
\put(2, 5){\line(1,0){4}}
\put(1, 6){\line(1, -1){1}}
\end{picture}\\
\end{center}
The two solutions where the two players choose different games are not stable, as the two players can improve their payoff by switching.
\section {Matching pennies}
Two players, each with a penny, are to choose from among two strategies- heads (H) and tails (T). The row player wins if the two pennies match, and the column player wins if they do not match. We express this using the following cost matrix, where 1 indicates a win and -1 indicates a loss:\\
\setlength{\unitlength}{1cm}
\begin{center}
\begin{picture}(6,6)
\put(1,2){\makebox(0,0){$T$}}
\put(1,4){\makebox(0,0){$H$}}
\put (1.2,5){\makebox(0,0){$1$}}
\put (1.7,5.7){\makebox(0,0){$2$}}
\put (3,5.5){\makebox(0,0){$H$}}
\put (5,5.5){\makebox(0,0){$T$}} %
\put (3.5,4.5){\makebox(0,0){-1}}
\put (5.5,4.5){\makebox(0,0){1}}
\put (2.5,3.5){\makebox(0,0){1}}
\put (4.5,3.5){\makebox(0,0){-1}}%
\put (3.5,2.5){\makebox(0,0){1}}
\put (5.5,2.5){\makebox(0,0){-1}}
\put (2.5,1.5){\makebox(0,0){-1}}
\put (4.5,1.5){\makebox(0,0){1}}%
\put(2, 1){\line(0,1){4}}
\put(4, 1){\line(0,1){4}}
\put(6, 1){\line(0,1){4}}
\put(2, 1){\line(1,0){4}}
\put(2, 3){\line(1,0){4}}
\put(2, 5){\line(1,0){4}}
\put(1, 6){\line(1, -1){1}}
\end{picture}\\
\end{center}
Notice that this game does not have a stable solution. The best option is for the players to randomize (with probability $\frac{1}{2}$) in order to thwart the strategy of the other player.
\section{Nash Equilibrium}
Games rarely possess \emph{dominant strategy solutions}; as such, a less stringent and more widely applicable solution concept is necessary. A desirable solution is one in which individual players act in accordance with their incentives, maximizing their own payoff, and this is best captured by the concept of \emph{Nash equilibrium}.
A Nash equilibrium is a solution concept (a condition which identifies the equilibrium) of a game involving two or more players in which no player has anything to gain by changing only his or her own strategy unilaterally. In fact, such a solution is self-enforcing in the sense that once the players are playing such a solution, it is in every player's best interest to stick to his strategy \cite{hajiaghayi2010, nisan2007}.
\begin{definition}
A strategy vector $\emph{s} \in \emph{S}$ is said to be a Nash equilibrium if for all players \emph{i} and each alternate strategy $\emph{s}^\prime _\emph{i} \in \emph{S}_\emph{i}$, we have that $\emph{u}_\emph{i}(\emph{s}_\emph{i}, \emph{s}_{-\emph{i}}) \geq \emph{u}_\emph{i}(\emph{s}^\prime _\emph{i}, \emph{s}_{-\emph{i}})$.
\end{definition}
A dominant strategy solution is a Nash equilibrium. If a solution is strictly dominating (switching to the solution always improves the outcome), it is also the unique Nash equilibrium. Note that a Nash equilibrium is not always an optimal solution (since a dominant strategy solution is not always optimal; c.f. Prisoner's dilemma). The Nash equilibria considered are \emph{pure strategy} equilibria since each player deterministically plays his chosen strategy. In Matching Pennies however, we noticed that there was no pure strategy equilibria. If the players were allowed to randomize with probability 1/2, we obtain a solution strategy since the expected payoff is 0 and neither player can improve by choosing a different randomization.
To define randomized strategies formally, let us enhance the choices of players so each one can pick a probability distribution over his set of possible strategies; such a choice is called a mixed strategy. We assume that players independently select strategies using the probability distribution. The independent random choices of players leads to a probability distribution of strategy vector \emph{s}. Nash, in 1951, proved that under this extension, every game with a finite number of players, each with a finite set of strategies, has a Nash equilibrium. If we do not have finite sets, we do not necessarily have a mixed strategy Nash equilibrium \cite{hajiaghayi2010, nisan2007}.
\begin{theorem}
Any game with a finite set of players and finite set of strategies has a Nash equilibrium of mixed strategies.
\end{theorem}
\section{Price of Anarchy (PoA) and Price of Stability (PoS)}
The ``price of anarchy" is a popular measure of inefficiency of an equilibrium. It is defined as the ratio between the worst objective function value of an equilibrum of the game and that of an optimal outcome (social optimum). We are interested in a ``price of anarchy" which is close to 1, i.e., all equilibriums are good approximations of an optimal solution. A game with multiple equilibria has a large ``price of anarchy" even if only one of its equilibria is highly inefficient. The ``price of stability" of a game is the ratio between the best objective function value of one of its equilibrium and that of an optimal outcome. In games with a unique equilibrium, PoA = PoS \cite{hajiaghayi2010}.
\section{Homework Assignment}
Suppose you want to sell your bike, car, house, etc., and you want to sell online (e.g., craigslist). What would your strategy be? What is the difference in putting your listing on craigslist vs. putting it on the classifieds of a magazine? Will you search for other bikes? What are the assumptions? How much would you sell for? Do you want to put it below/above the average price, and how much above or below?
\begin{thebibliography}{9}
\bibitem{hajiaghayi2010}
Hajiaghayi, Mohammad T. \emph{Algorithmic Game Theory: Lecture 1-- Hand-written notes}. 1 September 2010. University of Maryland.
\bibitem{nisan2007}
Nisan, Noam et al.
\emph{Algorithmic Game Theory}. New York: Cambridge \mbox{University} Press, 2007.
\bibitem{ross2010}
Ross, Don.
\emph{Game Theory (Stanford Encyclopedia of Philosophy)}. May 5, 2010. Stanford University. 6 September 2010 $<\mbox{ http://plato.stanford.edu/entries/game-theory/}>$.
\bibitem{feng2010}
Feng, Xiaofan. \emph{Cost-matrix drawing procedure for \LaTeX}. The George Washington University. 6 September 2010.
\end{thebibliography}
\end{document}