\documentclass[11pt]{article}

\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{nicefrac}
\usepackage{boxedminipage}


\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{\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 2 (due on Friday, 7th 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 Nash equilibrium: existence})  
\begin{enumerate}
     \item (1 points) Does every zero-sum game has a Pure Nash equilibrium, where every player plays a single move with probability 1? Give a proof or a counter example to support your answer. 
    \item (2 points) Find a Nash equilibrium of the game whose payoff bimatrix is given in Table~\ref{tab:find-ne-3X3}.
    \begin{table}[h]
        \centering
        \begin{tabular}{|c|c|c|}
            \hline
             9,6 & 15,0 & -15,6 \\
            \hline
             0,20 & 9,6 & 17,6 \\
            \hline 
             9,-20 & 9,11 & 9,6 \\
            \hline
        \end{tabular}
        \caption{Payoff bimatrix of a 3X3 game}
        \label{tab:find-ne-3X3}
    \end{table}
    \item (4 points) Game $(A,B)$ is said to be symmetric if $B=A^T$. First note that, both players have the same number of moves in a symmetric game. Prove that a symmetric game always has a symmetric NE, i.e., NE $(x,y)\in \mathbb R^n \times \mathbb R^n$ such that $y=x$. 

   {\em[Hint: Modify Nash's proof]}
\end{enumerate}

\item ({\em NE to LCP})
\begin{enumerate}    
    \item (3 point) Is the problem of computing a Nash equilibrium scale invariant? That is, if $(x,y)$ is a NE of game $(A,B)$, then for $\lambda, \kappa \ge 0$ and $a,b \in \mathbb R$ is it also a NE of game $(\lambda A+ a, \kappa B +b)$? Justify your answer. 
 \item (3 points) Using the above, prove that finding NE in game $(A,B)$ reduces to finding a symmetric NE in a symmetric game.
\item (4 points) Using the above two, show that the problem of computing a Nash equilibrium of a $2$ player game $(A,B)$ reduces to solving an LCP (linear complementarity program) which the Lemke-Howson algorithm can solve (see Slide 2
 of \href{https://courses.grainger.illinois.edu/cs580/fa2023/Slides/Lec10-LH-PPAD.pdf}{lecture slides} where $M\ge 0$ matrix). 

\end{enumerate}

\item ({\em Other game and equilibrium notions})
\begin{enumerate}
\item(2 points) Compute all Nash equilibria of the game shown in Table \ref{tab:find-ne-4X4}.
\begin{table}[h]
        \centering
        \begin{tabular}{|c|c|c|c|}
            \hline
             -1.4 & 1,-8 & 10, -2 &  3,2 \\
            \hline
             3,-5 & 5,-2 & -10, -9 & 5,-4 \\
            \hline 
             -3,-2 & 4,-5 & -3, -5 & 8,-4  \\
            \hline
             -2,1 & 4,1 & 9, -5 & 4,0 \\
            \hline
        \end{tabular}
        \caption{Payoff bimatrix of a 4X4 game}
        \label{tab:find-ne-4X4}
    \end{table}

[Hint: Apply iterated dominance.]
\item(3 points) Alice and Bob are playing a game $(A,B)$ in rounds where in $t^{th}$ round they update their strategies as follows, starting at uniformly random strategies $x(0)$ and $y(0)$. 
\[
\begin{array}{llcl}
\forall i,\ \ \ & x_i(t) & = & x_i(t-1) \frac{(Ay)_i}{x^TAy}\\
\forall j, \ \ \ & y_j(t) & = & y_j(t-1) \frac{(x^TB)_j}{x^TBy}
\end{array}
\]

Show that $(x(t),y(t))=(x(t-1),y(t-1))$ if and only if $(x(t),y(t))$ is a Nash equilibrium.

\item(3 points) Given a game $(A,B)$, show that each of its correlated equilibria is also a coarse correlated equilibrium. 

\item(2 points) Write the normal form representation of the extensive form game with imperfect information shown in Figure \ref{fig:ext-form}.
\begin{figure}
    \centering
    \includegraphics[width=0.75\textwidth]{extform.PNG}
    \caption{Extensive Form Game}
    \label{fig:ext-form}
\end{figure}

\end{enumerate}

\item ({\em Stackelberg strategies}) (10 points)
Consider the following Stackelberg game with three firms. Firm 1 chooses the quantity of its production first, then firms 2 and 3 choose their quantities simultaneously after observing firm 1's quantities. Suppose that they produce the same product with different cost functions. Firm 1's total cost is $C_1(q_1) = 10 q_1 + 10$, firm 2's total cost is $C_2(q_2) = 8 q_2$, and firm 3's total cost is $C_3(q_3) = 4 q_3$. The firms produce identical goods and the market price is $P(q_1 q_2,q_3) = 300 - q_1 - q_2 - q_3$. What quantities do the firms produce in the subgame perfect equilibrium?


\item ({\em Bonus problems})
\begin{enumerate}
\item Design an algorithm to compute $1/2$-approximate NE equilibrium of a win-lose game $(A,B)$, where every entry in the matrices $A$ and $B$ is either 0 or 1. 
 \item Let $(A,I)$ be an imitation game where $A$ is of the form described in the previous sub-question. Show that the support set of strategies in a Nash equilibrium of player $2,$ whose payoff matrix is $I,$ is a subset of the support set of the Nash equilibrium strategy of player $1.$ That is, if $(x,y)$ is a Nash equilibrium of the game $(A,I),$ then $supp(y) \subset supp(x).$
 \item Using the above, show that there exists a PTAS to compute an $\epsilon$-approximate NE of imitation games. 
\end{enumerate}

\end{enumerate}

\end{document}


\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 (2 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$.
Recall that the PoA is
\[
PoA = \max_{B = (b_1, \dots, b_n) : B \text{ is a NE}} \frac{OPT}{\sum_i {\max_{j\in S^B(i)} v_{ij}}} = \max_{B = (b_1, \dots, b_n) : B \text{ is a NE}} \frac{\sum_i {v_{i, \pi(i)}}}{\sum_i {\max_{j\in S^B(i)} v_{ij}}}
\]
where $S^B(i)$ is the set of items assigned to agent $i$ at NE B, and $\pi$ represents the optimal allocation.
\end{itemize}
