Final draft

2 files changed, 248 insertions, 0 deletions

diff --git a/final/main.bib b/final/main.bib
new file mode 100644
index 0000000..027bd7c
--- /dev/null
+++ b/final/main.bib
@@ -0,0 +1,80 @@
+@article{babaioff,
+  author    = {Moshe Babaioff and
+               Nicole Immorlica and
+               Brendan Lucier and
+               S. Matthew Weinberg},
+  title     = {A Simple and Approximately Optimal Mechanism for an Additive Buyer},
+  journal   = {FOCS},
+  year      = {2014},
+}
+
+@article{yao,
+  author    = {Andrew Chi{-}Chih Yao},
+  title     = {An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications},
+  journal   = {CoRR},
+  volume    = {abs/1406.3278},
+  year      = {2014},
+  url       = {http://arxiv.org/abs/1406.3278},
+  timestamp = {Tue, 01 Jul 2014 11:58:08 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/corr/Yao14},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@inproceedings{hart,
+  author    = {Sergiu Hart and
+               Noam Nisan},
+  title     = {The menu-size complexity of auctions},
+  booktitle = {{ACM} Conference on Electronic Commerce, {EC} '13, Philadelphia, PA,
+               USA, June 16-20, 2013},
+  pages     = {565--566},
+  year      = {2013},
+  crossref  = {DBLP:conf/sigecom/2013},
+  url       = {http://doi.acm.org/10.1145/2482540.2482544},
+  doi       = {10.1145/2482540.2482544},
+  timestamp = {Mon, 24 Feb 2014 16:09:47 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/sigecom/HartN13},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@book{hartline,
+   author = {Jason Hartline},
+   title = {Mechanism Design and Approximation},
+   year = {2014},
+   publisher={Available at http://jasonhartline.com/MDnA/}
+}
+
+
+@article{hartlinebayes,
+  author    = {Jason D. Hartline},
+  title     = {Bayesian Mechanism Design},
+  journal   = {Foundations and Trends in Theoretical Computer Science},
+  volume    = {8},
+  number    = {3},
+  pages     = {143--263},
+  year      = {2013},
+  url       = {http://dx.doi.org/10.1561/0400000045},
+  doi       = {10.1561/0400000045},
+  timestamp = {Wed, 23 Oct 2013 15:47:35 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/fttcs/Hartline13},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{armstrong,
+  title={Price discrimination by a many-product firm},
+  author={Armstrong, Mark},
+  journal={The Review of Economic Studies},
+  volume={66},
+  number={1},
+  pages={151--168},
+  year={1999},
+  publisher={Oxford University Press}
+}
+
+@inproceedings{alaei,
+  title={Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers},
+  author={Alaei, S},
+  booktitle={Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on},
+  pages={512--521},
+  year={2011},
+  organization={IEEE}
+}
diff --git a/final/main.tex b/final/main.tex
new file mode 100644
index 0000000..32d514d
--- /dev/null
+++ b/final/main.tex
@@ -0,0 +1,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}