\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\ssb}{\mbox{\boldmath $s$}}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 598RM: Algorithmic Game Theory, Fall 2018}
\\[0.5ex]
\textbf{HW 3 (due on Thursday, Nov 8th at 11:59pm CST)}
\end{center}
\noindent{\bf Instructions:}
\begin{enumerate}
\item We will grade this assignment out of a total of 30 points.
\item Feel free to discuss with fellow students, but write your own answers. If you do discuss a problem with someone then write their
names at the starting of the answer for that problem.
\item Please type your solutions if possible in Latex or doc whatever is suitable. See instructions on the webpage on how to submit.
\item Even if you are not able to solve a problem completely, do submit whatever you have. Partial proofs, high-level ideas, examples,
and so on.
\item Except where otherwise noted, you may refer to lecture slides/notes, and to the references provided.
You cannot refer to textbooks, handouts, or research papers that have not been listed. If you do use any approved sources, make
sure you cite them appropriately, and make sure to write in your own words.
\item No late assignments will be accepted.
\item By AGT book we mean the following book: Algorithmic Game Theory (edited) by Nisan, Roughgarden, Tardos and Vazirani.
Its free online version is available at Prof. Vijay V. Vazirani's webpage.
\end{enumerate}
\medskip
\medskip
\hline
\begin{enumerate}
%----------------------------------------------------------------------
\item (3 points) Prove that if $\mathcal C$ is the set of cost functions of the form $c(x)=ax^2+bx+c$ with $a,b,c\ge 0$, then the Piguo bound $\alpha(\mathcal C)$ is $\frac{3\sqrt{3}}{3\sqrt{3}-2}$.
\item (8 points) Consider an atomic selfish routing game in which all players have the same source vertex and sink vertex (and each controls one unit of flow). Assume that edge cost functions are non-decreasing, but do not assume that they are affine. Prove that a pure-strategy Nash equilibrium can be computed in polynomial time. Be sure to discuss the issue of fractional vs. integral flows, and explain how (or if) you use the hypothesis that edge cost functions are non-decreasing.
\medskip
[Hint: Recall the Rosenthal's potential function. You can assume without proof that the minimum-cost flow can be solved in polynomial time. If you haven't seen the min-cost flow problem before, you can read about it in any book on ``combinatorial optimization''.]
\item (5 points)
This problem develops some theory about potential games; we talked about these while discussing selfish routing. We consider
an abstract finite game with $n$ players with finite strategy sets $S_1, \dots , S_n$. Each player has a payoff function
$\pi_i$ mapping outcomes (elements of $S_1 \times \dots \times S_n$) to real numbers. Recall that a potential function for
such a game is defined by the following property: for every outcome $\ssb \in S_1 \times \dots \times S_n$, every player $i$, and every
deviation $s'_i \in S_i$.
\[ \pi_i(s'_i, \ssb_{-i}) - \pi_i(s_i,\ssb_{-i}) = \Phi(s'_i,\ssb_{-i}) - \Phi(s_i,\ssb_{-i}).\]
A team game is a game in which all players have the same payoff function: $\pi_1(\ssb) = \dots = \pi_n(\ssb)$
for every outcome $\ssb$. In a dummy game, the payoff of every player $i$ is independent of its strategy:
$\pi_i(s_i, \ssb_{-i}) = \pi_i(s'_i, \ssb_{-i})$ for every $\ssb_{-i}$ and every $s_i, s'_i\in S_i$.
Prove that a game with payoffs $\pi_1, \dots ,\pi_n$ is a potential game (i.e., admits a potential function) if and
only if it is the sum of a team game $\pi^t_1,\dots,\pi_n^t$ and a dummy game $\pi^d_1,\dots,\pi_n^d$ ({\em i.e.,}
$\pi_i(\ssb)=\pi^t_i(\ssb) + \pi^d_i(\ssb)$ for every $i$ and $\ssb$.)
\item (4 points)
Show that in every network cost-sharing game, the PoA is at most $n$, where $n$ is the number of players.
\item (3 points)
Consider an atomic selfish routing game with $m$ edges and cost functions taking values in $\{1,2,\dots,H\}$. Prove that best-response dynamics converges to a PNE in at most $mH$ iterations.
\item
Consider $n$ identical machines and $m$ selfish jobs (the players). Each job $j$ has a processing time $p_j$. Once
jobs have chosen machines, the jobs on each machine are processed serially from shortest to longest. (You
can assume that the $p_j$'s are distinct.) For example, if jobs with processing times $1, 3,$ and $5$ are scheduled
on a common machine, then they will complete at times $1, 4,$ and $9,$ respectively. The following questions
concern the game in which players choose machines in order to minimize their completion times. The objective function as a planner is to minimize the total completion time $\sum_{j=1}^m C_j$, where $C_j$ is the completion time job $j$.
\begin{itemize}
\item[$(a)$] (2 points) Define the rank $R_j$ of job $j$ in a schedule as the number of jobs on $j$'s machine with processing
time at least $p_j$ (including $j$ itself). For example, if jobs with processing times $1, 3,$ and $5$ are scheduled
on a common machine, then they have ranks $3, 2,$ and $1$, respectively.
Prove that in these scheduling games, the objective function value of an outcome can also be written
as $\sum_{j=1}^m p_j R_j$.
\item[$(b)$] (2 points) Prove that the following algorithm produces an optimal outcome: $(i)$ sort the jobs from
largest to smallest; $(ii)$ for $i = 1, 2, \dots ,m$, assign the $i^{th}$ job in this ordering to machine $i$ mod $n$
(where machine $0$ means machine $n$).
\item[$(c)$] (3 points) Prove that for every such scheduling game, the expected objective function value of every
coarse correlated equilibrium is at most twice that of an optimal outcome.
(Hint: The ($\lambda,\mu$)-smoothness condition (see notes provided) was required for all pairs $\ssb^*, \ssb$ of
outcomes. Weaken the definition so that this condition only needs to hold for some optimal outcome $\ssb^*$ and all outcomes $\ssb$.
Observe that PoA of coarse correlated equilibria remains at most $\frac{\lambda}{1-\mu}$ assuming only this weaker condition (with the
same proof as before). Prove that this scheduling game satisfies this weaker condition for $\lambda=2$ and $\mu=0$.)
\end{itemize}
\end{enumerate}
\vspace{1in}
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item Give example of a two-player game with pure NE, where best response dynamics can cycle.
\item Give example of a potential game where the strategy profile achieving minimum potential does not give the minimum cost NE.
[Hint: Try cost-sharing game.]
\item Prove that if a game admits two potential functions $\Phi_1$ and $\Phi_2$, then $\Phi_1$ and $\Phi_2$ differ by
a constant. That is, for some $c\in \mathbb R$, $\Phi_1(\ssb) - \Phi_2(\ssb)=c$ for every outcome $\ssb$ of the game.
Thus, it is well defined to speak of ``the potential function maximizer'' of a potential game.
\item Prove that a finite game admits a potential function if and only if for every two outcomes
$\ssb^1$ and $\ssb^2$ that differ in two players' choices, say players $i$ and $j$,
\[(\pi_i(s_i^2, \ssb_{-i}^1) - \pi_i(\ssb^1)) + (\pi_j(\ssb^2) - \pi_j(s_i^2,\ssb^1_{-i}))= (\pi_j(s_j^2, \ssb^1_{-j}) -\pi_j(\ssb^1)) +
(\pi_i(\ssb^2) - \pi_i(s_j^2, \ssb_{-j}^1)) \]
\item As we discussed in class, a congestion game is like an atomic selfish routing game except we drop the
assumption that strategies represent paths in a network. That is, there is a ground set $E$ (previously, the
edges), and each $e \in E$ has a cost function $c_e$. Each player $i$ has a strategy set $S_i$, and each strategy $s_i \in S_i$
is a subset of $E$ (previously, a path). In an outcome $\ssb=(s_1,\dots,s_n)$, if $x_e$ players are using a strategy that contains $e$,
then player $i$'s cost is $\sum_{e\in s_i} c_e(x_e)$.
We showed in class that every congestion game is a potential game.
\medskip
Next we prove the converse. Two games $G_1$ and $G_2$ are isomorphic if: (i) they have the same number $k$ of players; (ii) for each
$i$, there is a bijection $f_i$ from the strategies $A_i$ of player $i$ in $G_1$ to the strategies $B_i$ of player $i$ in $G_2$; and
(iii) these bijections preserve payoffs, so that $\pi_i^1(s_1,\dots,s_n) = \pi_i^2(f_1(s_1),\dots f_n(s_n))$ for every player $i$ and
outcome $(s_1,\dots,s_n)$ of $G_1$. (Here $\pi^1$ and $\pi^2$ are the payoff functions of $G_1$ and $G_2$ respectively).
\begin{itemize}
\item[$(a)$] Prove that every team game (see Problem 5) is isomorphic to a congestion game.
\item[$(b)$] Prove that every dummy game (see Problem 5) is isomorphic to a congestion game.
\item[$(c)$] Prove that every potential game is isomorphic to a congestion game.
\end{itemize}
\item
The multiplicative weights algorithm requires advance knowledge of the time horizon $T$ to set the parameter $\eta$. Modify the algorithm so that it does not need to know $T$ a priori. Your algorithm should have expected regret at most $b\sqrt{(\ln{n})/T}$ for all sufficiently large $T$ and for every adversary, where $b>0$ is a constant independent of $n$ and $T$.
\item This problem concerns combinatorial auction where each bidder $i$ has a unit-demand valuation $v_i$. This means that there are value $v_{i1},\dots, v_{im}$ such that $v_i(S) = \max_{j \in S} v_{ij}$ for every subset $S$ of items.
Consider a payoff-maximization game in which each bidder $i$ submits one bid $b_{ij}$ for each item $j$ and easy item is sold separately using a second-price single-item auction. Assume that each bid $b_{ij}$ lies between $0$ and $v_{ij}$. The utility of a bidder is her value for the items won less her total payment. For example, if bidder $i$ has values $v_{i1}$ and $v_{i2}$ for two items, and wins both items when the second-highest bids are $p_1$ and $p_2$, then her utility is $\max\{v_{i1}, v_{i2}\} - (p_1 + p_2)$.
\begin{itemize}
\item Prove that the POA of PNE in such a game can be at most $\frac{1}{2}$.
\item Prove that the POA of CCE in every such game is at least $\frac{1}{2}$.
\end{itemize}
\end{itemize}
\end{document}