\documentclass[11pt]{article}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
\usepackage[ruled,vlined,linesnumbered,noresetcount]{algorithm2e}
\newcommand{\A}{\mathcal{A}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\newenvironment{Q}
{%
\clearpage
\item
}
{%
\phantom{s}
\bigskip
\textbf{Solution.}
}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 598RM: Algorithmic Game Theory, Fall 2019}
\\[0.5ex]
\textbf{HW 2 (due on Sunday, 20th Oct 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 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}
%----------------------------------------------------------------------
\begin{Q}
\begin{enumerate}
\item (5 points) Consider a first price single item auction with set of bidders $A$. Let $n = |A|$ and the private value $v_i$ of each bidder $i$ come from a uniform distribution $[0,\ 1]$. Show that the bid profile $(b_1,\dots,b_n)$, where $b_i = \frac{(n-1)}{n} v_i, \ \forall i \in A$ is a Nash equilibrium.
{\em {\bf Hint:} Show that when $b_j= \frac{(n-1)}{n} v_j, \forall j \neq i$, then $b_i= \frac{(n-1)}{n} v_i$ is the best response of bidder $i$.}
\item (5 points) Consider a single item second-price 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}
\end{Q}
\begin{Q}
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''.)
\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}
\end{Q}
\begin{Q}
Consider combinatorial auctions for $m$ items among $n$ bidders. The goal of this exercise is to study special cases in which the VCG mechanism can be implemented efficiently. Suppose that each buyer sends as a bid a valuation vector of $2^m - 1$ numbers (a value for each subset of items, since $v_i(\emptyset) = 0$ for all $i$).
\begin{enumerate}
\item (2 points) Suppose that $m = 2$. Show that the VCG mechanism can be implemented in time $O(n^2)$. Provide both the allocation and the payments computed by the VCG mechanism.
\item (3 points) Suppose that $m = k$, for some fixed $k > 0$. Show that the VCG mechanism can be implemented in time $O(n^2 \cdot f(k))$, for some function $f$, where $f(k)$ does not depend on $n$. Notice that for fixed $k$, this is polynomial in $n$. Provide both the allocation and the payments computed by the VCG mechanism.
\item (5 points) Give an asymptotic upper bound on the number of items $m$ (with respect to the number of agents $n$) such that the VCG mechanism can be implemented in time that is polynomial in $n$. In particular, show that the VCG mechanism can be implemented in time $O(n^2 \cdot f(m))$, for some function $f$, where $f(m)$ does not depend on $n$, and give an asymptotic upper bound on $m$ such that this running time is polynomial in $n$.
{\em {\bf Hint:} Use dynamic programming.}
\end{enumerate}
\end{Q}
\begin{Q}
In a procurement auction with single-minded bidders, a single buyer (auctioneer) needs to buy a set $M$ of $m$ items from $n$ possible suppliers (bidders). Each supplier $i$ can provide a publicly known single set of items $S_i$ for a privately known price $v_i$. The buyer needs to buy all items, and aims to minimize the total price paid. Let $S = \{S_1, \dots, S_n\}$. Consider the following greedy algorithm $\A$ for the problem:
\begin{algorithm}[H]
\caption{$\A(m, n, S)$}
\SetAlgoLined
$R \leftarrow M$\;
$W \leftarrow \emptyset$\;
\Repeat{$R = \emptyset$}{
$j \leftarrow \argmax_k {\frac{|R \;\cap\; S_k|}{v_k}}$\;
$R \leftarrow R \setminus S_j$\;
$W \leftarrow W \cup \{j\}$
}
\KwResult{$W$}
\end{algorithm}
Let $v^*$ denote the total price paid in an optimal solution, $R_i$ denote the set of remaining items after the $i$-th step of the repeat loop (lines $3$ - $7$), $S_{j_i}$ denote the set of items that algorithm $\A$ selects at the $i$-th step, $v_{j_i}$ denote the price of set $S_{j_i}$, $x_i = \frac{|R_{i-1} \;\cap\; S_{j_i}|}{v_{j_i}}$ denote the items-per-unit of cost procured by the buyer at the $i$-th step and $z_i$ denote the number of remaining items left to procure after the $i$-th step.
\begin{enumerate}
\item (2 points) Show that for $i \geq 0$
\[
x_{i+1} \geq \frac{z_i}{v^*}
\]
\item (2 points) Show that for $i \geq 0$
\[
z_i \leq m \cdot \exp{\left(\sum_{k = 1}^i {-\frac{v_{j_k}}{v^*}}\right)}
\]
\item (2 points) Combine items $(a)$ and $(b)$ to show that $\A$ finds a $(1 + \ln{m})$-approximation to the optimal procurement.
\item (4 points) Deduce an incentive-compatible polynomial-time $(1 + \ln{m})$-approximation mechanism for procurement auctions among single-minded bidders.
{\em {\bf Hint:}
Notice that since this is a procurement auction, the allocation that maximizes the social welfare is the one that ``costs the least''. Show first that the procurement scheme defined by $\A$ is monotone decreasing (i.e. a winning bid $(b_i)$ is still a winning bid for any $b'_i \leq b_i$), and identify the ``critical values'' to be paid to the winning suppliers.
}
\end{enumerate}
\end{Q}
\begin{Q}
\textbf{(A fun bonus question)}
(10 points) Describe a real-life mechanism that you are not satisfied with, and suggest how to make it better.
\end{Q}
\end{enumerate}
\vspace{1in}
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item
This problem considers variations on the Bulow-Klemperer Theorem (Lecture 21).
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
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.
\item 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 $A\setminus 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 can depend on $i$, $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$.
\end{itemize}
\end{document}