\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 4 (due on Tuesday, 15th Dec at 11:59pm CT)} \end{center} \noindent{\bf Instructions:} \begin{enumerate} \item We will grade this assignment out of a total of 80 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 (15 points) \begin{itemize} \item[$(a)$] (2.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)$] (2.5 points) Consider an arbitrary single-parameter environment with feasible set $X$. Prove that the welfare-maximizing allocation rule \begin{equation}\label{eq.1} x(b) = \mbox{argmax}_{x \in X} \sum_{i=1}^n b_i x_i \end{equation} is monotone. [For the definition of monotonic allocation rule, See Definition 4.2 of \url{http://theory.stanford.edu/~tim/f13/l/l3.pdf}] \item[$(c)$] (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? \item[$(d)$] (5 points) Consider a combinatorial auction in a which a bidder can submit multiple bids under different names, unbeknownst to the mechanism. The allocation and payment of a bidder is the union and sum of the allocations and payments, respectively assigned to all of its pseudonyms. Show that the following is possible: a bidder in a combinatorial auction can earn higher utility from the VCG mechanism by submitting multiple bids than by bidding truthfully. Can this ever happen in the Vickrey auction? Give a brief explanation. \end{itemize} \item (10 points) Combinatorial auctions Recall the sponsored search auction problem discussed in class: there are $k$ slots, the $j^{th}$ slot has a known click-through rate (CTR) of $\alpha_j$ (non-increasing in $j$), and the payoff of bidder $i$ in slot $j$ is $\alpha_j (v_i - p_j)$, where $v_i$ is the (private) value-per-click of the bidder and $p_j$ is the price charged per-click in that slot. For historical reasons, modern search engines do not use the truthful auction discussed in class. Instead, they use auctions derived from the Generalized Second-Price (GSP) auction, defined as follows: \begin{itemize} \item[$(1)$] Rank advertisers by bid; assume without loss of generality that $b_1\ge b_2 \ge \dots\ge b_n$. \item[$(2)$] For $i = 1, 2, \dots , k$, assign the $i^{th}$ bidder to the $i^{th}$ slot. \item[$(3)$] For $i = 1, 2, \dots , k$, charge the $i^{th}$ bidder a price of $b_{i+1}$ per click. \end{itemize} \begin{enumerate} \item (1 points) Prove that for $k = 2$ and any sequence $\alpha_1 \ge \alpha_2>0$, there exist valuations for the bidders such that the GSP auction is not truthful. (This in fact holds for any $k \ge 2$). \item (2 points) Fix CTRs for slots and valuations-per-click for bidders. We can assume that $k = n$ by adding dummy slots with zero CTR (if $k < n$) or dummy bidders with zero valuation (if $k > n$). A bid vector $b$ is an equilibrium of GSP if no bidder can increase its payoff by changing its bid. Verify that this translates to the following conditions, assuming that $b_1 \ge b_2 \ge \dots \ge b_n$: for every $i$ and higher slot $j < i$, \[ \alpha_i(v_i - b_{i+1}) \ge \alpha_j (v_i - b_j);\] and for every lower slot $j > i$, \[\alpha_i(v_i - b_{i+1})\ge \alpha_j (v_i - b_{j+1}).\] {\em {\bf Hint:} Derive these by adopting $i$'s perspective and ``targeting'' the slot $j$.} \item (3 points) A bid vector $\mathbf b$ with $b_1 \ge \dots \ge b_n$ is envy-free if for every bidder $i$ and slot $j \neq i$, \[\alpha_i(v_i - p_i) \ge \alpha_j (v_i - p_j);\] where $p_j = b_{j+1}$ Verify that an envy-free bid vector is necessarily an equilibrium. (The terminology ``envy-free'' stems from the following interpretation: for the current price-per-click is $p_j$ of slot $j$; then the above inequalities say: ``each bidder $i$ is as happy getting its current slot at its current price as it would be getting any other slot and that slot's current price''.) {\em {\bf Hint:} You might want to first prove that the bidders must be sorted in non-increasing order of valuations.} \item (4 points) Prove that, for every set of $\alpha_j$s and $v_i$s, there is an equilibrium of the GSP auction for which the outcome (i.e., the assignment of bidders to slots) and the prices paid precisely match those of the truthful auction discussed in class. If you want, you can assume that the CTRs are strictly decreasing. {\em {\bf Hint:} Recall that using Myerson's lemma we know a closed-form solution for the payments made by the truthful auction (see (8) and (9) in \url{http://theory.stanford.edu/~tim/f13/l/l3.pdf}). What bids would yield these payments in a GSP auction? Part (c) might be useful for proving that they form an equilibrium.} \end{enumerate} \item (5 points) Consider a combinatorial auction on $m$ goods where you know a priori that every bidder is unit demand. This means that the valuation of a bidder $i$ can be described by $m$ private parameters (one per good) $v_{i1},\dots, v_{im}$, and its valuation for an arbitrary set $S$ of goods is defined as $max_{j\in S} v_{ij}$. Prove that the VCG mechanism can be implemented in polynomial time for unit-demand bidders. \item (10 points) Consider a set $M$ of distinct items. There are $n$ bidders, and each bidder $i$ has a publicly known subset $T_i\subseteq M$ of items that it wants, and a private valuation $v_i$ for getting them. IF bidder $i$ is awarded a set $S_i$ of items at a total price of $p$, then her utility is $v_i x_i - p$ where $x_i$ is $1$ if $T_i \subseteq S_i$ and $0$ otherwise. This is a single-parameter environment. Since each item can only be awarded to one bidder, a subset $W$ of bidders can all receive their desired subsets simultaneously if and only if $T_i \cap T_j=\emptyset$ for each distinct $i,j \in W$. \begin{itemize} \item[$(a)$](3 points) Prove that the problem of computing a welfare-maximizing feasible outcome, given the $v_i$'s and $T_i$'s as input, is NP-hard. \item[$(b)$](3 points) Here is a greedy algorithm for the social welfare maximization problem, given bids $b$ from the bidders. \begin{center} \begin{tabular}{|l|}\hline \hspace{5pt}Initialize $W=\emptyset$ and $X=M$ \\ \hspace{5pt}Sort and re-index the bidders so that $b_1\ge b_2 \ge \dots \ge b_n$ \\ \hspace{5pt}{\bf for} i=1,2,\dots,n {\bf do} \\ \hspace{15pt} {\bf if} $T_i \subseteq X$ {\bf then}\\ \hspace{25pt} remove $T_i$ from $X$ and add $i$ to $W$\\ \hspace{5pt}{\bf end for}\\ \hspace{5pt}Return winning bidders $W$.\\ \hline \end{tabular} \end{center} Does this algorithm define a monotone allocation rule? Prove it or give an explicit counterexample. \item[$(c)$] (4 points) If the above allocation rule is monotone then design a polynomial-time procedure/algorithm to compute payment of the winners. Otherwise do nothing. \end{itemize} \item (5 points) This problem considers a variation of the Bulow-Klemperer theorem (Nov 12 lecture). Consider selling $k \ge 1$ identical items (with at most one given to each bidder) to bidders with valuations drawn iid from $F$, where $F$ is a regular distribution (i.e., corresponding $\phi^{-1}$ is monotonically increasing function). Prove that for every $n \ge k$, the expected revenue of the Vickrey auction (with no reserve) with $n+k$ bidders is at least that of the Myerson's optimal auction for $F$ with $n$ bidders. \\ (Hint: Myerson's optimal auction will be Vickrey with reserve $\phi^{-1}(0)$, {\em i.e.,} discard bids below $\phi^{-1}(0)$, give the item to $k$ highest bidders and charge them $\max\{(k+1)^{th} \mbox{highest bid}, \phi^{-1}(0)\}$) \item (5 points) Consider the reverse auction we briefly talked about in class: $A$ denotes the set of bidders who are willing to sell the spectrum they hold. There is a set $F \subseteq 2^B$ of feasible sets that is upward closed (i.e., supersets of feasible sets are again feasible), i.e., if $S\in F$ then we can repack $S$ in available range if spectrum of $S$ is acquired. \begin{itemize} \item Initialize $S = A$. \item While there is a bidder $i \in S$ such that $S \setminus \{i\}$ is feasible: \hspace{2cm} (*) Delete some such bidder $i$ from $S$ such that $S\setminus \{i\}$ is feasible. \item Return S. \end{itemize} Suppose we implement the step (*) using a scoring rule, which assigns a number to each bidder $i$. At each iteration, the bidder with the largest score (whose deletion does not destroy feasibility of $S$) gets deleted. The score assigned to a bidder $i$ can depend on $i$’s bid, the bids of other bidders that have already been deleted, the feasible set $F$, and the history of what happened in previous iterations. (Note a score is not allowed to depend on the value of the bids of other bidders that have not yet been deleted.) Assume that the scoring rule is increasing -- holding everything fixed except for $b_i$, $i$’s score is increasing in its bid $b_i$. Then, show that the allocation rule above is monotone: for every $i$ and $b_{-i}$, if $i$ wins with bid bid $b_i$ then she will keep winning with any bid less than $b_i$. \item (10 points) [Fair-division] Suppose there are $n$ agents with additive valuations for $m$ goods, \textcolor{red}{ such that EVERY AGENT'S MMS VALUE IS $1$}. If every good has value at most $1$ for every agent, and there are at most $n$ goods with value higher than $1/5$ for any agent, then prove that there is a polynomial time algorithm to compute a $4/5$-MMS allocation of the goods among the agents. (You can assume without loss of generality that the ordinal preferences of all agents are the same. See \cite{BouveretL16} for a proof.) \item (10 points) Consider a game where $n$ players are allocating a shared bandwidth of $1$. Each player $i$ chooses an amount $1 \ge x_i \ge 0$ and the utility of player $i$ is $U_i(x_i ,x_{−i}) = x_i(1- \sum_{j=1}^n x_j)$. Note that if $\sum_{j=1}^n x_j > 1$, all players have a non-positive utility. \begin{itemize} \item (5 points) Does this game have a Nash equilibrium? If it does, give a Nash equilibrium. \item (5 points) Is it a potential game? Prove your answer. \end{itemize} \item (10 points) Consider the following weighted generalization of the network cost-sharing game. For each player $i$, we have a weight $w_i>0$. As before, each player selects a single path connecting her source and sink. But instead of sharing edge cost equally, players are now assigned cost shares in proportion to their weight. In particular, for a strategy vector $S$ and edge $e$, let $S_e$ denote those players whose path contains $e$, and let $W_e=\sum_{i \in S_e} w_i$ be the total weight of these players. Then player $i$ pays $c_e w_i/W_e$ for each edge $e \in P_i$. Note that if all players have the same weight, this is the original game. \begin{itemize} \item (4 points) Show that, in general, this game does not have an exact potential function. \item (4 points) Show that there exists a potential function $\Phi$ such that, \[ \begin{array}{l} \forall i, \forall {\mbox paths} P_i,P'_i:\ \ \ (\Phi(P_i,P_{-i}) - \Phi(P'_i, P_{-i})) (C_i(P_i,P_{-i}) - C_i(P'_i,P_{-i})) \ge 0 \\ \forall i, \forall {\mbox paths} P_i,P'_i:\ \ \ \Phi(P_i,P_{-i}) = \Phi(P'_i, P_{-i}) \Leftrightarrow C_i(P_i,P_{-i}) = C_i(P'_i,P_{-i}) \end{array} \] \item (2 points) Using the above, show that the game has a pure Nash equilibrium. \end{itemize} \end{enumerate} \end{document}