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 358c825..9d67074 100644 --- a/problem.tex +++ b/problem.tex @@ -184,8 +184,8 @@ Given that the full information problem \EDP{} is NP-hard, we further seek mecha % 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. We stress here that the approximation ratio is defined with respect \emph{to the maximal value in the full information case}. \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}. + should be computable in time polynomial in various parameters. + %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} As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one |