From 43c2c5cfa7a1fe31795bbc00c56116a25544da26 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Mon, 8 Jul 2013 09:37:37 -0700 Subject: alpha, beta --- problem.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'problem.tex') diff --git a/problem.tex b/problem.tex index 8d5b262..1ac1a38 100644 --- a/problem.tex +++ b/problem.tex @@ -143,7 +143,7 @@ $p:\reals_+^n\to \reals_+^n$, determining the payments $[p_i(c)]_{i\in \mathcal{ We seek mechanisms that are \emph{normalized} (unallocated experiments receive zero payments), \emph{individually rational} (payments for allocated experiments exceed costs), have \emph{no positive transfers} (payments are non-negative), and are \emph{budget feasible} (the sum of payments does not exceed the budget $B$). We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring that reporting one's true cost is an \emph{almost-dominant} strategy: no subject increases their utility by reporting a cost that differs more than $\delta>0$ from their true cost. Under this definition, a mechanism is truthful if $\delta=0$. -In addition, we would like the allocation $S(c)$ to be of maximal value; however, $\delta$-truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with that yield a \emph{constant approximation ratio}, \emph{i.e.}, there exists $\alpha\geq 1$ s.t.~$OPT \leq \alpha V(S(c))$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time. +In addition, we would like the allocation $S(c)$ to be of maximal value; however, $\delta$-truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with that are \emph{$(\alpha,\beta)$-approximate}, \emph{i.e.}, there exist $\alpha\geq 1$ and $\beta>0$ s.t.~$OPT \leq \alpha V(S(c))+\beta$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time. We note that the greedy algorithm \eqref{eq:max-algorithm} breaks truthfulness. Though this is not true for all submodular functions (see, \emph{e.g.}, \cite{singer-mechanisms}), it is true for the objective of \EDP{}: we show this in Appendix~\ref{sec:non-monotonicity}. This motivates our study of more complex mechanisms. -- cgit v1.2.3-70-g09d2