From cec9b298f548ce44fe5eaecf71c04d65c95de993 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 4 Nov 2012 23:38:08 -0800 Subject: opts --- problem.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'problem.tex') 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 -- cgit v1.2.3-70-g09d2