From 7a24b373f4f5bdb1f7ded11442b0cf65391ad932 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 8 Jul 2013 09:51:46 -0700
Subject: alpha,beta

---
 appendix.tex | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'appendix.tex')

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.
-- 
cgit v1.2.3-70-g09d2

