\documentclass[10pt]{article}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage[english]{babel}
\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*}%
  {\vspace{-2ex} \begin{enumerate} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{enumerate}}
 
\newenvironment{itemize*}%
  {\vspace{-2ex} \begin{itemize} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{itemize}}
 
\newenvironment{description*}%
  {\vspace{-2ex} \begin{description} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{description}}

\newcommand\blfootnote[1]{%
  \begingroup
  \renewcommand\thefootnote{}\footnote{#1}%
  \addtocounter{footnote}{-1}%
  \endgroup
}

\DeclareMathOperator*{\E}{\mathbb{E}}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbb{P}}

\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
\newcommand{\R}{\mathbb{R}}
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
\newcommand{\llbracket}{[\![}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem*{goal}{Goal}

\author{Thibaut Horel \and Paul Tylkin}
\title{Economics 2099 Project}
\begin{document}

\maketitle



\section{Introduction to the Problem}

\blfootnote{We are grateful to Jason Hartline who provided the original idea
for this project.}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) = \left(\sum_{i=1}^m x_i t_i\right) - p
\end{displaymath}

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 expresses the assumption that the ex-ante allocation rule is upper-bounded by
$\hat{x}$.

We use the notation from \cite{alaei} where $R(\hat{x})$ denotes the revenue
obtained by the optimal mechanism solution to Problem~\ref{eq:opt} with ex-ante
allocation constraint $\hat{x}$ given by \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})$?}

\section{Importance of the Problem and Possible Approach}
\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 cases 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}, i.e. the constraint is trivially satisfied. 
        In this case, as discussed above, the
        mechanism described in \cite{babaioff} provides a 6-approximation to $R((1,...,1))$.
    \item when $\hat{x} = \left(\frac{1}{m},\ldots,\frac{1}{m}\right)$, 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 ex-ante relaxation
        of the unit-demand case for which a 2-approximation to $R\left(
        \left(\frac{1}{m},\ldots,\frac{1}{m}\right)\right)$ is already known.
\end{itemize}

In the general case, a candidate simple mechanism suggested by Jason Hartline
is the following: the buyer is charged a price $p_0$ to participate in the
mechanism, and then is offered each item separately with a posted prices
$p_1,\ldots, p_m$. This is essentially the concept of a two-part tariff, as
discussed in \cite{armstrong}. Our problem is then to understand how to set
$p_0$ and the posted prices $p_1,\ldots, p_m$ such that in expectation over the
agent's type, item $i$ is sold with probability $x_i\leq \hat{x}_i$.

\bibliographystyle{abbrv}
\bibliography{main}
\end{document}
