diff options
Diffstat (limited to 'problem.tex')
| -rw-r--r-- | problem.tex | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/problem.tex b/problem.tex index 2a40185..98ca4ac 100644 --- a/problem.tex +++ b/problem.tex @@ -49,7 +49,7 @@ knowledge; the objective of the buyer in this context is to select a set $S$ maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq B$. We write: \begin{equation}\label{eq:non-strategic} - OPT(V,\mathcal{N}, B) = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid + OPT = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid \sum_{i\in S}c_i\leq B\right\} \end{equation} for the optimal value achievable in the full-information case. %\stratis{Should be $OPT(V,c,B)$\ldots better drop the arguments here and introduce them wherever necessary.} @@ -82,7 +82,7 @@ A mechanism is truthful iff every $i \in \mathcal{N}$ and every two cost vector \eqref{eq:non-strategic}. Formally, there must exist some $\alpha\geq 1$ such that: \begin{displaymath} - OPT(V,\mathcal{N}, B) \leq \alpha V(S). + OPT \leq \alpha V(S). \end{displaymath} 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. \item \emph{Computational efficiency.} The allocation and payment function |