\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\ssb}{\mbox{\boldmath $s$}}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 598RM: Algorithmic Game Theory, Fall 2018}
\\[0.5ex]
\textbf{HW 2 (due on Tuesday, Oct 16th at 3:30pm CST)}
\end{center}
\noindent{\bf Instructions:}
\begin{enumerate}
\item We will grade this assignment out of a total of 30 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. See instructions on the webpage on how to submit.
\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
\hline
\begin{enumerate}
%----------------------------------------------------------------------
\item (4 points)
\begin{itemize}
\item[$(a)$] (2 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 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}]
\end{itemize}
\item (5 points) Continuing $(1.b)$ above, restrict now to feasible set $X$ that contains only 0-1 vectors -- that is, each bidder either wins or loses. We can identify each feasible outcome with a ``feasible set'' of bidders (the winners). Assume that for every bidder $i$ there is an outcome in which $i$ does not win. Myerson's payment formula dictates that a sinning bidder pays her ``critical bid'' -- the infimum of the bids at which she would continue to win. (see (6) in \url{http://theory.stanford.edu/~tim/f13/l/l3.pdf}.)
Prove that when $S^*$ is the set of winning bidders under the allocation rule \eqref{eq.1} and $i \in S^*$, $i$'s payment equals the difference between $(1)$ the maximum social welfare of a feasible set that excludes $i$; and $(2)$ the social welfare $\sum_{j \in S^* \setminus \{i\}} v_j$ of the bidders other than $i$ in the chosen outcome $S^*$.
[The above shows that each winning bidder pays her ``externality'' -- the welfare loss she imposes on others.]
\item (10 points)
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.
\\
\\
\item[$(a)$] (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[$(b)$] (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}).\]
(Derive these by adopting $i$'s perspective and ``targeting'' the slot $j$.)
\item[$(c)$] (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''.)
(Hint: you might want to first prove that the bidders must be sorted in non-increasing order of valuations.)
\item[$(d)$] (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.
(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{itemize}
\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 (6 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)$](2 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)$](2 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)$] (2 points) If the above allocation rule is monotone then design a polynomial-time procedure/algorithm to compute payment of the winners. Otherwise do nothing.
\item[{\bf Extra.}] Prove that if all bidders report truthfully and have sets $T_i$ of cardinality at most $d$, then the outcome of the allocation rule in $(b)$ has social welfare at least $\frac{1}{d}$ times that of maximum possible.
\end{itemize}
\item ({\bf Extra. Just for fun}) The revelation principle (Theorem 3.1 of \url{http://theory.stanford.edu/~tim/f13/l/l4.pdf}) states that (direct-revelation) DSIC mechanisms can simulate all other mechanisms with dominant-strategy equilibria. Critique the revelation-principle from a practical perspective. Name a specific situation where you might prefer a non-direct-revelation mechanism with a dominant-strategy equilibrium to the corresponding DSIC mechanism, and explain your reasoning.
\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 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∈S} v_{ij}$. Prove that the VCG mechanism can
be implemented in polynomial time for unit-demand bidders.
\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}