\documentclass[11pt]{article}

\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb, bm}
\usepackage{hyperref}
\usepackage{nicefrac}
\usepackage{boxedminipage}
\usepackage{comment}
\usepackage[ruled,vlined,linesnumbered,noresetcount]{algorithm2e}

\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\bb}{{\mathbf{b}}}
\newcommand{\argmax}{{\mbox{argmax}}}
\newcommand{\E}{{\mathbb{E}}}
\newcommand{\ssb}{\mbox{\boldmath $s$}}
\newcommand{\ruta}[1]{\textcolor{red}{\bf *** Ruta: #1 *** }}

\begin{document}
\setlength{\parskip}{.1 in}

\begin{center}
\LARGE
\textbf{CS 580: Algorithmic Game Theory, Fall 2023}
\\[0.5ex]
\textbf{HW 3 (due on Monday, 30th October at 11:59pm CST)}
\end{center}


\noindent{\bf Instructions:}
\begin{enumerate}
\item We will grade this assignment out of a total of 40 points. 
\item You can work on any homework in groups of ($\le$) two. Submit only one assignment per group. First submit your solutions on Gradescope and you can add your group member after submission.
\item If you discuss a problem with another group then write the
names of the other group's members at the beginning of the answer for that problem. 
\item Please type your solutions if possible in Latex or doc whichever is suitable, and submit on Gradescope.
\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. 
You cannot refer to textbooks, handouts, or research papers that have not been listed. If you do use any approved sources, make 
sure you \textbf{cite them appropriately}, and make sure to \textbf{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 \href{https://www.ics.uci.edu/~vazirani/}{webpage}.
\end{enumerate}
\medskip
\medskip

\noindent\makebox[\linewidth]{\rule{\textwidth}{0.4pt}}


%----------------------------------------------------------------------
\begin{enumerate}
\item ({\em Routing games problem $1$})   \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 ({\em Routing games problem $2$}) (10 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 ({\em Best response Dynamics})
\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 $\mathbf{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}

\item ({\em Single parameter auctions})  (10 points) 
\begin{enumerate}
\item[$(a)$] (5 points) Consider a first price single item auction with set of bidders $A$. Let $n=|A|$, and private value $v_i$ of each bidder $i$ comes from a uniform distribution $[0,\ 1]$. Show that bid profile $(b_1,\dots,b_n)$ such that $b_i=\frac{(n-1)}{n} v_i,\ \forall i \in A$ is a Nash equilibrium.

{\bf Extra:} What is the expected revenue of the auctioneer at this Nash equilibrium? How does it compare with the expected revenue of Vickrey Auction?
\item[$(b)$] (5 points) Consider a single item second-price (Vickrey) auction with $n$ bidders. Assume that a subset $S$ of the bidders decide to collude, that is, the bidders in $S$ coordinate to submit false bids in order to maximize the sum of their payoffs. Under what conditions will this collusion be successful, and what should their collective strategy be?
\end{enumerate}

\item (Bonus Question) Show that computing the pure Nash equilibrium of a potential game is $\mathsf{PLS}$-complete. 

\end{enumerate}

\end{document}