From c2b6a0052aab570ca0e2659f4882fdfc7bd4b8e5 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 15 Dec 2014 17:48:38 -0500
Subject: Problem statement

---
 project2/main.tex | 101 ++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 87 insertions(+), 14 deletions(-)

(limited to 'project2/main.tex')

diff --git a/project2/main.tex b/project2/main.tex
index f83f79b..cfc3831 100644
--- a/project2/main.tex
+++ b/project2/main.tex
@@ -1,9 +1,10 @@
 \documentclass[10pt]{article}
-\usepackage{fullpage}
 \usepackage{amsmath,amsfonts,amsthm}
 \usepackage[english]{babel}
-\usepackage[capitalize, noabbrev]{cleveref}
 \usepackage{paralist} 
+\usepackage[utf8x]{inputenc}
+\usepackage[pagebackref=true,breaklinks=true,colorlinks=true]{hyperref}
+\usepackage[capitalize, noabbrev]{cleveref}
 
 % these are compressed lists to help fit into a 1 page limit
 \newenvironment{enumerate*}%
@@ -41,28 +42,100 @@
 
 \maketitle
 
-\section{Problem}
-
-We are interested in a multi-item auction for agents with submodular
-preferences.
+\section{Introduction}
 
-If we denote by $m$ the number of items, we look at a specific case where the
-type $t$ of an agent is a vector $t=(t_1,\ldots,t_m)$ drawn from a distribution
-$F$ over $\mathbb{R}_+^m$ and for an allocation $x$ and price
-$p$, the utility of the agent is:
+We consider the problem of selling $m$ heterogeneous items to a single agent
+with additive utility. The type $t$ of the agent is drawn from a distribution
+$F$ over $\R_+^m$. For an allocation $x = (x_1,\ldots,x_m)$ where $x_i$,
+$i\in[m]$, denotes the probability of being allocated item $i$ and payment $p$,
+the utility of an agent with type $t=(t_1,\ldots, t_m)$ is defined by:
 \begin{displaymath}
-    u(t, x, p) = \sum_{S\subseteq 2^m} x(S)g\left(1+\sum_{j\in S} t_j\right)-p
+    u(t, x, p) = \left(\sum_{i=1}^m x_i t_i\right) - p
 \end{displaymath}
-where $g$ is a concave function from $\mathbb{R}_+$ to $\mathbb{R}_+$ with
-$g(0) = 0$.
 
+By the taxation principle, a mechanism for this setting can be described by
+a pair $x(\cdot), p(\cdot)$ where the allocation rule $x$ and the payment rule
+$p$ are indexed by the agent's type. For an agent with type $t$, $\big(x(t),
+p(t)\big)$ is her preferred menu option.
+
+The revenue-optimal mechanism for this single-agent problem can be formally
+obtained as the solution to the following optimization problem:
+\begin{equation}
+    \label{eq:opt}
+    \begin{split}
+        \max_{(x, p)} & \E_{t\sim F}\big[p(t)\big]\\
+        \text{s.t.} &\, u(t, x(t), p(t)) \geq u(t', x(t'), p(t')),\quad
+        \forall t, t'\in\R_+^m\\
+        &\, u(t, x(t), p(t)) \geq 0,\quad\forall t\in\R_+^m\\
+        &\,x_i(t)\leq 1,\quad \forall t\in\R_+^m,\,\forall i\in[m]
+\end{split}
+\end{equation}
+where the first constraint expresses incentive compatibility and the second
+constraint expresses individual rationality.
+
+Unfortunately, it has been shown in \cite{hart} that even in this simple case
+and as soon as $m\geq 2$, the optimal mechanism can have a menu size which is
+exponential in $m$. Therefore it is important to understand to which extent
+simple mechanisms can approximate the revenue-optimal mechanism.
+
+A remarkable result of \cite{babaioff} proves that a simple mechanism provides
+a constant approximation to Problem~\ref{eq:opt}. More precisely, it is shown
+that the maximum of \emph{item pricing} where each item is priced separately at
+its monopoly reserve price and \emph{bundle pricing} where the grand bundle of
+all items is priced and sold together achieves a 6-approximation to the optimal
+mechanism.
+
+We propose to extend this result by considering a more general version of
+Problem~\ref{eq:opt} where there is an additional \emph{ex-ante allocation
+constraint}. Formally, we are given a vector $\hat{x}
+= (\hat{x}_1,\ldots,\hat{x}_m)$ and we add the following constraint to
+Problem~\ref{eq:opt}:
+\begin{equation}
+    \label{eq:ea}
+    \E_{t\sim F}\big[x_i(t)] \leq \hat{x}_i,\quad\forall i\in[m]
+\end{equation}
+which simply expresses that the ex-ante allocation rule is upper-bounded by
+$\hat{x}$.
+
+Let us denote by $R(\hat{x})$ the revenue obtained by the optimal mechanism
+solution to Problem~\ref{eq:opt} with ex-ante allocation constraint
+\eqref{eq:ea}.
+
+\paragraph{Problem.} \emph{Given an ex-ante allocation constraint $\hat{x}$, is
+there a simple mechanism whose ex-ante allocation rule is upper-bounded by
+$\hat{x}$ and whose revenue is a constant approximation to $R(\hat{x})$?}
+
+\paragraph{} One reason why one might want to consider this problem is that it
+can be used as a building block for more general mechanisms. Indeed, in
+\cite{alaei}, Alaei shows that under fairly general assumptions, given an
+$\alpha$-approximate mechanism for the single-agent, ex-ante allocation
+constrained problem it is possible to construct in polynomial time a mechanism
+for the multi-agent problem which is a $\gamma\cdot\alpha$ approximation to the
+revenue-optimal mechanism where $\gamma$ is a constant which is at least
+$\frac{1}{2}$.
+
+It is interesting to consider two specific case for which we already have an
+answer to our problem:
+\begin{itemize}
+    \item when $\hat{x} = (1,\ldots,1)$, \eqref{eq:ea} does not further
+        constrain Problem~\ref{eq:opt}. In this case, as discussed above, the
+        mechanism described in \cite{babaioff} provides a 6-approximation.
+    \item when $\hat{x} = (\frac{1}{m},\ldots,\frac{1}{m})$, by summing the
+        constraint \eqref{eq:ea} for all $i\in[m]$, we see that the ex-ante
+        allocation constraint implies that in expectation, no more than
+        one-item is sold to the agent. This is exactly the unit-demand case for
+        which TODO:cite provides a 2 approximation.
+\end{itemize}
 
 \section{Related Work}
 
-In \cite{babaioff}, the authors describe a setting with a monopolist seller, offering $n$ heterogeneous goods, and a single buyer. 
+In \cite{babaioff}, the authors describe a setting with a monopolist seller,
+offering $n$ heterogeneous goods, and a single buyer. 
 \cite{hart}
 \cite{hartline}
 \cite{yao} 
+\cite{armstrong}
+\cite{alaei}
 
 \bibliographystyle{abbrv}
 \bibliography{main}
-- 
cgit v1.2.3-70-g09d2

