From 4a89391c9d18d8a2e1b3a88bc3bf108890e2cad1 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sat, 6 Jul 2013 17:15:37 -0700
Subject: payoff

---
 problem.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index 6c717af..f3ac078 100644
--- a/problem.tex
+++ b/problem.tex
@@ -148,7 +148,7 @@ $S:\reals_+^n \to 2^\mathcal{N}$,  determining the set
 $p:\reals_+^n\to \reals_+^n$, determining the payments $[p_i(c)]_{i\in \mathcal{N}}$ received by experiment subjects.
   
 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 payoff by reporting a cost that differs more than $\delta$ from their true cost. Under this definition, a mechanism is truthful if $\delta=0$. 
+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$ 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 the allocation and payment functions can be computed in polynomial time.
 
 We note that the $\max$ operator in  the greedy algorithm \eqref{eq:max-algorithm} breaks
-- 
cgit v1.2.3-70-g09d2

