diff options
| -rw-r--r-- | final/main.tex | 33 |
1 files changed, 17 insertions, 16 deletions
diff --git a/final/main.tex b/final/main.tex index ac8f87d..198b8ab 100644 --- a/final/main.tex +++ b/final/main.tex @@ -44,6 +44,7 @@ \author{Thibaut Horel \and Paul Tylkin} \title{Economics 2099 Project} +\date{Fall 2014} \begin{document} \maketitle @@ -54,12 +55,12 @@ for this project.} \section{Introduction} \label{sec:intro} -\subsection{Problem} +\subsection{Setup of the Problem} 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]$, +$\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} @@ -86,17 +87,17 @@ obtained as the solution to the following optimization problem: 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 +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 +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 +\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 @@ -136,7 +137,7 @@ single-item auction (see \cite{hartline}, Chapter 3). In particular, if the type of the agent (her value) is drawn from a regular distribution, the posted price revenue curve is concave and equal to the -revenue curve. In this case, the optimal mechanism which serves with ex-ante +revenue curve. In this case, the optimal mechanism which serves the agent with ex-ante allocation probability $\hat{x}$ is a simple posted-price mechanism with price $p_{\hat{x}} = F^{-1}(1-\hat{x})$. @@ -144,20 +145,20 @@ $p_{\hat{x}} = F^{-1}(1-\hat{x})$. fully understood yet, but the revenue function $R(\hat{x})$ defined above still seems to play an important role in understanding the revenue optimal auction. For example, it is noted in \cite{alaei} that $R(\hat{x})$ is a concave -function of $\hat{x}$. This allows to define a convex optimization program -(where the objective function is the sum of the revenue curve for all agents) +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. +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 +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} +\section{A Two-Part Tariff Mechanism} \subsection{Definition of the Mechanism} @@ -180,8 +181,8 @@ restore individual rationality, we need to have the agent pay only when: \begin{displaymath} \sum_{i=1}^m (t_i - p_i)^+ \geq p_0 \end{displaymath} -where we used the notation $(x)^+\eqdef\max\{x, 0\}$, so that the sum in the -above inequality could also be written $\sum_{i: t_i\geq p_i} (t_i- p_i)$. +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 p_i} (t_i- p_i)\geq p_0.$$ We can now formally describe the candidate mechanism. |