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
152
153
154
155
156
157
158
159
160
161
162
163
|
\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.
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 hope to obtain simple
auctions with constant approximation ratios 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 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})$?}
Note that 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))$.
\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}$.
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 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$.
\section{Roadmap}
Here are the steps we plan to execute before the completion of our project:
\begin{enumerate}
\item work out simple, illustrative examples for which we will be able to do exact
computation on the proposed two-part mechanism. The goal is to obtain
a ``proof-of-concept'' that this mechanism can yield, at least in some
cases, a constant approximation to the optimal revenue.
\item prove (or disprove) that this two-part mechanism achieves
a constant-approximation for any product distribution $F$.
\item by then, we should have a better understanding of two-part tariff
ideas. Use this understanding to re-interpret the results from
\cite{yao} as two-part tariff mechanisms. Indeed, it seems that many
mechanisms in this paper have a ``two-part'' structure (entrance fee
plus separate prices) and could benefit from this re-interpretation.
\end{enumerate}
In terms of timeline, we estimate that these steps will take us until beginning
of January 2015.
\bibliographystyle{abbrv}
\bibliography{main}
\end{document}
|
