path: root/final/main.tex

\documentclass[10pt]{article}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage[english]{babel}
\usepackage{paralist} 
\usepackage[utf8x]{inputenc}
\usepackage[pagebackref=false,breaklinks=true,colorlinks=true,citecolor=blue]{hyperref}
\usepackage[capitalize, noabbrev]{cleveref}
\usepackage[square,sort]{natbib}


% 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}{\mathbf{E}}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{P}}
\DeclareMathOperator*{\I}{\mathcal{I}}
\DeclareMathOperator*{\TPRev}{\textsc{TPRev}}
\DeclareMathOperator*{\Rev}{\textsc{Rev}}
\DeclareMathOperator*{\BRev}{\textsc{BRev}}
\DeclareMathOperator*{\SRev}{\textsc{SRev}}

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

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

\author{Thibaut Horel \and Paul Tylkin}
\title{The Additive Single Buyer Problem\\ with Ex-Ante Allocation Constraints \\ \vskip0.1in {\sc Economics 2099 Project}}
\date{}
\begin{document}
%include all references
\nocite{*}

\maketitle

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

\begin{abstract}
In this paper, given the problem of selling $m$ heterogeneous items, with ex-ante allocation constraint $\hat{x}$, to a single buyer with additive utility, having type drawn from the distribution $F$, we focus on finding a simple mechanism obeying the allocation constraint whose revenue is a constant approximation to the revenue of the optimal mechanism with this constraint. In particular, following a suggestion by J.D. Hartline, we define a mechanism based on a two-part tariff approach (in which the price charged to the buyer consists of an entrance fee plus posted prices for the items) and then draw a connection with a technique from \citep{yao}, in which we relate this mechanism to a $p$-exclusive mechanism. This mechanism can be viewed as a generalization of the work of \citep{babaioff}, where we have introduced allocation constraints.
\end{abstract}

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

\subsection{Setup of the Problem}

The exposition in this section draws from \citep{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 $\left(x(\cdot), p(\cdot)\right)$ 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 (\citep{hartline}, Section 3.4).

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 \citep{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 \citep{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
\citep{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 the result of \citep{babaioff} 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}$.

Following \citep{hartline}, we use the notation $R(\hat{q})$ to denote the
revenue obtained by the optimal mechanism which serves with ex-ante allocation
probability equal to $\hat{q}$.  We slightly modify the notation from
\citep{alaei} by replacing his $R$ with $\Rev$ and always making the type
distribution $F$ explicit; so we will write $\Rev(\hat{x}, F)$, letting this
denote 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}. Finally, when the ex-ante allocation constraint \eqref{eq:ea} is
not present, we use $\Rev(F) \eqdef \Rev((1,\dots, 1), F)$ to denote the
revenue of the revenue optimal IR-IC mechanism. In this case, as
discussed above, the mechanism described in \citep{babaioff} provides
a 6-approximation to $\Rev((1,...,1),F)$.

The main question underlying this work can then be formulated as:

\paragraph{Question.} \emph{Given an ex-ante allocation constraint $\hat{x}$
and a type distribution $F$, is there a simple mechanism whose ex-ante
allocation rule is upper-bounded by $\hat{x}$ and whose revenue is a constant
approximation to $\Rev(\hat{x},F)$?}

\subsection{Examples and Motivations}

\paragraph{Single-item case.} 
To make things more concrete, let us first look at the single-item case, which
has already been studied extensively and is well understood. In this setting,
$\hat{x}$ is a real number and the function $\Rev(\hat{x},F)$ defined above is
obtained by maximizing the revenue curve $R(x)$ subject to the allocation
constraint $x\leq \hat{x}$, and turns out to be a very useful object to
understand the revenue maximizing multiple-agent single-item auction (see
\citep{hartline}, Chapter 3).

In particular, if the type of the agent (her value) is drawn from a regular
distribution, the revenue curve $R(x)$ is equal to the posted price revenue
curve $P(x) = xF^{-1}(1-x)$ and the optimal mechanism which serves the agent
with ex-ante allocation probability at most $\hat{x}$ has revenue $\Rev(\hat{x},F)$,
given by solving
\begin{align*}
    \begin{split}
        \max_{x} & \;xF^{-1}(1-x) \\
\text{subject to }& \; x \leq \hat{x} 
    \end{split}
\end{align*}
which is a convex optimization program since $P(x) = xF^{-1}(1-x)$ is concave
for regular distributions.

\paragraph{Multiple-item case.} The multiple-agent multiple-item setting is not
fully understood yet, but the revenue function $\Rev(\hat{x},F)$ defined above still
seems to play an important role in understanding the revenue optimal auction.
For example, it is noted in \citep{alaei} that $\Rev(\hat{x},F)$ 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, \citep{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 $\hat{v}_0$ to participate in the
mechanism, and then is offered each item separately with posted prices
$\hat{v}_1,\ldots, \hat{v}_m$.  This is essentially the concept of a two-part
tariff, as discussed in \citep{armstrong}.

Note that as the candidate mechanism is described above, it is not individually
rational because the agent gets charged $\hat{v}_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 - \hat{v}_i)^+ \geq \hat{v}_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 \hat{v}_i} (t_i-
\hat{v}_i)\geq \hat{v}_0.$$

We can now formally describe the candidate mechanism $\M$.

\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(t) = \I[t_i \geq \hat{v}_i],\; p(t) = \hat{v}_0 + \sum_i
            \hat{v}_ix_i &\text{ if} \sum_{i=1}^m (t_i - \hat{v}_i)^+ \geq
            \hat{v}_0 \\
            x_i(t) = 0\text{ for all $i$},\; p(t) = 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
\citep{yao}, even though the interpretation as a two-part tariff is
not explicit in his paper.

For a choice $\hat{v} = (\hat{v}_0,\hat{v}_1,\dots,\hat{v}_m)$ of the entrance
fee and the posted prices, let us denote by $x(t, \hat{v})$ and $p(t, \hat{v})$
the allocation rule and payment rule of the two-part tariff mechanism. We will use
$\TPRev(F)$ to denote the best expected revenue which can be obtained by the
two-part tariff mechanism for an optimal choice of $\hat{v}$:
\begin{displaymath}
    \TPRev(F) = \sup_{\hat{v}\in\R_+^{m+1}} \E_{t\sim F}[p(t, \hat{v})]
\end{displaymath}
and by $\TPRev(\hat{x}, F)$ the best revenue which can be obtained by the
two-part tariff mechanism with ex-ante allocation constraint $\hat{x}$:
\begin{displaymath}
    \begin{split}
        \TPRev(\hat{x}, F) = \sup_{\hat{v}\in\R_+^{m+1}} &\E_{t\sim F}[p(t, \hat{v})]\\
        \text{s.t.} &\, \E_{t\sim F}[x_i(t, \hat{v})]\leq \hat{x}_i,\quad \forall
        i\in[m]\\
\end{split}
\end{displaymath}
The question we introduced in Section~\ref{sec:intro} can then be formulated for
the two-part tariff mechanism: $$\text{\emph{is $\TPRev(\hat{x}, F)$ a constant
approximation to $\Rev(\hat{x}, F)$?}}$$

The following Lemma shows that at least in the unconstrained case, the
answer to the previous question is positive. In fact, the proof shows that the
two-part tariff mechanism is rich enough to simulate both bundle pricing and
separate posted pricing. Using the notation from \citep{babaioff}, let us write
$\BRev(F)$ for the revenue obtained by the optimal grand bundle pricing and 
$\SRev(F)$ for the revenue obtained by selling each item at its monopoly reserve
price. Then we have:

\begin{lemma} For any product distribution $F$,
    \begin{displaymath}
        \TPRev(F)\geq \max\{\BRev(F), \SRev(F)\}\geq 6\cdot \Rev(F).
    \end{displaymath}
\end{lemma}

\begin{proof}
    The second inequality is the main result from \citep{babaioff}; we will
    thus only prove the first inequality, which holds even without the
    assumption that $F$ is a product distribution.

    In the specific case where $\hat{v} = (0,\hat{v}_1,\dots,\hat{v}_m)$,
    \emph{i.e} $\hat{v}_0 = 0$, there is no entrance fee and the two-part
    tariff mechanism simply sells each item separately in a take-it-or-leave-it
    manner. For the optimal choice of $(\hat{v}_1,\dots,\hat{v}_m)$, the
    revenue of the mechanism reaches $\SRev(F)$. Since the supremum defining
    $\TPRev(F)$ optimizes (in particular) over all $\hat{v}$, with $\hat{v}_0
    = 0$, we have that $\TPRev(F)\geq \SRev(F)$.

    When $\hat{v}_1=\dots=\hat{v}_m = 0$, the two-part tariff mechanism then
    simply sells all the items at price $\hat{v}_0$ whenever $\sum_{i=1}^m
    t_i\geq \hat{v}_0$, \emph{i.e} is a grand bundle pricing mechanism. For the
    optimal choice of $\hat{v}_0$, the revenue reaches $\BRev(F)$. As in the
    previous paragraph, this implies that $\TPRev(F)\geq \BRev(F)$.
\end{proof}

\subsection{$\beta$-exclusivity}

As noted by \citep{yao}, the above mechanism $\M$ has the additional property
of being $\beta$-exclusive, where $\beta$-exclusivity is defined as
follows: for a vector $\beta = (\beta_1,\dots,\beta_m)$ a mechanism is said to
be $\beta$-exclusive if $x_i = 0$ whenever $\beta_i > t_i$. This is
essentially saying that there is a reserve price for each item.

Theorem 6.1 from \citep{yao} shows that for an optimal choice of
$\hat{v}_{-1}\geq \beta$ and $\hat{v}_0$, mechanism $\M$ described above is
a constant $7$-approximation to the optimal $\beta$-exclusive mechanism. We will discuss this in greater detail in Section \ref{sec:reduction}.

There is a one-way reduction from mechanisms with ex-ante constraint $\hat{x}$ to $\beta$-exclusive mechanisms captured by the following Lemma.

\begin{lemma}
    If a mechanism is $\beta$-exclusive with $\beta\geq F^{-1}(1-\hat{x})$, then
    it is satisfies the ex-ante allocation constraint given by $\hat{x}$.
\end{lemma}

\begin{proof}
Let us consider a $\beta$-exclusive mechanism with $\beta\geq
F^{-1}(1-\hat{x})$, meaning that for all $i\in[m]$: $\beta_i\geq
F^{-1}(1-\hat{x}_i)$.

For a given $i\in[m]$, we have $\Pr[t_i\geq \beta_i] = (1-F(\beta_i))\leq
\hat{x}_i$. Since the mechanism only allocates $i$, when $t_i\geq \beta_i$ by
$\beta$-exclusivity, this implies:
\begin{displaymath}
    \E[x_i(t)]\leq \Pr[t_i\geq\beta _i]\leq \hat{x}_i
\end{displaymath}
This is true for all $i\in[m]$ so the mechanism satisfies the ex-ante
allocation constraint $\hat{x}$.
\end{proof}

Let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. 
One could hope to use this reduction to show that $\TPRev(\hat{x}, F)$ is
a constant approximation to $\Rev(\hat{x}, F)$ by:
\begin{enumerate}
    \item showing that the revenue of the optimal $\beta$-exclusive
        mechanism, $\Rev_\beta(F)$, with $\beta = F^{-1}(1-\hat{x})$ is a constant approximation
        to $\Rev(\hat{x}, F)$.
    \item using that $\M$ is a constant approximation to the optimal
        $\beta$-exclusive mechanism (Theorem 6.1 in \citep{yao}).
\end{enumerate}

Unfortunately, this approach breaks at step 1. To see why, consider for
simplicity a discrete type space $T\subset \R_+^m$ and assume that the support
of $F$ is exactly $T$. Writing $T = T_1\times\dots\times T_m$ and $F
= F_1\times\dots\times F_m$, consider an ex-ante constraint $\hat{x}$ such that
for all $i\in[m]$, $0<\hat{x}_i < \min_{t_i\in T_i} f_i(t)$. Then, this forces the
associated $\beta_i$ to be such that $\beta_i > \max_{t_i\in T_i} t_i$ for all
$i\in [m]$. But a $\beta$-exclusive mechanism for such a $\beta$ will never
allocate any item and hence will have a revenue of $0$. Hence the optimal
$\beta$-exclusive mechanism for $\beta = F^{-1}(1-\hat{x})$ will have revenue
$0$.

However, there is a very simple mechanism which satisfies the ex-ante
allocation constraint $\hat{x}$: regardless of the type, allocate each item $i\in [m]$
with probability $\hat{x}_i$ at price $$t_i^{min}\eqdef\min_{t_i\in T_i} t_i.$$
This mechanism is clearly IR and IC, satisfies the constraint $\hat{x}$ and has
expected revenue $$\sum_{i\in [m]} \hat{x}_i t_i^{min}.$$ The revenue is positive
whenever there exists $i$ such that $t_i^{min}>0$.

This example shows that the approximation ratio in step 1. described above is
in fact unbounded.

\section{$n$-to-1 Bidders Reductions}
\label{sec:reduction}
The goal of this section is to compare the two ways of constraining the single
buyer problem that we discussed: namely $p$-exclusivity and ex-ante allocation
constraints and draw a parallel in how these two notions are used to construct
$n$-to-1 bidders reductions in \citep{yao} and \citep{alaei} respectively.
\subsection{\citep{alaei}'s Approach}
\subsection{\citep{yao}'s Approach}
The notion of $\beta$-exclusivity introduced by \citep{yao} was crucial in his
reduction from the $m$-item $n$-buyer setting to the $m$-item single buyer
setting. He describes a mechanism known as \emph{Best-Guess Reduction}, which
conducts $n$ single-buyer $m$-item auctions, using an IR-IC $\beta$-exclusive
mechanism, for a particular value of $\beta$ drawn from the joint bid distribution
over all buyers conditioned on the bids of all other buyers, and then combines
this with the Vickrey second-price auction, showing that this mechanism has
revenue that is a constant approximation to the optimal $m$-item, $n$-buyer
mechanism. He then defines another mechanism, \emph{Second-Price Bundling},
which is meant to heuristically approximate this combined mechanism, and shows
that its revenue is also a constant approximation to the optimal mechanism.

We will step through his results in greater detail, and also improve the approximation ratio in one of his lemmas, using the result from the published version of \citep{babaioff}. We begin with a definition and a key lemma:
\begin{definition}[$F^+_\beta$, Definition 4.1 in \citep{yao}] \end{definition}
\begin{lemma}[Lemma 6.1 in \citep{yao}]
Let $F =F_1\times\dots\times F_m$, and let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. Let $$\xi(F) = (\Pr[t_1> \beta_1],...,\Pr[t_m > \beta_m]).$$ Then, $$Rev_\beta(F) \leq \beta \xi(F) + \Rev(F_\beta^+ - \beta).$$ \end{lemma}

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