\documentclass[11pt]{article}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\bb}{{\mathbf{b}}}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 598RM: Algorithmic Game Theory, Fall 2020}
\\[0.5ex]
\textbf{HW 1 (due on Friday, 25th Sept at 11:59pm CST)}
\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.
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 ({\em Competitive Equilibrium: Warm-up})
\begin{enumerate}
\item (3 points) Compute equilibrium prices and allocation for the following Fisher market. Show that the resulting allocation is Pareto optimal.
Market with two agents $A=\{1,2\}$, and two goods $G=\{1,2\}$. Budgets of the agents are $B_1 = 5, B_2 = 2$, and their utility functions are $v_1(x_{11}, x_{12}) = 3x_{11} + 4x_{12}$ and $v_1(x_{11}, x_{12}) = x_{11} + 2x_{12}$.
\item(7 points) {\em (fairness properties)}
Given a Fisher instance where budget of agent $i$ is $B_i$ (budget can also be thought of as weight/clout/importance for a fair-division task), show that a CE allocation satisfies the following:
\begin{itemize}
\item It is weighted envy-free
\item It is weighted proportional
\item The weighted Nash welfare maximizing allocation gives a CE.
\end{itemize}
\end{enumerate}
\item (10 points) {\em (Proportional response (PR) dynamics)}
Consider a proportional response function $f:D\rightarrow D$, where $D=\{\bb\in \mathbb R_+^{mn}\ |\ \sum_{j\in G} b_{ij}=B_i\}$: for a $\bb\in D$, if $\bb'=f(\bb)$ then construct $\bb'$ from $\bb$ as follows:
Think of $b_{ij}$ as the bid of agent $i$ on good $j$. Price of good $j$ is the total bids collected on it, i.e., $p_j=\sum_{i\in A} b_{ij}$. And the allocation is proportional to the bid, i.e., $x_{ij}=\frac{b_{ij}}{p_j}$. (In economics such a market implementation is known as {\em Trading-post}, introduced by Shapley and Shubik in 1977.)
Based on the utilities obtained, agents update their bids (proportional to the utility received from the previous bid):
\[
b'_{ij} = B_i \frac{v_{ij} x_{ij}}{\sum_{k\in G} v_{ik} x_{ik}}
\]
Show that, given a CE $(p^*,X^*)$ the corresponding bids $b^*_{ij} = p^*_j x^*_{ij}$ for all $(i,j)$ forms a fixed-point of $f$, i.e., $f(\bb^*)=\bb^*$.
\medskip
\medskip
\noindent{\bf Remark.} In the proportional response dynamics agents update their bids as per function $f$ every day. That is, starting with an arbitrary bid profile $b(0)\in D$, bids on day $t\ge 1$ is $b(t) = f(b(t-1))$. This is a well-studied dynamics that is known to converge to the fixed-point a.k.a. CE. The dynamics can be extended to more general utility functions like CES, gross-substitutes, and is known to converge for these too. See slides for the references.
\item ({\em On the computation of CE})
\begin{enumerate}
\item (7 points) Show that, for the case of Fisher model with binary valuations, {\em i.e.,} $v_{ij}\in \{0,1\}$ for all $(i,j) \in A \times G$, the algorithm we discussed terminates in $O(n)$ many iterations of the outer while loop (recall that $n=|A|$); take the starting prices to be $p_j=\epsilon,\ \forall j\in G$ where $0 < \epsilon < \min_{i\in A} B_i/m$.
\medskip
\noindent{\bf Remark.} Observe that both the events of our algorithm can be computed in {\em strongly polynomial-time}. Therefore, the proof of the above statement shows that the algorithm runs in strongly polynomial time for binary instances.
\item (3 points) Consider a bi-valued HZ instance: for each agent $i$ her value for good for good $j$ is $v_{ij} \in \{a_i,b_i\}$ for all $j\in G$, where $0\le a_i < b_i$. Reduce the computation of HZ equilibrium for this instance to finding HZ equilibrium in a binary valued instance where for all $(i,j)$ pairs $v_{ij} \in \{0,1\}$.
\end{enumerate}
\item ({\em EFX}) The following questions are regarding fair-division of a set of indivisible goods.
\begin{enumerate}
\item(2 points) Show an example with additive valuations for which the envy-cycle procedure does not give an EFX allocation.
\item(3 points) Show that an EFX allocation exist when agents have identical general monotone valuations.
\item(3 points) Design a polynomial-time algorithm to obtain an EFX allocation when agents have identical additive valuations.
\item(2 points) Design a polynomial-time algorithm to obtain an EFX allocation when there are two agents with additive valuations.
\end{enumerate}
\item ({\em MMS and Prop1})
Suppose there are $m$ indivisible goods, and $n$ agents with additive valuations.
\begin{enumerate}
\item(2 points) Show that MMS allocations exist when $n=2$.
\item(3 points) EF1 implies 1/n-MMS.
\item(2 points) Show an example where an MMS allocation is not EF1.
\item(3 points) Show that envy-freeness up to one item (EF1) implies proportionality up to one item (Prop1), but Prop1 does not imply EF1.
\end{enumerate}
\item ({\em Max Nash Welfare w/ Indivisible Goods})
Consider a fair-division instance with set $M$ of $m$ indivisible goods, and $n$ agents with additive valuations. Show that an allocation that maximizes the
Nash welfare (MNW) over the set $\Pi(M)$ of feasible integral allocations, i.e., $\mbox{arg}\max_{(A_1,\dots,A_n)\in \Pi(M)} \displaystyle\Pi_{i=1}^n v_i(A_i)$,
\begin{enumerate}
\item(4 points) is EF1 + PO.
\item(2 points) may not be EFX.
\item(4 points) is EFX when agents have identical valuations.
\end{enumerate}
\end{enumerate}
\end{document}