diff options
| -rw-r--r-- | appendix.tex | 6 | ||||
| -rw-r--r-- | main.tex | 2 |
2 files changed, 4 insertions, 4 deletions
diff --git a/appendix.tex b/appendix.tex index 904bd45..5cb60f8 100644 --- a/appendix.tex +++ b/appendix.tex @@ -510,10 +510,10 @@ an \emph{almost-dominant} \cite{schummer2004almost} strategy. Formally, let $c_{ B.\label{budget}$ - \item \emph{Approximation Ratio.} The value of the allocated set should not + \item \emph{$(\alpha,\beta)$-approximation.} The value of the allocated set should not be too far from the optimum value of the full information case, as given by \eqref{eq:non-strategic}. -Formally, there must exist some $\alpha\geq 1$ - such that $OPT \leq \alpha V(S(p))$, where $OPT = \max_{S\subseteq\mathcal{N}} \left\{V(S) \;\mid \; +Formally, there must exist some $\alpha\geq 1$ and $\beta>0$ + such that $OPT \leq \alpha V(S(p))+\beta$, where $OPT = \max_{S\subseteq\mathcal{N}} \left\{V(S) \;\mid \; \sum_{i\in S}c_i\leq B\right\}$. % The approximation ratio captures the \emph{price of truthfulness}, \emph{i.e.}, the relative value loss incurred by adding the truthfulness constraint. % to the value function maximization. @@ -70,7 +70,7 @@ Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the a For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$, there exists a $\delta$-truthful, individually rational and budget feasible mechanim for \EDP{} that runs in time $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$ - and returns + and allocates a set $S^*$ such that % \begin{align*} $ OPT |