1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
\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 deeply 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}$.
\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 unit-demand case for
which TODO:cite provides a 2 approximation to $R\left( \left(\frac{1}{m},\ldots,\frac{1}{m}\right)\right)$.
\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 a menu of goods with prices $p_1,...,p_m$.
However, there is an ex-ante constraint of being allocated a given good $i$,
given by $\hat{x}_i$. For each good, if the buyer is allocated the good, which
he is with probability $x_i \leq \hat{x}_i$, then he pays $p_i$; otherwise, he
pays nothing. This is essentially the concept of a two-part tariff, as
discussed in \cite{armstrong}.
\bibliographystyle{abbrv}
\bibliography{main}
\end{document}
|
