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*{\Val}{\textsc{Val}}
\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{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem*{definition}{Definition}
\newtheorem*{goal}{Goal}
\newtheorem*{counterexample}{Counterexample}
\newtheorem*{desiredresult}{Desired Result}

\newenvironment{proofsketch}[1][Proof Sketch]{\proof[#1]\mbox{}\\*}{\endproof}

\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. We also appreciate the helpful suggestions of Aviad Rubinstein.}

\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 $\beta$-exclusive mechanism. This mechanism can be viewed as a generalization of the work of \citep{babaioff}, where we have introduced allocation constraints.

We also explore an adaptation of the Core Decomposition lemma in \citep{babaioff}, as suggested by A. Rubinstein. However, this approach to finding a simple mechanism has a counterexample, which we discuss.

While we did not solve the ex-ante pricing problem, we provide an exposition of our current understanding of the problem and what we perceive to be some of the obstacles remaining for a solution.
\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)$?}

While we have not been able to answer this question, we provide an exposition of two potential approaches: a mechanism based on a two-part tariff approach, as suggested by J. D. Hartline and as an adaptation of the Core Decomposition Lemma from \citep{babaioff}, as suggested by A. Rubinstein. The latter candidate mechanism has a counterexample, which we discuss in Section \ref{sec:counterexample}. Thus, this problem remains open, but we hope that our discussion could suggest paths towards an eventual solution.

\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}
\label{subsec: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.
However, \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} \label{tprevlemma} 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} and we will discuss it in more detail as Lemma \ref{babaiofflemma}; 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}

There is a counterexample to step 1 for discrete, non-regular distributions. 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 for discrete non-regular distributions, the approximation ratio in step 1, described above, is
in fact unbounded. However, this relies on the discreteness of the type distribution, and, we have not identified a counterexample for regular, continuous type distributions.

\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 $\beta$-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}
To reduce the $m$-item, $n$-buyer mechanism to multiple instances of an $m$-item, single buyer mechanism is accomplished within \citep{alaei} in two different ways. The first method, which he calls \emph{prerounding}, and we can abbreviate by $\text{PR}^+$, first sets an arbitrary order to serve the buyers (this could also be interpreted, as he points out, as a problem where the agents arrive sequentially). Then, for each buyer, the single-buyer mechanism is run on some subset of items still available, setting the allocation probabilities to 0 for items not in that subset. Under the assumption that there is no cross-item complementarity (meaning that the revenue from a bundle of items is at most the sum of the revenue of the single items; a counterexample would be if one of the items was a television set and another was a remote control that only worked with that television), the mechanism is shown to be DSIC and, assuming that there are at least $k$ of each of the $m$ items, to allocate a given item to a particular buyer with probability at least $1 - \frac{1}{\sqrt{k+3}}$.

The second method, which \citep{alaei} refers to as \emph{postrounding}, and we can abbreviate by $\text{PR}^-$, independently runs the single buyer mechanism for each buyer simultaneously. This will result in some overallocation, so the mechanism then takes away items that have already been allocated from some buyers (not charging buyers for the items that have been deallocated), such that the probability of an item being taken away is uniform over all buyers. The mechanism is shown to be BIC, and, similarly to $\text{PR}^+$, assuming that there are at least $k$ of each of the $m$ items, allocates and does not ultimately take away a given item to a particular buyer with probability at least $1 - \frac{1}{\sqrt{k+3}}$.
\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 also defines a mechanism known as \emph{Deterministic Best-Guess Reduction}, in which the $\beta$-exclusive mechanism from \emph{Best-Guess Reduction} is replaced with a $\beta$-bundling 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}] Let $F =F_1\times\dots\times F_m$, and let $t_i \sim F_i$. Let $$\Xi \sim \left(\text{Bernoulli}(t_1 > \beta_1),...,\text{Bernoulli}(t_m>\beta_m)\right),$$ i.e. $\xi_i$, which is defined to be the $i^{th}$ coordinate of a random variable with distribution $\Xi$, is 1 with probability $t_i>\beta_i$ and 0 otherwise. Then, let $F^+_\beta$ be defined as follows: the $i^{th}$ coordinate in $F^+_\beta$ is: 
$$ F^+_{\beta,i} = \begin{cases}  F_i | (F_i > \beta_i) &\text{if } \xi_i = 1 \\ \beta_i &\text{otherwise}\end{cases}$$
 \end{definition}

Intuitively, this defines a transformation of the distribution $F$ using $\beta$ which can then be used in the following lemma to relate the revenue of the optimal $\beta$-exclusive mechanism to the revenue of the optimal mechanism. This new distribution $F_\beta^+$, which has support $[\beta_1,\infty) \times \cdots \times [\beta_m,\infty)$, is then shifted, so that the distribution $F_\beta^+ - \beta$ has support $[0,\infty) \times \cdots \times [0,\infty) = [0,\infty)^k$.

\begin{lemma}[Lemma 6.1 in \citep{yao}]
\label{xilemma}
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 \cdot \xi(F) + \Rev(F_\beta^+ - \beta).$$ \begin{proofsketch} Let $M$ be an IR-IC $\beta$-exclusive mechanism with allocation rule $x(t)$ and payment rule $p(t)$. The goal is to prove that $$ \Rev_\beta(F) \leq \E_{t \sim F}[(p(t)] \leq \beta \cdot \xi(F) + \Rev(F_\beta^+ - \beta).$$

First, we establish that \begin{align*} \Rev_\beta(F) \leq \E_{t \sim F}[p(t)] &= \E_{t \sim F}[\beta\cdot x(t)] + \E_{t \sim F}[p(t) - \beta\cdot x(t)] \\ &= \beta \cdot \xi(F) + \E_{t \sim F}[p(t) - \beta \cdot x(t)]. \end{align*} The first inequality follows from the definition of $\beta$-exclusivity, namely that the revenue of a $\beta$-exclusive mechanism is upper-bounded by the revenue of a mechanism with the same type distribution, payment rule, allocation rule, but $\beta = (1,...,1)$.

Next, we define another mechanism, $M'$, such that $M'$ is also IR-IC, and has allocation rule $\tilde{x}(\tilde{t})$ and payment rule $\tilde{p}(\tilde{t})$, with $\tilde{t} \sim F_\beta^+$, so that we have $$\E_{t \sim F}[p(t) - \beta \cdot x(t)] \leq \E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \beta \cdot \tilde{x}(\tilde{t})].$$

Finally, we show that $$\E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \beta \cdot \tilde{x}(\tilde{t})] \leq \Rev(F_\beta^+ - \beta),$$ where the mechanism $M''$ that has revenue given by $\Rev(F_\beta^+ - \beta)$ is also shown to be IR-IC.
 \end{proofsketch}\end{lemma}

Next, \citep{yao} quotes the following result from \citep{babaioff} (with the constant improved from $5 + \frac{3\sqrt{e}}{2} \approx 7.47$ to 6 since \citep{yao}):

\begin{lemma}[Theorem 2 in \citep{babaioff}; Lemma 6.2 in \citep{yao}] \label{babaiofflemma} Let $F =F_1\times\dots\times F_m$, let $\BRev(F)$ be the revenue obtained by the optimal grand bundle mechanism, treating the grand bundle as a single item, and let $\SRev(F)$ be the revenue obtained by selling each item separately at its monopoly reserve price. Then,
$$\Rev(F) \leq 6 \cdot \max\{\SRev(F), \BRev(F)\}.$$ \begin{proofsketch} Following \citep{liyao}'s notion of a Core Decomposition, \citep{babaioff} decompose the optimal revenue into the contributions from items in the \emph{core} and \emph{tail}; although their definitions are slightly different, the tail is meant to represent items that the buyer has a very high value for and the core consists of the tail's complement. In particular, \citep{babaioff} define the core for each $F_i$ as $t^*_i > k_i$, where $t^*_i$ is the highest value that the buyer places on item $i$, and $k_i$ is chosen to appropriately separate the core and tail. This is done, as explained in \citep{babaioff}, Propostion 3, by setting $k_i = \SRev(F)$. This allows the revenue from the core and tail to be separately bounded, and leads to the desired constant approximation (with which of $\SRev(F)$ or $\BRev(F)$ is greater depending on the ratio of the welfare of the core to $\SRev(F)$). \end{proofsketch}
  \end{lemma}

As a side note, a version of this lemma for more general distributions was recently proved by \citep{rubinstein}, in which the authors show that when a single buyer has subadditive utility and type drawn from distribution $F$, then the revenue of the optimal auction on $m$ items has the following constant-factor approximation: $$\Rev(F) \leq 314 \cdot \SRev(F) + 24 \cdot \BRev(F).$$ They do this by also using the Core Decomposition lemma from \citep{liyao}. Extensions to multiple buyers are not currently known. It may be possible to also relate this to our problem with allocation constraints, and prove an analogue of Lemma \ref{tprevlemma} for a buyer with subadditive utility.

Now, let $\BRev_\beta(F)$ denote the revenue of the $\beta$-bundling mechanism introduced by \citep{yao}. We have already met this mechanism in Section \ref{subsec:mechanism}, as $\M$. The following lemma provides the relationship between the revenue of this mechanism and the revenue of the $\beta$-exclusive mechanism.

\begin{lemma}[Theorem 6.1 in \citep{yao}, with a constant of 7 instead of 8.5] Let $F =F_1\times\dots\times F_m$, let $\BRev_\beta(F)$ denote the revenue of the $\beta$-bundling mechanism, and let $\Rev_\beta(F)$ denote the revenue of the optimal $\beta$-exclusive mechanism. Then, $$\Rev_\beta(F) \leq 7\cdot \BRev_\beta(F).$$ \end{lemma}

Now, to summarize the results of these lemmas, we have shown that the revenue of the optimal $\beta$-exclusive mechanism is a constant approximation to the revenue of the $\beta$-bundling mechanism, which is related to the optimal revenue via the transformation of $F$ described in Lemma \ref{xilemma}. 

Next, we define the Best-Guess Reduction mechanism (BGR for short), and let $\Rev_{BGR}(F)$ denote its revenue. Let $B_{(-i,j)}$ denote the maximum bid by all buyers except for buyer $i$ for item $j \in [m]$. Then, the vector of these is denoted by $$B_{-i} \eqdef  \left(B_{(-i,1)},..,B_{(-i,m)}\right).$$ In this mechanism, the goal of selling $m$ heterogeneous buyers goods to $n$ bidders is achieved by running, for each $i \in [n]$, a single-bidder, $m$-unit $B_{-i}$-exclusive mechanism\footnote{Using the bids of everyone else to set the mechanism for a bidder has the flavor of peer prediction with proper scoring rules.}. Let $p_{2nd}(t)$, $t \sim F$ denote the payment rule under the Vickrey second-price mechanism, and let $$\Rev_{2nd}(F) \eqdef \E_{t \sim F} p_{2nd}(t).$$ Then, the following mechanism, which we call $\text{BGR}^+$ (\citep{yao} calls it \emph{BG}) is defined as follows:

$$\text{BGR}^+ \eqdef \begin{cases} \text {if } \Rev_{BGR}(F) \geq \Rev_{2nd}(F) \text{ use BGR} \\ \text{if } \Rev_{BGR}(F) < \Rev_{2nd}(F) \text{ use Vickrey 2nd price mechanism} \end{cases}$$

The revenue of this mechanism, $\Rev_{\text{BGR}^+}$ is related to the revenue of the revenue of the optimal mechanism via the following lemma:

\begin{lemma}[\citep{yao}, combination of Theorem 2 and Theorem 5.2, with improved constant based on \citep{babaioff}]  
\ \\
Let $F =F_1\times\dots\times F_m$. Then, $$\Rev(F) \leq 8\cdot \Rev_{\text{BGR}^+}(F)$$\end{lemma}

The deterministic version of the BGR mechanism, which we call DBGR, can be defined by using the $B_{-i}$-bundling mechanism instead of the $B_{-i}$-exclusive mechanism, as in BGR (\citep{yao}, Section 3). Then, define the following mechanism, analogously to $\text{BGR}^+$:

$$\text{DBGR}^+ \eqdef \begin{cases} \text {if } \Rev_{DBGR}(F) \geq \Rev_{2nd}(F) \text{ use DBGR} \\ \text{if } \Rev_{DBGR}(F) < \Rev_{2nd}(F) \text{ use Vickrey 2nd price mechanism} \end{cases}$$

If we denote the revenue from this mechanism by $\Rev_{\text{DBGR}^+}(F)$, then it is also a constant approximation of the optimal revenue:

\begin{lemma}[\citep{yao}, combination of Theorem 3 and Corollary to Theorem 2] \ \\ Let $F =F_1\times\dots\times F_m$. Then, $$\Rev(F) \leq 69 \cdot \Rev_{\text{DBGR}^+}(F)$$ \end{lemma}

While this mechanism's revenue does indeed provide a constant approximation to the revenue of the optimal mechanism (and thereby establishes the desired $n$-to-1 buyer reduction, it is not very simple to implement: namely, it uses $n$ different $\beta$-bundling mechanisms and $n$ second-price Vickrey auctions, and each buyer is charged a (potentially different) $\hat{v}_0$, depending on his type. To avoid this, \citep{yao} proposes a mechanism called \emph{Second-Price Bundling} (SPB) which offers all of the items for which buyer $i$ had the maximum value (breaking ties uniformly at random) to him as a single bundle at the price of $w+\sum p_{2nd}(t)$, where $w$ is a common price (\lq\lq entry fee\rq\rq) posted to all buyers. As observed in \citep{yao}, Section 9.2, setting $w$ to 0 makes the SPB mechanism equivalent to selling each item separately at the Vickrey 2nd price auction price. By proving an upper and lower bound on $\Rev_{\text{SPB}}(F)$, the revenue of the SPB mechanism relative to $\Rev(F)$, he then shows that $$\Rev_{\text{SPB}}(F) = \Theta(\Rev(F)),$$ which indicates that the SPB mechanism is a suitable substitute for the complexity of the $\text{DBGR}^+$ mechanism, and hence that the $n$-to-1 bidder reduction has been successfully accomplished.

\subsection{Connections} Interestingly, while the approaches of \citep{alaei} and \citep{yao} use quite different methodology, the overall idea of running separate allocation-constrained single-buyer mechanisms to approximate the revenue of an $n$-buyer $m$-item mechanism suggests that there is something very natural (and important) in the use and general understanding of allocation constraints for $m$-item single buyer mechanisms.

\section{Conclusion}

We have discussed 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$. Following a suggestion by J.D. Hartline, we have proposed a mechanism $\M$ 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 drew a connection with a technique from \citep{yao}, in which we relate this mechanism to a $\beta$-exclusive mechanism. We also surveyed the $n$-to-1 buyer reduction techniques within \citep{alaei} and \citep{yao}, unifying the exposition and terminology. 

Our proposed mechanism $\M$ can be viewed as a generalization of the work of \citep{babaioff}, but with the addition of allocation constraints. We showed, via a counterexample, that for a discrete, non-regular distribution the approximation ratio of the revenue for the optimal $\beta$-exclusive mechanisms to the optimal revenue of the two-party tariff mechanism $\M$ is unbounded. Assuming regularity of the distribution, this may yet yield an approach to finding the desired simple mechanism. Whether the optimal revenue of the two-party tariff mechanism is a constant approximation to the revenue of the optimal mechanism with allocation constraints remains an open and interesting path for future research.

\appendix

\section{Addendum: An Alternative Mechanism}

We also tried instead to adapt the approach of
\cite{babaioff} to the ex-ante constrained problem: that is, showing that the
maximum between (ex-ante constrained) grand bundling and separate posted
pricing is a constant approximation to the optimal mechanism. Note that this
would imply, similarly to Lemma~\ref{tprevlemma}, that our candidate two-part
tariff mechanism is also a constant approximation to the optimal mechanism.

The ``core decomposition'' Lemma of \cite{babaioff}, which is a key ingredient
in the proof of their main result, can be adapted to the case of ex-ante
constraints, as we now show.

\begin{lemma}[Marginal mechanism]\label{lemma:marginal}
    Let $(D, D')$ be a joint distribution of types over two disjoint set of
    items $S$ and $T$. Then:
    \begin{displaymath}
        \Rev\big(\hat{x}, (D, D')\big) \leq \Val(D) + \E_{t_S\sim
        D}\left[\Rev\left(\frac{\hat{x}_T}{\Pr_{D}[t_S]}, D'|t_S\right)\right]
    \end{displaymath}
    where $\Val(D) \eqdef \sum_{i\in S} \E_{t\sim D}[t_i]$
\end{lemma}

\begin{proof}
    This is an adaptation of Lemma 21 from \cite{hart-nisan}. The
    main difference is that, starting from an optimal mechanism for $(D, D')$
    satisfying the ex-ante constraint $\hat{x}$, fixing the value $t_S$ of the
    items in $S$, the induced mechanism on $T$ for the distribution $(D'|t_S)$
    allocates with probability at most $\frac{\hat{x}}{\Pr_{D}[t_S]}$.
\end{proof}

\begin{corollary}\label{cor}
    For $D$ and $D'$, two distributions of types over disjoint set of items $S$
    and $T$. Then:
    \begin{displaymath}
        \Rev(\hat{x}, D\times D') \leq \Val(D) + \Rev(\hat{x}_T, D')
    \end{displaymath}
\end{corollary}

\begin{proof}
    This follows from Lemma~\ref{lemma:marginal} by observing that $D'|t_S
    = D'$ since we have a product distribution. We also have:
    \begin{displaymath}
        \E_{t_S\sim D}
        \left[\Rev\left(\frac{\hat{x}_T}{\Pr_{D}[t_S]}, D'\right)\right]
        \leq \Rev(\hat{x}_T, D')
    \end{displaymath}
    Indeed, the value of the left-hand side can be obtained by randomizing over
    the mechanisms of value $\Rev\left(\frac{\hat{x}_T}{\Pr_{D}[t_S]},
    D'\right)$ with probability $\Pr_D[t_S]$ for all values of $t_S$. Note that
    the probability of allocation resulting from this randomization is then
    bounded above by $\E_{t_S\sim D}\left[\frac{\hat{x}_T}{\Pr_D[t_S]}\right]
    = \hat{x}_T$.
\end{proof}

Corollary~\ref{cor}, combined with Lemma~5 from \cite{babaioff} (which can be
extended, having made the appropriate changes, to the constrained case) as in the proof
Lemma~6 from \cite{babaioff} yields the following version of the core
decomposition lemma:

\begin{lemma}
        $\Rev(\hat{x}, D)\leq \Val(D^C_\emptyset) + \sum_A p_A\Rev(\hat{x}_A,
        D^T_A)$.
\end{lemma}

\begin{proof}
    Similarly to the proof of Lemma 6 in \cite{babaioff}, we get:
    \begin{displaymath}
        \Rev(\hat{x}, D) \leq \sum_A p_A \Rev(\hat{x}_A, D_A)
    \end{displaymath}
    Using Corollary~\ref{cor}, we get that $\Rev(\hat{x}_A, D_A)
    \leq \Val(D_A^C) + \Rev(\hat{x}_A, D_A^T)$. Hence:
    \begin{align*}
        \Rev(\hat{x}, D) &\leq \sum_A p_A\big(\Val(D_A^C) + \Rev(\hat{x}_A,
        D_A^T) \big)\\
        &= \sum_A p_A\Val(D_A^C) + \sum_A p_A \Rev(\hat{x}_A,
        D_A)\\
        &\leq \sum_A p_A\Val(D_{\emptyset}^C) + \sum_A p_A \Rev(\hat{x}_A,
        D_A)\\
        &= \Val(D_{\emptyset}^C) + \sum_A p_A \Rev(\hat{x}_A,
        D_A)
    \end{align*}
    Where the second inequality used that $\Val(D_A^C)\leq
    \Val(D_{\emptyset}^C)$ and where the last equality used $\sum_A p_A = 1$.
\end{proof}


However, if we keep pushing in this direction, it seems that the approach fails
when trying to obtain the following:
\begin{desiredresult}
    $\Rev(\hat{x}, D) \leq m\SRev(\hat{x}, D)$.
\end{desiredresult}

This result would be required if we wanted to apply the same proof technique as
\cite{babaioff} to the proof of the approximation ratio of our mechanism.
Unfortunately, the proof of this lemma does not transpose to the ex-ante
constrained case: the main idea in a putative proof would be to use induction and
Lemma~\ref{lemma:marginal} to ``split'' the set of items and reduce to the
induction hypothesis.
\label{sec:counterexample}
However, A. Rubinstein identifies the following counterexample to this
potential approach:
\begin{counterexample}[\citep{rubinstein2}, Example 4 adapted]
    Consider an $m$-item auction with a single bidder. The values
    $v_i$ of the items are drawn i.i.d. from the following distribution: with
    probability $1-\frac{1}{m^{3/4}}$, $v_i = 0$; otherwise, $v_i$ is drawn
    from an equal revenue distribution with support $\{1,\ldots,m^{1/10}\}$,
    i.e. $\Pr[v_i \geq k] = \frac{1}{km^{3/4}}$. We suppose that the ex-ante allocation constraint is uniform (the same for all items)
    and equal to $\frac{1}{m^{3/4}}$.
\end{counterexample}

\begin{proof}
First, note that the expected value for each item is $\frac{C\log m}{m^{3/4}}$,
for some constant $C$ (by summation of the CDF of the distribution). We now
introduce a ``good'' mechanism, which can guarantee almost the entire social welfare, and then show that neither the separate posted
price mechanism nor the grand bundle mechanism are a constant approximation to
it (and therefore that the maximum of their revenues is not a constant approximation to it either).

\paragraph{Good Mechanism} Approach the buyer and offer for her to select her
most-preferred $m^{1/4}$ items at price $(1-\epsilon)\frac{Cm\log m}{m^{3/4}}$. Since
each item has nonzero value with probability $\frac{1}{m^{3/4}}$, if there are
many items, the number of items with nonzero values will concentrate and be
(roughly) equal to $m\cdot\frac{1}{m^{3/4}} = m^{1/4}$. So the $m^{1/4}$
favorite items of the buyer will coincide with the $m^{1/4}$ items with
nonzero value, and their combined value will also concentrate close to their
expected value of $\frac{Cm\log m}{m^{3/4}}$. Hence, this mechanism has revenue
$(1-\epsilon)\frac{Cm\log m}{m^{3/4}}$. Also note that this mechanism satisfies
the ex-ante allocation constraints since an item will be sold if and only if it has nonzero
value, which happens with probability $\frac{1}{m^{3/4}}$.

\paragraph{Computing the Separate Posted Price Revenue, $\SRev$} The revenue for each item is the same no matter what the
posted price is and is equal to $\frac{1}{m^{3/4}}$. Hence the overall revenue
is $\frac{m}{m^{3/4}}$ which is only a $O(\frac{1}{\log m})$ fraction of the revenue of the
``good'' mechanism. 

\paragraph{Computing the Grand Bundle Revenue, $\BRev$} Since the ex-ante constraint is the same for all of the items,
the grand bundle can be allocated with probability at most $\frac{1}{m^{3/4}}$
(otherwise, this would violate the ex-ante constraint for one of the items).
When it is allocated, the revenue is upper-bounded by the expected value of all
the items, i.e. $\frac{Cm\log m}{m^{3/4}}$. So the revenue of the grand bundle
mechanism is at most $\frac{1}{m^{3/4}}$ times the one of the ``good''
mechanism.
\end{proof}


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