diff options
Diffstat (limited to 'final/main.tex')
| -rw-r--r-- | final/main.tex | 62 |
1 files changed, 28 insertions, 34 deletions
diff --git a/final/main.tex b/final/main.tex index 13baefd..9e2f3f3 100644 --- a/final/main.tex +++ b/final/main.tex @@ -51,8 +51,10 @@ \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} +\newtheorem{conjecture}{Conjecture} \newtheorem*{definition}{Definition} \newtheorem*{goal}{Goal} +\newtheorem*{counterexample}{Counterexample} \newenvironment{proofsketch}[1][Proof Sketch]{\proof[#1]\mbox{}\\*}{\endproof} @@ -69,7 +71,11 @@ for this project.} \begin{abstract} -In this paper, given the problem of selling $m$ heterogeneous items, with ex-ante allocation constraint $\hat{x}$, to a single buyer with additive utility, having type drawn from the distribution $F$, we focus on finding a simple mechanism obeying the allocation constraint whose revenue is a constant approximation to the revenue of the optimal mechanism with this constraint. In particular, following a suggestion by J.D. Hartline, we define a mechanism based on a two-part tariff approach (in which the price charged to the buyer consists of an entrance fee plus posted prices for the items) and then draw a connection with a technique from \citep{yao}, in which we relate this mechanism to a $\beta$-exclusive mechanism. This mechanism can be viewed as a generalization of the work of \citep{babaioff}, where we have introduced allocation constraints. +In this paper, given the problem of selling $m$ heterogeneous items, with ex-ante allocation constraint $\hat{x}$, to a single buyer with additive utility, having type drawn from the distribution $F$, we focus on finding a simple mechanism obeying the allocation constraint whose revenue is a constant approximation to the revenue of the optimal mechanism with this constraint. + +In particular, following a suggestion by J.D. Hartline, we define a mechanism based on a two-part tariff approach (in which the price charged to the buyer consists of an entrance fee plus posted prices for the items) and then draw a connection with a technique from \citep{yao}, in which we relate this mechanism to a $\beta$-exclusive mechanism. This mechanism can be viewed as a generalization of the work of \citep{babaioff}, where we have introduced allocation constraints. + +We also explore an adaptation of the Core Decomposition lemma in \citep{babaioff}, as suggested by A. Rubinstein. While we did not solve the ex-ante pricing problem, we provide an exposition of our current understanding of the problem and what we perceive to be some of the obstacles remaining for a solution. \end{abstract} \section{Introduction} @@ -152,6 +158,8 @@ and a type distribution $F$, is there a simple mechanism whose ex-ante allocation rule is upper-bounded by $\hat{x}$ and whose revenue is a constant approximation to $\Rev(\hat{x},F)$?} +While we have not been able to answer this question, we provide an exposition of two potential approaches: a mechanism based on a two-part tariff approach, as suggested by J. D. Hartline and as an adaptation of the Core Decomposition Lemma from \citep{babaioff}, as suggested by A. Rubinstein. Thus, this problem remains open, but we hope that our discussion could suggest paths towards an eventual solution. + \subsection{Examples and Motivations} \paragraph{Single-item case.} @@ -349,7 +357,7 @@ a constant approximation to $\Rev(\hat{x}, F)$ by: $\beta$-exclusive mechanism (Theorem 6.1 in \citep{yao}). \end{enumerate} -Unfortunately, this approach breaks at step 1. To see why, consider for +There is a counterexample to step 1 for discrete, non-regular distributions. Consider for simplicity a discrete type space $T\subset \R_+^m$ and assume that the support of $F$ is exactly $T$. Writing $T = T_1\times\dots\times T_m$ and $F = F_1\times\dots\times F_m$, consider an ex-ante constraint $\hat{x}$ such that @@ -367,8 +375,8 @@ This mechanism is clearly IR and IC, satisfies the constraint $\hat{x}$ and has expected revenue $$\sum_{i\in [m]} \hat{x}_i t_i^{min}.$$ The revenue is positive whenever there exists $i$ such that $t_i^{min}>0$. -This example shows that the approximation ratio in step 1, described above, is -in fact unbounded. +This example shows that for discrete non-regular distributions, the approximation ratio in step 1, described above, is +in fact unbounded. However, this relies on the discreteness of the type distribution, and, we have not identified a counterexample for regular, continuous type distributions. \section{$n$-to-1 Bidders Reductions} \label{sec:reduction} @@ -455,20 +463,13 @@ Our proposed mechanism $\M$ can be viewed as a generalization of the work of \ci \appendix -\section{Addendum: Answers to Jason's Questions} - -\subsection{Counter-example on $\beta$-exclusive mechanisms} - -We agree that the counter-example, by exploiting heavily the discreteness of the -type distribution, is not satisfying in that it does not say anything about -regular (or simply continuous) distributions. +\section{Addendum: An Alternative Mechanism} -Yet, since the $\beta$-exclusive approach didn't seem as promising, and after -a discussion with Aviad Rubinstein, we tried instead to adapt the approach of +We also tried instead to adapt the approach of \cite{babaioff} to the ex-ante constrained problem: that is, showing that the maximum between (ex-ante constrained) grand bundling and separate posted pricing is a constant approximation to the optimal mechanism. Note that this -would imply, similarly to Lemma~\ref{tprevlemma} that our candidate two-part +would imply, similarly to Lemma~\ref{tprevlemma}, that our candidate two-part tariff mechanism is also a constant approximation to the optimal mechanism. The ``core decomposition'' Lemma of \cite{babaioff}, which is a key ingredient @@ -517,40 +518,33 @@ constraints, as we now show. = \hat{x}_T$. \end{proof} -Corollary~\ref{cor}, combined with Lemma~5 from \cite{babaoiff} (which can be -extended \emph{mutatis mutandi} to the constrained case) as in the proof -Lemma~6 from \cite{babaoiff} yields the following version of the core +Corollary~\ref{cor}, combined with Lemma~5 from \cite{babaioff} (which can be +extended, having made the appropriate changes, to the constrained case) as in the proof +Lemma~6 from \cite{babaioff} yields the following version of the core decomposition lemma: -\begin{lemma} +\begin{conjecture} $\Rev(\hat{x}, D)\leq \Val(D^C_\emptyset) + \sum_A p_A\Rev(\hat{x}_A, D^T_A)$. -\end{lemma} +\end{conjecture} However, if we keep pushing in this direction, it seems that the approach fails -when trying to obtain the following lemma: -\begin{lemma} +when trying to obtain the following: +\begin{conjecture} $\Rev(\hat{x}, D) \leq m\SRev(\hat{x}, D)$. -\end{lemma} +\end{conjecture} -This lemma would be required if we wanted to apply the same proof technique as +This conjecture would be required if we wanted to apply the same proof technique as \cite{babaioff} to the proof of the approximation ratio of our mechanism. Unfortunately, the proof of this lemma does not transpose easily to the ex-ante constrained case: the main idea is to use induction and Lemma~\ref{lemma:marginal} to ``split'' the set of items and reduce to the -induction hypothesis. Unfortunately, the ex-ante constraint does not work well -with this way of splitting. And we haven't been able to work around it and -obtain a positive result as of now. +induction hypothesis. -\subsection{Answer to the second question, to be rewritten} +However, A. Rubinstein identifies the following counterexample to this potential approach: +\begin{counterexample}[\citep{rubinstein2},Example 4 adapted] Consider a single-item auction with a single bidder, $m$ items, with each item having an ex-ante allocation probability of $\frac{1}{m^{1/4}}$ +\end{counterexample} -We did not solve the ex ante pricing problem. We were hoping to find an -approximately optimal mechanism for the ex-ante constrained single buyer, -multiple-items setting. This was our stated goal, both in the abstract and the -introduction, but we agree that the extent to which we solve it is not very -clear and we apologize for that. The rest of the paper is an exposition of what -we understood about the problem, and more precisely about the two-part tariff -mechanism. The original problem is still open at this point. \bibliographystyle{abbrvnat} \bibliography{main} |