diff options
| -rw-r--r-- | project2/main.tex | 62 |
1 files changed, 34 insertions, 28 deletions
diff --git a/project2/main.tex b/project2/main.tex index c3bb706..1e02d78 100644 --- a/project2/main.tex +++ b/project2/main.tex @@ -48,8 +48,6 @@ \maketitle - - \section{Introduction to the Problem} \blfootnote{We are grateful to Jason Hartline who provided the original idea @@ -83,17 +81,16 @@ obtained as the solution to the following optimization problem: 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. +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. -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. +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 @@ -115,7 +112,13 @@ allocation constraint $\hat{x}$ given by \eqref{eq:ea}. 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 @@ -125,20 +128,6 @@ 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 ex-ante relaxation - of the unit-demand case for which a 2-approximation to $R\left( - \left(\frac{1}{m},\ldots,\frac{1}{m}\right)\right)$ is already known. -\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 @@ -148,9 +137,26 @@ 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{Two-Part Tariffs and Optimal Pricing} +\section{Roadmap} + +Here are the steps we plan to execute before the completion of our project. + +\begin{enumerate} + \item work out simple 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} -\section{The Core Decomposition Lemma} +In terms of timeline, we estimate that these steps will take us until beginning +of January 2015. \bibliographystyle{abbrv} \bibliography{main} |