summaryrefslogtreecommitdiffstats
path: root/problem.tex
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2012-11-04 22:44:51 +0100
committerThibaut Horel <thibaut.horel@gmail.com>2012-11-04 22:44:51 +0100
commitcf952f7a9cf431b7f49fd8150a183295e8f894c1 (patch)
tree586f9291ab9f93aa32428b934d21c77901f6e698 /problem.tex
parent13222e35de229c969419ffd7e47d0080810b56f7 (diff)
parentfe1eddfacaec77b0038abdb899d3f5a56352e8b4 (diff)
downloadrecommendation-cf952f7a9cf431b7f49fd8150a183295e8f894c1.tar.gz
Merge branch 'master' of ssh://74.95.195.229:1444/git/data_value
Conflicts: general.tex
Diffstat (limited to 'problem.tex')
-rw-r--r--problem.tex2
1 files changed, 1 insertions, 1 deletions
diff --git a/problem.tex b/problem.tex
index 363731a..e3ee84b 100644
--- a/problem.tex
+++ b/problem.tex
@@ -85,7 +85,7 @@ A mechanism is truthful iff every $i \in \mathcal{N}$ and every two cost vector
OPT(V,\mathcal{N}, B) \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{Computationally efficient.} The allocation and payment function
+ \item \emph{Computational efficiency.} The allocation and payment function
should be computable in polynomial time in the number of
agents $n$. %\thibaut{Should we say something about the black-box model for $V$? Needed to say something in general, but not in our case where the value function can be computed in polynomial time}.
\end{itemize}