\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{xifthen}%
\usepackage{tikz}
\usepackage[hidelinks,colorlinks]{hyperref}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
		\node[shape=circle,draw,inner sep=2pt] (char) {$#1$};}}

\newcounter{question}
\setlength\parindent{0pt}

\newcommand{\question}[2]{%
	\stepcounter{question}
	\vspace{.25in} \textbf{Q\arabic{question}
		\ifthenelse{\isempty{#1}}%
		{}%
		{[#1 Points]\ }%
		#2} \vspace{.10in}
}

\newcommand{\qpart}[2]{%
	\vspace{.10in} \textbf{(#1)}
	\ifthenelse{\isempty{#2}}%
	{}%
	{[#2 Points]}%
}

\newcommand{\solution}[1] {\vspace{.25in} \textbf{Solution to Q#1} \vspace{.10in}}
\newcommand{\solpart}[1] {\vspace{.10in} \textbf{(#1)}}
\newcommand{\set}[1]{\{#1\}}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\newcommand{\E}{\mathbb{E}}
\begin{document}

\medskip
\begin{center}
{\Large CSC304 \,\, Fall'26}\\[0.2cm]
{\Large Assignment 2}\\[0.2cm]
{\large Due: November 6, 2026, by 11:59pm ET}
\end{center}

\textbf{Instructions:}
\begin{enumerate}
	\item Typed assignments are preferred (e.g., using LaTeX or Word), especially if your handwriting is possibly illegible or if you do not have access to a good quality scanner. Please submit a single PDF to MarkUs. You may work in groups of size up to $3$; only one member of each group should submit.
	\item Remember our citation policy. You are free to read online material (though, if you find the exact homework problem, do not read the solution), to discuss any problems with your peers, and to use language models. There are two rules you must follow: You must write the solution in your own words (it helps to not take any pictures or notes from your discussions), and for each question, you must cite any peer (by name), online source (by link), or language model (by chat link) you consulted. There is no penalty for citing, but failing to do so counts as plagiarism.
	\item Attempt to solve each problem, but if you have no clue how to approach a (sub)problem, remember the $20\%$ rule: You get $20\%$ of the points for a (sub)problem if you leave it blank or scratch off everything you have written for it. This rule does \emph{NOT} apply to the bonus question. The bonus question is optional, so if you solve all the other questions, you will still get $100\%$ credit for this assignment.
\end{enumerate}

\question{20}{VCG in a Continuous Space}

The government decides to help out three companies by building a single warehouse that they can all share. The warehouse is to be built at a location $x \in [0,10]$. Each company $i \in \{1,2,3\}$ is located at $y_i$, where $y_1 = 1$, $y_2 = 5$, and $y_3 = 9$. A warehouse at location $x$ provides value $100-(y_i-x)^2$ to each company $i$ simultaneously.\\[-0.2cm]

Under the VCG mechanism, decide where the warehouse should be built, and how much payment each company should be charged. Show your calculation.

\question{20}{VCG for Public Project}

Suppose a city with $n$ residents wants to decide whether to build a new bridge. The cost of the project would be $C$. There are only two possible outcomes: a) the bridge is built, and each resident $i$ derives a private value $v_i \ge 0$, or b) it is not built, and each resident derives zero value. The government wants to build the bridge only if $\sum_i v_i \ge C$, and if the bridge is built, it can charge each resident $i$ a potentially different payment $p_i$.

\medskip
Your goal is to run the VCG auction while adding the city as agent $n+1$, which derives value $-C$ if the bridge is built and zero if it is not. If both outcomes are optimal for VCG (i.e., if $\sum_i v_i = C$), assume that VCG builds the bridge.

\qpart{a}{2.5} Show that VCG would indeed choose to build the bridge only if $\sum_i v_i \ge C$.

\qpart{b}{2.5} Show that resident $i$ is charged a non-zero payment only if she is pivotal, i.e., if $\sum_j v_j \ge C > \sum_{j \neq i} v_j$.

\qpart{c}{5} What is the payment charged to a pivotal resident $i$?

\qpart{d}{10} Show that the total payment charged to the residents is at most $C$ (thus, the city can never make profit from building the bridge).

\question{20}{Sponsored Search}

Consider the following sponsored search auction with three slots $s_1,s_2,s_3$, and four bidders $A,B,C,D$. The \emph{clickthrough rate} of each slot and the \emph{value per click} for each bidder are as follows.

\medskip
Recall that in sponsored search, a bidder with value per click $v$ that is assigned a slot with clickthrough rate $c$ and charged payment \emph{per click} $p$ has expected value $v \cdot c$, expected payment $p \cdot c$, and expected utility $(v - p) \cdot c$.
\vskip 2mm
\begin{center}
	\begin{tabular}{c@{\hskip 0.4in}c@{\hskip 0.8in}c@{\hskip 0.4in}c}
		Values per Click & Bidders & Slots & Clickthrough Rates\\[0.2cm]
		$4$ & $\circled{A}$ & $\circled{s_1}$ & $0.3$ \\[0.2cm]
		$8$ & $\circled{B}$ & $\circled{s_2}$ & $0.5$ \\[0.2cm]
		$5$ & $\circled{C}$ & $\circled{s_3}$ & $0.2$ \\[0.2cm]
		$2$ & $\circled{D}$ & &
	\end{tabular}
\end{center}
\vskip 2mm

\qpart{a}{5} Under VCG, determine the allocation of slots to bidders and the payments charged to bidders \emph{per click}. What is the total expected revenue under this mechanism? Show your calculation for full credit.

\qpart{b}{5} Under GSP, determine the allocation of slots to bidders and the payments charged to bidders \emph{per click}, assuming bidders bid truthfully. What is the total expected revenue under this mechanism? Show your calculation for full credit.

\qpart{c}{10} Note that if bidders bid truthfully, GSP obtains at least as much expected revenue as VCG in this example. Show that this is true generally for all sponsored search auctions, not just the one drawn above. For this part, you can use the notation from class: there are $k$ slots and $n$ bidders, bidder $j$ has value per click $v_j$, and slot $j$ has clickthrough rate $c_j$. Without loss of generality, assume that $v_1 \ge \ldots \ge v_n$ and $c_1 \ge \ldots \ge c_k$, and, for convenience, let $v_j = 0$ for $j > n$ and $c_{k+1} = 0$.

\question{20}{Bayes-Nash Equilibria}

Consider an auction between a buyer and a seller. Seller $s$ wants to sell a good for which his own value is $v_s$. Buyer $b$ has value $v_b$ for the good. Both $v_s$ and $v_b$ are drawn independently from the uniform distribution $U[0,1]$. Each player knows his own value, but only knows the distribution of the other player's value.\\[-0.2cm]

Here's how the auction goes down. The seller and the buyer independently write down some prices (say $p_s$ and $p_b$, respectively) on different pieces of paper. Then, they compare their prices. If it turns out that $p_s \le p_b$, then the item is sold at price $p_s$, the seller gets utility $p_s-v_s$, and the buyer gets utility $v_b-p_s$. On the other hand, if $p_s > p_b$, the item remains unsold and both players get zero utility.\\[-0.2cm]

Is there a Bayes-Nash equilibrium in which the buyer honestly writes down her value (i.e. $p_b = v_b$)? If so, what is the seller's price $p_s$ in this equilibrium? Show your calculation.\\[-0.2cm]

\emph{[Hint: Assume $p_b = v_b$, and derive the optimal price $p_s$ for the seller to write. Then, check whether given this strategy of the seller, $p_b = v_b$ is indeed the optimal price for the buyer to write.]}

\question{20}{Second-Price Auction with a Twist}

In class, we proved that the second-price auction is strategyproof. Consider using the second-price auction for selling a single item, but with a twist. After all the bids are submitted, the auctioneer is supposed to sell the item to the highest bidder at price equal to the second-highest bid. The auctioneer usually does that, but with some probability $p$, makes an error and sells the item to the \emph{second-highest bidder} at price equal to the second-highest bid (i.e., the winner's own bid).\\[-0.2cm]

You show up to such an auction and see that there is only one bidder other than yourself. Your value for the item is $v \in [0,1]$. You know that this other bidder has a value $v'$ drawn from the uniform distribution $U[0,1]$ and that the other bidder, unaware of the fact that the auctioneer has this tendency to make an error, is going to truthfully bid their value $v'$. What is the optimal bid that you should submit? Your answer can depend on your own value $v$ and the probability of error $p$.

\newpage

\vspace{0.25in}
\textbf{\Large{Bonus Question}}

\question{20}{VCG for Housing Reassignment}

Consider the following housing reassignment setting. There are $n$ agents. Each agent $i$ owns a house that she values at $v_{i,i} \ge 0$, and values the house of agent $j$ at $v_{i,j} \ge 0$. When a set of agents $S$ participate in the mechanism, the set of possible outcomes consist of all bijections $\sigma : S \to S$, where $\sigma(i) = j$ denotes that agent $i$ is given the house of agent $j$; $\sigma(i) = i$ would indicate that agent $i$ retains her own house. Note that in this setting, the set of outcomes changes if one of the agents is absent because that agent's house would then no longer be available for reassignment. The value derived by a participating agent $i$ under an outcome $\sigma$ is $v_{i,\sigma(i)}$, and if she is asked to pay $p_i$, her net utility would be $v_{i,\sigma(i)} - p_i$.

\medskip
Suppose all agents participate in the VCG mechanism and $p_i$ is the payment charged to agent $i$. Note that $p_i < 0$ and $p_i > 0$ are both possible in this setting. Either prove or disprove by providing a counter-example: in every housing reassignment instance, $\sum_i p_i \le 0$ (i.e., VCG will never make overall profit).

\medskip\noindent\emph{[Hint: For a set $S$ of agents, let $W(S)$ denote the maximum total value of the agents in $S$ over all bijections $\sigma : S \to S$. Express $\sum_i p_i$ in terms of $W(\set{1,\ldots,n})$ and $W(\set{1,\ldots,n} \setminus \set{i})$ for $i \in \set{1,\ldots,n}$. Then, think of each outcome as a perfect matching between agents and houses in a bipartite graph, and consider the union of the optimal outcomes for the sets $\set{1,\ldots,n} \setminus \set{i}$ over all $i$ (choosing one optimal outcome for each $i$). What can you say about the structure of this graph?]}

\end{document}