diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2012-11-04 23:38:08 -0800 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2012-11-04 23:38:08 -0800 |
| commit | cec9b298f548ce44fe5eaecf71c04d65c95de993 (patch) | |
| tree | 13f4281ec9d84ef688762b118902f8c530a5bd4c /problem.tex | |
| parent | c3bbc02ac28d7019588d0c97e39b9e249ee5442a (diff) | |
| download | recommendation-cec9b298f548ce44fe5eaecf71c04d65c95de993.tar.gz | |
opts
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 |
