From c29302b25adf190f98019eb8ce5f79b10b66d54d Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 5 Nov 2012 16:04:20 +0100
Subject: Typos

---
 problem.tex | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index 98ca4ac..4ddaab4 100644
--- a/problem.tex
+++ b/problem.tex
@@ -54,7 +54,7 @@ B$. We write:
 \end{equation}
 for the optimal value achievable in the full-information case. %\stratis{Should be $OPT(V,c,B)$\ldots better drop the arguments here and introduce them wherever necessary.}
 
-In the \emph{strategic case}, each items in $\mathcal{N}$ is held by a different strategic agent, whose cost is a-priori private.
+In the \emph{strategic case}, each items in $\mathcal{N}$ is held by a different strategic agent, whose cost is \emph{a priori} private.
 A \emph{mechanism} $\mathcal{M} = (f,p)$ comprises (a) an \emph{allocation function}
 $f:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function}
 $p:\reals_+^n\to \reals_+^n$. Given the
@@ -67,10 +67,10 @@ no positive transfers ($p_i(c)\geq 0$).
 
 In addition to the above, mechanism design in budget feasible reverse auctions seeks mechanisms that have the following properties \cite{singer-mechanisms,chen}:
 \begin{itemize}
-    \item \emph{Truthfulness.} An agent has no incentive to missreport her true cost. Formally, let $c_{-i}$
+    \item \emph{Truthfulness.} An agent has no incentive to misreport her true cost. Formally, let $c_{-i}$
  be a vector of costs of all agents except $i$. %    $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i',
 %    c_{-i})$, then the 
-A mechanism is truthful iff  every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$
+A mechanism is truthful iff for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$
  $p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s(c_i',c_{-i})\cdot c_i$.
     \item \emph{Budget Feasibility.} The sum of the payments should not exceed the
     budget constraint:
@@ -108,8 +108,10 @@ c_{-i})$ implies $i\in f(c_i', c_{-i})$, and (b)
 \end{lemma}
 \fussy
 Myerson's Theorem is particularly useful when designing a budget feasible truthful
-mechanism, as it allows us to focus on designing a monotone allocation function. Then, the
-mechanism will be truthful as long as we give each agent her threshold payment---the caveat being that the latter need to sum to a value below $B$.
+mechanism. One can focus on designing a monotone allocation function, and the
+resulting mechanism will be truthful as long as each agent is given her
+threshold payment---the caveat being that the latter need to sum to a value
+below $B$.
 
 \subsection{Budget Feasible Experimental Design}
 In this paper, we approach the problem of optimal experimental design from the
@@ -130,9 +132,9 @@ incentivize her participation in the study. Note that, in this setup, the featur
 
 %\subsection{D-Optimality Criterion}
 Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes \eqref{dcrit} within a good approximation ratio. As \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation one would consider  the (equivalent) maximization of $V(S) = \det\T{X_S}X_S$. %, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. 
-However, the following lower bound implies that such an optimization goal cannot be attained under the costraints of  truthfulness, budget feasibility, and individual rationallity.
+However, the following lower bound implies that such an optimization goal cannot be attained under the constraints of  truthfulness, budget feasibility, and individual rationality.
 \begin{lemma}
-For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individionally rational mechanism for a budget feasible reverse auction with value fuction $V(S) = \det{\T{X_S}X_S}$.
+For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individually rational mechanism for a budget feasible reverse auction with value function $V(S) = \det{\T{X_S}X_S}$.
 \end{lemma}
 \begin{proof}
 \input{proof_of_lower_bound1}
-- 
cgit v1.2.3-70-g09d2

