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
164
165
166
167
168
|
\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}
\blfootnote{We are grateful to Jason Hartline who provided the original idea
for this project.}
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$. 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 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 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})$?}
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}
|
