alpha,beta

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.