From 6be1a06c3dafa8ac938600cbd0780f14d5dc0e36 Mon Sep 17 00:00:00 2001 From: Paul Date: Wed, 13 May 2015 18:11:50 -0400 Subject: Added stuff --- final/main.tex | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-) (limited to 'final') diff --git a/final/main.tex b/final/main.tex index b778e23..d3a1cc8 100644 --- a/final/main.tex +++ b/final/main.tex @@ -52,6 +52,8 @@ \newtheorem*{definition}{Definition} \newtheorem*{goal}{Goal} +\newenvironment{proofsketch}[1][Proof Sketch]{\proof[#1]\mbox{}\\*}{\endproof} + \author{Thibaut Horel \and Paul Tylkin} \title{The Additive Single Buyer Problem\\ with Ex-Ante Allocation Constraints \\ \vskip0.1in {\sc Economics 2099 Project}} \date{} @@ -363,7 +365,7 @@ 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 +This example shows that the approximation ratio in step 1, described above, is in fact unbounded. \section{$n$-to-1 Bidders Reductions} @@ -391,10 +393,17 @@ We will step through his results in greater detail, and also improve the approxi $$ F^+_{\beta,i} = \begin{cases} F_i | (F_i > \beta_i) &\text{if } \xi_i = 1 \\ \beta_i &\text{otherwise}\end{cases}$$ \end{definition} -Intuitively, this defines a transformation of the distribution $F$ using $\beta$ which can then be used in the following lemma to relate the revenue of the optimal $\beta$-exclusive mechanism to the revenue of the optimal mechanism. +Intuitively, this defines a transformation of the distribution $F$ using $\beta$ which can then be used in the following lemma to relate the revenue of the optimal $\beta$-exclusive mechanism to the revenue of the optimal mechanism. This new distribution $F_\beta^+$, which has support $[\beta_1,\infty) \times \cdots \times [\beta_m,\infty)$, is then shifted, so that the distribution $F_\beta^+ - \beta$ has support $[0,\infty) \times \cdots \times [0,\infty) = [0,\infty)^k$. \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 \cdot \xi(F) + \Rev(F_\beta^+ - \beta).$$ \end{lemma} +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 \cdot \xi(F) + \Rev(F_\beta^+ - \beta).$$ \begin{proofsketch} Let $M$ be an IR-IC $\beta$-exclusive mechanism with allocation rule $x(t)$ and payment rule $p(t)$. The goal is to prove that $$ \Rev_\beta(F) \leq \E_{t \sim F}[(p(t)] \leq \beta \cdot \xi(F) + \Rev(F_\beta^+ - \beta)$$. + +First, we establish that \begin{align*} \Rev_\beta(F) \leq \E_{t \sim F}[p(t)] &= \E_{t \sim F}[\beta\cdot x(t)] + \E_{t \sim F}[p(t) - \beta\cdot x(t)] \\ &= \beta \cdot \xi(F) + \E_{t \sim F}[p(t) - \beta \cdot x(t)]. \end{align*} The first inequality follows from the definition of $\beta$-exclusivity, namely that the revenue of a $\beta$-exclusive mechanism is upper-bounded by the revenue of a mechanism with the same type distribution, payment rule, allocation rule, but $\beta = (1,...,1)$. + +Next, we define another mechanism, $M'$, such that $M'$ is also IR-IC, and has allocation rule $\tilde{x}(\tilde{t})$ and payment rule $\tilde{p}(\tilde{t})$, with $\tilde{t} \sim F_\beta^+$, so that we have $$\E_{t \sim F}[p(t) - \beta \cdot x(t)] \leq \E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \beta \cdot \tilde{x}(\tilde{t})].$$ + +Finally, we show that $$\E_{\tilde{t} \sim F_{\beta}^+}[\tilde{p}(\tilde{t}) - \beta \cdot \tilde{x}(\tilde{t})] \leq \Rev(F_\beta^+ - \beta),$$ where the mechanism $M''$ that has revenue given by $\Rev(F_\beta^+ - \beta)$ is also shown to be IR-IC. + \end{proofsketch}\end{lemma} \bibliographystyle{abbrvnat} \bibliography{main} -- cgit v1.2.3-70-g09d2