\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}}}
\newcommand{\argmax}{{\mbox{argmax}}}

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

\begin{center}
\LARGE
\textbf{CS 580RM: Algorithmic Game Theory, Fall 2023}
\\[0.5ex]
\textbf{HW 1 (due on Friday, Sept 15th 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 Consider a market $\mathcal M$ with $n$ agents and $m$ divisible goods, where supply of good $j$ is $q_j$ and the valuation of agent $i$ is defined by a monotonically non-decreasing concave function $V_i: \mathbb R_+^m\rightarrow \mathbb R_+$. A {\em competitive equilibrium with equal income (CEEI)} of such a market is a pair $(X, p)$ where $p$ is a price vector $(p_1,\dots,p_m)$, $p_j$ is the price-per-unit of good $j$ and $X=(X_1,\dots,X_n)$ is an allocation of goods to agents s.t.,

\begin{itemize}
    \item {\bf Optimal Bundle.} For each agent $i$, $X_i \in \argmax_{Y\ge 0: \sum_j p_j Y_j \le 1} V_i(Y)$.
    \item {\bf Demand equals Supply.} For each good $j$, $\sum_{i\in [n]} X_{ij} \le q_j$, and whenever $p_j>0$ we have $\sum_{i\in [n]} X_{ij} = q_j$. 
\end{itemize}
\begin{enumerate}
    \item (5 points) Show that it is without loss of generality to assume that $q_j=1$ for all goods $j$, that is, to assume that the supply of every good is one. Formally, come up with another market $\mathcal M'=([n],[m],(q'_j)_{j\in [m]},(V'_i)_{i\in [n]})$ such that $q'_j=1,\ \forall j\in[m]$, and show that a CEEI of $\mathcal M'$ can be mapped to a CEEI of $\mathcal M$.
    \item (5 points) Show that when the DPSV algorithm is executed to compute a CEEI of such a market, Event $2$ of the algorithm can always be computed in polynomial time. That is, the value of $\alpha$ for which a new MBB edge appears between some agent $i\in A_D$ and some good $j\in G_F,$ and the pair $(i,j),$ can be computed in polynomial time. Here, $\alpha$ is the constant by which the prices of the goods in $G_D$ are scaled in one iteration of the algorithm. Set $A_D$ consists of agents with MBB edges to goods in $G_D$ before $\alpha$ starts increasing, and $G_F$ is the set of goods with demand = supply,  meaning if the market consisted only of the subset $(A_F,G_F),$ then the prices of goods in $G_F$ and their allocation to $A_F$ satisfy the requirements of a CEEI. (See \href{https://courses.engr.illinois.edu/cs580/fa2023/Slides/Lec3-CE-Algorithm.pdf}{Lecture 3 slides} for further details)
\end{enumerate}


\item ({\em Indivisibles: Short Questions})
\begin{enumerate}
    \item (2 points) Give an example with general monotone valuations where an EF1 allocation is not Prop1. 
	\item (3 points) Give an example with additive valuations where the round robin algorithm achieves better social welfare ($\sum_i V_i(A_i)$) than the envy-cycle-elimination algorithm under certain choices.
    \item (2 points) Give an example with additive valuations where an EF1+PO allocation is not EFX.
    \item(2 points) For additive valuation functions, we showed $MMS_i\le \frac{v_i(M)}{n}$ for all agents $i.$ Give an example with submodular valuation functions where this is not true, and in fact $MMS_i=v_i(M)$ for all agents $i$. 
\item (1 point) Prove that if an $\alpha$-MMS allocation exists for an instance, then an $\alpha$-MMS+PO allocation also exists. 
\end{enumerate}    

\item({\em Algorithm Design})
\begin{enumerate}
    \item (5 points) Consider an instance with additive valuations where items are identically ordered. That is, there exists an ordering of items $g_1,g_2, \dots,g_m$ such that for each agent $i$,
    \[ v_{ig_1} \ge v_{ig_2} \ge \dots \ge v_{ig_m}. \]
    Show that the {\em envy-cycle elimination} algorithm gives an EFX allocation when the items are considered in a particular order. 
    \item (5 points) In this question, we will develop an efficient algorithm to compute a Prop1+PO allocation. 
    We want to find a Prop1+PO allocation of $m$ indivisible items, among $n$ agents, each with an additive valuation function, namely $v_i(S)=\sum_{j\in S} v_{ij}$ for any $S\subseteq [m]$. 
    
    Consider the corresponding market with the same set of agents and items, but now the items are assumed to be divisible. Agent $i$'s valuation function is extended to be defined for fractional allocations as follows: for allocation $X_i=(X_{i1},\dots, X_{im})$ to agent $i$ her value is $v_i(X_i)=\sum_{j\in [m]} v_{ij} X_{ij}$. Let prices $p=(p_1,\dots,p_m)$ and allocation $X=(X_1,\dots,X_n)$ be a CEEI of this market. 
    We know that $X$ is both PO and proportional. However, it is a fractional allocation and, therefore, has to be rounded to get a feasible allocation of the original problem with indivisible items.
    
    Assume that the allocation graph is acyclic (this is wlog). That is, the bipartite graph $G=([n]\cup [m],E)$ between agents and items with edge set $E=\{(i,j)\ |\ X_{ij}>0\}$ has no cycles. Thus it is a set of trees, i.e., $G=\cup_{k=1}^d T_k$. 
    
    {\bf Rounding.} For each tree $T_k$, pick any agent $a\in T_k$ and think of $T_k$ as rooted at $a$. Now, for each agent node $i$ in $T_k$, all of its children are item nodes. We round the fractional allocation so every agent $i\in T_k$ gets all its children in her bundle. Let the resulting integral allocation be $A_i$ for agent $i$. 
    
    \begin{itemize}
        \item Show that $(A_1,\dots,A_n)$ together with prices $p=(p_1,\dots,p_m)$ is a CE of the above market where the agents' budgets are different than one. By the first welfare theorem, this implies that this allocation is PO. 
        \item Show that $(A_1,\dots, A_n)$ is Prop1. \\
        {\em [Hint: Note that, $v_i(X_i)\ge V_i([m])/n$, and  $\{j\ |\ X_{ij}>0\} \subseteq A_i$. At most, how many items does an agent lose from her fractional allocation as we round it? That is, what is an upper bound on $|\{j\ |\ X_{ij}>0\} \setminus A_i|$? }
    \end{itemize}

\end{enumerate}

\item ({\em MMS})
\begin{enumerate}
\item (3 points) Construct an instance with general monotone valuations, such that there does not exist an $\alpha$-MMS allocation for any $\alpha>0$. 
\item (7 points) For the case with additive valuation functions, where $v_i(M) = n$ for all agents $i$, show that when $v_{ij}\le \epsilon$ for all agents $i$ and goods $j$, an EF1$+(1-\epsilon)$-MMS allocation exists and can be computed in polynomial time. 
\end{enumerate}

\item({\em Bonus})
\begin{enumerate}
    \item Prove that when agents have binary additive valuation functions (that is, $v_{ij}\in \{0,1\}$ for all $$(i,j)$$), then an EF1+PO allocation can be found in polynomial time.
\item For an $\alpha\in[0,1]$, an $\alpha$-EFX allocation is defined as: for all pairs of agents $i,j,$ and every good $g\in A_j,$ we have $v_i(A_i) \ge \alpha v_i(A_j\backslash \{g\}).$ Prove that when the valuation functions of the agents are subadditive, $\frac{1}{2}$-EFX $\Rightarrow$ $\alpha$-MMS for $\alpha=1/(cn),$ for some constant $c$, where $n$ is the number of agents.
\item Prove that, for additive valuations over indivisible goods, an allocation that maximizes the Nash welfare, namely $\argmax_{(A_1,\dots, A_n)} \Pi_{i\in[n]} V_i(A_i)$, is also EF1+PO.
\item For the assignment, valuations, also known as OXS valuations, show that computing the MMS value of an agent is strongly NP-hard. 
\end{enumerate}
\end{enumerate}
\end{document}