From 411e59045922c4d50d14fb30aa5e0bdeecf42991 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sat, 6 Jul 2013 14:05:17 -0700
Subject: intro sufficiently concave

---
 intro.tex | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'intro.tex')

diff --git a/intro.tex b/intro.tex
index 4d8b5dd..8a8c2c0 100644
--- a/intro.tex
+++ b/intro.tex
@@ -22,7 +22,7 @@ In our setting, experiments cannot be manipulated and hence measurements are rel
 There is a cost $c_i$ associated with experimenting on
 subject $i$ which varies from subject to subject.  This cost $c_i$ is determined by the subject $i$: it may be viewed as the  
 cost $i$ incurs when tested and for which she needs to be reimbursed; or, it might be viewed as the incentive for $i$ to participate in the experiment; or, it might be the intrinsic worth of the data to the subject. The economic aspect of paying subjects has always been inherent in experimental design: experimenters often work within strict budgets and design creative incentives. Subjects often negotiate better incentives or higher payments. 
-However, we are not aware of a principled study of this setting from a strategic point of view, when subjects declare their costs and therefore determine their payment.  Such a setting is increasingly realistic, given the growth of these experiments over the Internet and associated data markets. 
+However, we are not aware of a principled study of this setting from a strategic point of view, when subjects declare their costs and therefore determine their payment.  Such a setting is increasingly realistic, given the growth of these experiments over the Internet. % and associated data markets. 
 
 % When subjects are strategic, they may have an incentive to misreport their cost, leading to the need for a sophisticated choice of experiments and payments. Arguably, user incentiviation is of particular pertinence due to the extent of statistical analysis over user data on the Internet. %, which has led to the rise of several different research efforts in studying data markets \cite{...}.
 
@@ -64,7 +64,7 @@ We note that the objective \eqref{obj} is submodular. Using this fact, applying
 From a technical perspective, we propose a convex optimization problem and establish that its optimal value within a constant factor from the optimal value of \EDP.  
  In particular, we show our relaxed objective is within a constant factor from the so-called multi-linear extension of  \eqref{obj}, which in turn can be related to \eqref{obj} through pipage rounding. We establish the constant factor to the multi-linear extension by bounding  the partial derivatives of these two functions; we achieve the latter by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices.
 
-Our convex relaxation of \EDP{} involves maximizing a self-concordant function subject to linear constraints. Its optimal value can be computed with arbitrary accuracy in polynomial time using the so-called barrier method. However, the outcome of this computation may not necessarily be monotone, a property needed in designing a truthful mechanism. Nevetheless, we construct an algorithm that solves the above convex relaxation and is ``almost'' monotone; in turn, we also show that this algorithm can be employed to design a $\delta$-truthful mechanism for \EDP{}.
+Our convex relaxation of \EDP{} involves maximizing a self-concordant function subject to linear constraints. Its optimal value can be computed with arbitrary accuracy in polynomial time using the so-called barrier method. However, the outcome of this computation may not necessarily be monotone, a property needed in designing a truthful mechanism. Nevetheless, we construct an algorithm that solves the above convex relaxation and is ``almost'' monotone; we achieve this by applying the barrier method on a set perturbed constraints, over which our objective is ``sufficiently'' concave. In turn, we also show that this algorithm can be employed to design a $\delta$-truthful mechanism for \EDP{}.
 
 
 %This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}.   %{\bf FIX the last sentence}
-- 
cgit v1.2.3-70-g09d2

