From 0d429224b86ee6b4002e53214c4d2c9222ecbe27 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 4 Nov 2012 09:57:24 -0800 Subject: intro main --- problem.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'problem.tex') 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} -- cgit v1.2.3-70-g09d2