\documentclass[11pt]{article}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
\usepackage{bm}
\usepackage[ruled,vlined,linesnumbered,noresetcount]{algorithm2e}
\newcommand{\ssb}{\mbox{\boldmath $s$}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 598RM: Algorithmic Game Theory, Fall 2020}
\\[0.5ex]
\textbf{HW 3 (due on Sunday, 22nd Nov at 11:59pm CT)}
\end{center}
\noindent{\bf Instructions:}
\begin{enumerate}
\item We will grade this assignment out of a total of 60 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. We will upload submission instructions on the course webpage and Piazza.
\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
\noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}
\begin{enumerate}
\item
\begin{enumerate}
\item (5 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 (5 points) 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.]
\end{enumerate}
%----------------------------------------------------------------------
\item (10 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 Consider a combinatorial auction with $n$ bidders and $n$ items where each bidder $i$ has a unit-demand valuation $v_i$. This means that $v_i(S) = \max_{j \in S} v_{i,j}$ for every subset $S$ of items. We assume that $v_{i,j} > 0$ for all $i, j$.
In this auction, each bidder $i$ submits one bid $b_{i,j}$ for each item $j$, and each item is sold separately using a second-price single-item auction. Assume that $b_{i,j} \in (0, v_{i,j})$ for all $i,j$. The utility of a bidder is her value for the items won, minus 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)$. Let $G = (A, B)$ be a bipartite graph where $A$ is the set of bidders and $B$ is the set of items.
\begin{itemize}
\item (7 points) Show that every allocation $\pi$ of items to bidders that maximizes the Social Welfare $\left(\sum_{i} {v_i(\pi(i))}\right)$ induces a matching on $G$.
\item (8 points) Show that the PoA of PNE in such a game can be at most $2$.
\end{itemize}
\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{enumerate}
\item (4 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 (4 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 (7 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.
{\em {\bf 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{enumerate}
\item
\begin{enumerate}
\item (2 points) Give an example of a game with $2$ players that admits a PNE, but the best-response dynamics cycles.
\item This problem studies a scenario with $n$ agents, where agent $i$ has a positive weight $w_i > 0$. There are $m$ identical machines. Each agent chooses a machine, and wants to minimize the load of her machine, defined as the sum of the weights of the agents who choose it. A pure Nash equilibrium in this game is an assignment of agents to machines so that no agent can
unilaterally switch machines and decrease the load she experiences.
Consider the following restriction of best-response dynamics:
\parbox{\linewidth}{\LinesNumberedHidden
\begin{algorithm}[H]
\caption{{\bf Maximum Weight Best-Response Dynamics}}
While the current outcome $\bm{s}$ is not a PNE:
$\qquad$ among all agents with a beneficial deviation, let $i$
denote an agent \\
$\qquad \quad$ with the largest weight $w_i$ and
$s'_i$ a best response to $\bm{s}_{-i}$
$\qquad$ update the outcome to $(s'_i, \bm{s}_{-i})$
\end{algorithm}}
\begin{enumerate}
\item (3 points) Show that, starting from the outcome $\bm{s}_0$ where no agent has selected any machines (all machines have load $0$), the Maximum Weight Best-Response Dynamics converges to a PNE in exactly $n$ iterations.
\item (5 points) Show that, starting from any outcome $\bm{s}$, the Maximum Weight Best-Response Dynamics converges to a PNE in at most $n$ iterations.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{document}