\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}}
\DeclareMathOperator*{\I}{\mathcal{I}}

\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{Approximate Mechanisms\\ for Ex-Ante Allocation Constraints \\ \vskip0.1in {\sc Economics 2099 Project}}
\date{Fall 2014}
\begin{document}

\maketitle

\blfootnote{We are grateful to Jason Hartline who provided the original idea
for this project.}

\section{Introduction}
\label{sec:intro}

\subsection{Setup of the Problem}

The exposition in this section draws from \cite{hartlinebayes}. 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$. We use the notation $[m]$ for $\{1,...,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. As noted in \cite{hartlinebayes},
this formulation can easily be extended to support additional constraints which
arise in natural scenarios: budget constraints or matroid constraints, for
example.

If the distribution $F$ is correlated, a result from \cite{hart} shows that the
gap between the revenue of auctions with finite menu size and
a revenue-maximizing auction can be arbitrarily large. When $F$ is a product
distribution, however, there is a possibility of obtaining a simple auction with a constant
approximation ratio to the optimal revenue. In fact, a result from
\cite{babaioff} shows 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 as a single item,
achieves a 6-approximation to the optimal revenue.

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 that the ex-ante allocation probability 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}. The main question
underlying this work can then be formulated as:

\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})$?}

\subsection{Examples and Motivations}

\paragraph{}Note that when $\hat{x} = (1,\ldots,1)$, the ex-ante allocation constraint \eqref{eq:ea} does not further
constrain the optimization problem given by Equation \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))$.

\paragraph{Single-item case.} 
To make things more concrete, let us first look at the single-item case which
is well understood. In this setting, $\hat{x}$ is a real number and the
function $R(\hat{x})$ defined above is simply the revenue curve and turns out
to be a very useful object to understand the revenue maximizing multiple-agent
single-item auction (see \cite{hartline}, Chapter 3).

In particular, if the type of the agent (her value) is drawn from a regular
distribution, the posted price revenue curve is concave and equal to the
revenue curve. In this case, the optimal mechanism which serves the agent with ex-ante
allocation probability $\hat{x}$ is a simple posted-price mechanism with price
$p_{\hat{x}} = F^{-1}(1-\hat{x})$.

\paragraph{Multiple-item case.} The multiple-agent multiple-item setting is not
fully understood yet, but the revenue function $R(\hat{x})$ defined above still
seems to play an important role in understanding the revenue optimal auction.
For example, it is noted in \cite{alaei} that $R(\hat{x})$ is a concave
function of $\hat{x}$. This allows us to define a convex optimization program
(where the objective function is the sum of the revenue curves for all agents)
whose optimal value is an upper bound on the expected value of the
multiple-agent revenue-optimal mechanism.

Furthermore, in the same paper, 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}$.


\section{A Two-Part Tariff Mechanism}

\subsection{Definition of the Mechanism}

Given the simplicity of posted-price mechanisms and the fact that they are
optimal in the single-agent single-item setting (for a regular distribution
$F$), it would be desirable to obtain a mechanism as close as possible to posted-price.
Unfortunately, Hart and Nisan \cite{hart-nisan} showed that even in the
unconstrained, regular case, no posted-price mechanism for the single-agent
problem has an approximation ratio better than $\Omega(\log n)$.

Instead, we consider the following candidate mechanism suggested by Jason
Hartline: the buyer is charged a price $p_0$ to participate in the mechanism,
and then is offered each item separately with posted prices $p_1,\ldots, p_m$.
This is essentially the concept of a two-part tariff, as discussed in
\cite{armstrong}.

Note that as written above, the candidate mechanism is not individually
rational because the agent gets charged $p_0$ regardless of her type. To
restore individual rationality, we need to have the agent pay only when
\begin{displaymath}
    \sum_{i=1}^m (t_i - p_i)^+ \geq p_0
\end{displaymath}
where we used the notation $(x)^+\eqdef\max(x, 0)$, so that the
above inequality could also be written as $$\sum_{i: t_i\geq p_i} (t_i- p_i)\geq p_0.$$

We can now formally describe the candidate mechanism.

\begin{center}
\fbox{
\begin{minipage}{0.9\textwidth}
    \vspace{1em}
\begin{center}
    \textbf{Candidate mechanism for the single-agent problem}
\end{center}
    \begin{displaymath}
        \begin{cases}
            x_i = \I[t_i \geq p_i],\; p = p_0 + \sum_i p_ix_i &\text{ if} \sum_{i=1}^m (t_i - p_i)^+ \geq p_0 \\
            x_i = 0\text{ for all $i$},\; p = 0&\text{ otherwise }
        \end{cases}
    \end{displaymath}
    \vspace{1em}
\end{minipage}
}
\end{center}
where we use the notation $\I[\text{expression}]$ to denote the indicator
variable for the expression, which takes on value 1 when the expression is true and 0 otherwise.

We note that this mechanism is exactly the $\beta$-bundle mechanism from
\cite{yao}, even though the interpretation in terms of entrance fee plus posted
prices is not explicit in this paper.

\subsection{$p$-exclusivity}

As noted by Yao, the above mechanism has the additional property of being
$p$-exclusive in the following sense: for a vector $p = (p_1,\dots,p_m)$
a mechanism is said to be $p$-exclusive if $x_i = 0$ whenever $p_i > t_i$. This
is essentially saying that there is a reserve price for each item.

The notion of $p$-exclusivity introduced by Yao was crucial in his reduction
from the multiple-buyer setting to the single buyer setting. $p$-exclusivity
can easily be enforced in the problem we formulated in Section~\ref{sec:intro},
by adding the following non-linear constraints:
\begin{displaymath}
    x_i(t_i - p_i)\geq 0,\quad \forall i\in[m] 
\end{displaymath}

$p$-exclusivity relates to ex-ante allocation constraints through the following
Lemma.

\begin{lemma}
    If a mechanism is $p$-exclusive for some vector $p=(p_1,\dots, p_m)$, then
    it satisfies the ex-ante allocation constraint defined by $\hat{x}
    = \big(F^{-1}(1-p_1), \dots, F^{-1}(1-p_m)\big)$.
\end{lemma}


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