diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 6 |
1 files changed, 3 insertions, 3 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. |