diff options
Diffstat (limited to 'final')
| -rw-r--r-- | final/main.bib | 39 | ||||
| -rw-r--r-- | final/main.tex | 37 |
2 files changed, 38 insertions, 38 deletions
diff --git a/final/main.bib b/final/main.bib index a50107a..aaf7c97 100644 --- a/final/main.bib +++ b/final/main.bib @@ -5,7 +5,7 @@ S. Matthew Weinberg}, title = {A Simple and Approximately Optimal Mechanism for an Additive Buyer}, journal = {FOCS}, - year = {2014}, + year = {2014} } @article{yao, @@ -13,11 +13,7 @@ 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} + year = {2014} } @inproceedings{hart, @@ -27,12 +23,7 @@ booktitle = {{ACM} Conference on Electronic Commerce, {EC} '13, Philadelphia, PA, USA, June 16-20, 2013}, pages = {565--566}, - year = {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} + year = {2013} } @book{hartline, @@ -51,11 +42,6 @@ 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, @@ -85,10 +71,17 @@ booktitle = {{ACM} Conference on Electronic Commerce, {EC} '12, Valencia, Spain, June 4-8, 2012}, pages = {656}, - year = {2012}, - url = {http://doi.acm.org/10.1145/2229012.2229061}, - doi = {10.1145/2229012.2229061}, - timestamp = {Mon, 24 Feb 2014 16:09:47 +0100}, - biburl = {http://dblp.uni-trier.de/rec/bib/conf/sigecom/HartN12}, - bibsource = {dblp computer science bibliography, http://dblp.org} + year = {2012} +} + +@inproceedings{alaeietal, + author = {Saeed Alaei and + Hu Fu and + Nima Haghpanah and + Jason D. Hartline}, + title = {The Simple Economics of Approximately Optimal Auctions}, + booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS} + 2013, 26-29 October, 2013, Berkeley, CA, {USA}}, + pages = {628--637}, + year = {2013}, } diff --git a/final/main.tex b/final/main.tex index ce27f47..b49e959 100644 --- a/final/main.tex +++ b/final/main.tex @@ -31,9 +31,10 @@ \endgroup } -\DeclareMathOperator*{\E}{\mathbb{E}} + +\DeclareMathOperator*{\E}{\mathbf{E}} \let\Pr\relax -\DeclareMathOperator*{\Pr}{\mathbb{P}} +\DeclareMathOperator*{\Pr}{\mathbf{P}} \DeclareMathOperator*{\I}{\mathcal{I}} \DeclareMathOperator*{\TPRev}{\textsc{TPRev}} \DeclareMathOperator*{\Rev}{\textsc{Rev}} @@ -48,12 +49,15 @@ \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} +\newtheorem*{definition}{Definition} \newtheorem*{goal}{Goal} \author{Thibaut Horel \and Paul Tylkin} \title{The Additive Single Buyer Problem\\ with Ex-Ante Allocation Constraints \\ \vskip0.1in {\sc Economics 2099 Project}} \date{} \begin{document} +%include all references +\nocite{*} \maketitle @@ -306,10 +310,9 @@ essentially saying that there is a reserve price for each item. Theorem 6.1 from \citep{yao} shows that for an optimal choice of $\hat{v}_{-1}\geq \beta$ and $\hat{v}_0$, mechanism $\M$ described above is -a constant $7$-approximation to the optimal $\beta$-exclusive mechanism. +a constant $7$-approximation to the optimal $\beta$-exclusive mechanism. We will discuss this in greater detail in Section \ref{sec:reduction}. -There is an easy one-way reduction from $\hat{x}$ ex-ante constrained -mechanisms to $\beta$-exclusive mechanisms captured by the following Lemma. +There is a one-way reduction from mechanisms with ex-ante constraint $\hat{x}$ to $\beta$-exclusive mechanisms captured by the following Lemma. \begin{lemma} If a mechanism is $\beta$-exclusive with $\beta\geq F^{-1}(1-\hat{x})$, then @@ -331,11 +334,12 @@ This is true for all $i\in[m]$ so the mechanism satisfies the ex-ante allocation constraint $\hat{x}$. \end{proof} +Let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. One could hope to use this reduction to show that $\TPRev(\hat{x}, F)$ is a constant approximation to $\Rev(\hat{x}, F)$ by: \begin{enumerate} \item showing that the revenue of the optimal $\beta$-exclusive - mechanism with $\beta = F^{-1}(1-\hat{x})$ is a constant approximation + mechanism, $\Rev_\beta(F)$, with $\beta = F^{-1}(1-\hat{x})$ is a constant approximation to $\Rev(\hat{x}, F)$. \item using that $\M$ is a constant approximation to the optimal $\beta$-exclusive mechanism (Theorem 6.1 in \citep{yao}). @@ -352,29 +356,29 @@ allocate any item and hence will have a revenue of $0$. Hence the optimal $\beta$-exclusive mechanism for $\beta = F^{-1}(1-\hat{x})$ will have revenue $0$. -However, there is a very simple mechanism which satisfies the $\hat{x}$ ex-ante -allocation constraint: regardless of the type, allocate each item $i\in [m]$ -with probability $\hat{x}_i$ at price $t_i^{min}\eqdef\min_{t_i\in T_i} t_i$. +However, there is a very simple mechanism which satisfies the ex-ante +allocation constraint $\hat{x}$: regardless of the type, allocate each item $i\in [m]$ +with probability $\hat{x}_i$ at price $$t_i^{min}\eqdef\min_{t_i\in T_i} t_i.$$ 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 +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. \section{$n$-to-1 Bidders Reductions} - +\label{sec:reduction} The goal of this section is to compare the two ways of constraining the single buyer problem that we discussed: namely $p$-exclusivity and ex-ante allocation constraints and draw a parallel in how these two notions are used to construct $n$-to-1 bidders reductions in \citep{yao} and \citep{alaei} respectively. \subsection{\citep{alaei}'s Approach} \subsection{\citep{yao}'s Approach} -The notion of $p$-exclusivity introduced by \citep{yao} was crucial in his +The notion of $\beta$-exclusivity introduced by \citep{yao} was crucial in his reduction from the $m$-item $n$-buyer setting to the $m$-item single buyer setting. He describes a mechanism known as \emph{Best-Guess Reduction}, which -conducts $n$ single-buyer $m$-item auctions, using an IR-IC $p$-exclusive -mechanism, for a particular value of $p$ drawn from the joint bid distribution +conducts $n$ single-buyer $m$-item auctions, using an IR-IC $\beta$-exclusive +mechanism, for a particular value of $\beta$ drawn from the joint bid distribution over all buyers conditioned on the bids of all other buyers, and then combines this with the Vickrey second-price auction, showing that this mechanism has revenue that is a constant approximation to the optimal $m$-item, $n$-buyer @@ -382,7 +386,10 @@ mechanism. He then defines another mechanism, \emph{Second-Price Bundling}, which is meant to heuristically approximate this combined mechanism, and shows that its revenue is also a constant approximation to the optimal mechanism. -We will step through his results in greater detail, and also improve the approximation ratio in one of his lemmas, using the result from the published version of \citep{babaioff}. +We will step through his results in greater detail, and also improve the approximation ratio in one of his lemmas, using the result from the published version of \citep{babaioff}. We begin with a definition and a key lemma: +\begin{definition}[$F^+_\beta$, Definition 4.1 in \citep{yao}] \end{definition} +\begin{lemma}[Lemma 6.1 in \citep{yao}] +Let $F =F_1\times\dots\times F_m$, and let $\Rev_\beta(F)$ be the revenue of the optimal $\beta$-exclusive mechanism. Let $$\xi(F) = (\Pr[t_1> \beta_1],...,\Pr[t_m > \beta_m]).$$ Then, $$Rev_\beta(F) \leq \beta \xi(F) + \Rev(F_\beta^+ - \beta).$$ \end{lemma} \bibliographystyle{abbrvnat} \bibliography{main} |