diff options
Diffstat (limited to 'final/main.tex')
| -rw-r--r-- | final/main.tex | 143 |
1 files changed, 107 insertions, 36 deletions
diff --git a/final/main.tex b/final/main.tex index 32d514d..ac8f87d 100644 --- a/final/main.tex +++ b/final/main.tex @@ -48,11 +48,14 @@ \maketitle -\section{Introduction} - \blfootnote{We are grateful to Jason Hartline who provided the original idea for this project.} +\section{Introduction} +\label{sec:intro} + +\subsection{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 @@ -117,51 +120,119 @@ underlying this work can then be formulated as: 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 +\subsection{Examples and Motivations} + +\paragraph{}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{Single-item case.} +To make things more concrete, let us first look at the single-item case which +is well understood. In this setting, $\hat{x}$ is a real number and the +function $R(\hat{x})$ defined above is simply the revenue curve and turns out +to be a very useful object to understand the revenue maximizing multiple-agent +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 +allocation probability $\hat{x}$ is a simple posted-price mechanism with price +$p_{\hat{x}} = F^{-1}(1-\hat{x})$. + +\paragraph{Multiple-item case.} The multiple-agent multiple-item setting is not +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) +whose optimal value is an upper bound on the expected value of the +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 +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} -\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}$. +\subsection{Definition of the Mechanism} +Given the simplicity of posted-price mechanisms and the fact that they are +optimal in the single-agent single-item setting (for a regular distribution +$F$), we would like a mechanism as close as possible to posted-price. +Unfortunately, Hart and Nisan \cite{hart-nisan} showed that even in the +unconstrained, regular case, no posted-price mechanism for the single-agent +problem has an approximation ratio better than $\Omega(\log n)$. -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$. +Instead, we consider the following candidate mechanism suggested by Jason +Hartline: 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}. -\section{Roadmap} +Note that as written above, the candidate mechanism is not individually +rational because the agent gets charged $p_0$ regardless of her type. To +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)$. + +We can now formally describe the candidate mechanism. + +\begin{center} +\fbox{ +\begin{minipage}{0.9\textwidth} + \vspace{1em} +\begin{center} + \textbf{Candidate mechanism for the single-agent problem} +\end{center} + \begin{displaymath} + \begin{cases} + x_i = [t_i \geq p_i],\; p = p_0 + \sum_i p_ix_i &\text{ if} \sum_{i=1}^m (t_i - p_i)^+ \geq p_0 \\ + x_i = 0\text{ for all $i$},\; p = 0&\text{ otherwise } + \end{cases} + \end{displaymath} + \vspace{1em} +\end{minipage} +} +\end{center} +where we used the Iverson bracket notation $[P]$ to denote the indicator +variable of predicate $P$. + +We note that this mechanism is exactly the $\beta$-bundle mechanism from +\cite{yao}, even though the interpretation in terms of entrance fee plus posted +prices is not explicit in this paper. + +\subsection{$p$-exclusivity} + +As noted by Yao, the above mechanism has the additional property of being +$p$-exclusive in the following sense: for a vector $p = (p_1,\dots,p_m)$ +a mechanism is said to be $p$-exclusive if $x_i = 0$ whenever $p_i > t_i$. This +is essentially saying that there is a reserve price for each item. + +The notion of $p$-exclusivity introduced by Yao was crucial in his reduction +from the multiple-buyer setting to the single buyer setting. $p$-exclusivity +can easily be enforced in the problem we formulated in Section~\ref{sec:intro}, +by adding the following non-linear constraints: +\begin{displaymath} + x_i(t_i - p_i)\geq 0,\quad \forall i\in[m] +\end{displaymath} -Here are the steps we plan to execute before the completion of our project: +$p$-exclusivity relates to ex-ante allocation constraints through the following +Lemma. -\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} +\begin{lemma} + If a mechanism is $p$-exclusive for some vector $p=(p_1,\dots, p_m)$, then + it satisfies the ex-ante allocation constraint defined by $\hat{x} + = \big(F^{-1}(1-p_1), \dots, F^{-1}(1-p_m)\big)$. +\end{lemma} -In terms of timeline, we estimate that these steps will take us until beginning -of January 2015. \bibliographystyle{abbrv} \bibliography{main} |