From 1aec92a787374451c7757be86bd27ee4ac064c41 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Thu, 1 Nov 2012 17:01:27 +0100
Subject: Some typos

---
 problem.tex | 11 ++++-------
 1 file changed, 4 insertions(+), 7 deletions(-)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index 2c80d4e..5723581 100644
--- a/problem.tex
+++ b/problem.tex
@@ -34,8 +34,6 @@ As $\hat{\beta}$ is a multidimensional normal random variable, the $D$-optimalit
 \subsection{Budget Feasible Mechanism Design}
 In this paper, we approach the problem of optimal experimental design from the perspective of \emph{a budget feasible reverse auction} \cite{singer-mechanisms}. In particular, we assume that each experiment $i\in \mathcal{N}$ is associated with a cost $c_i$, that the experimenter needs to pay in order to conduct the experiment.  The experimenter has a budget $B\in\reals_+$. In the \emph{full information case}, the costs are common knowledge; optimal design in this context amounts to selecting a set $S$ maximizing the value $V(S)$ subject to the constraint $\sum_{i\in S} c_i\leq B$.
 
-As in \cite{singer-mechanisms,chen}, we focus in a \emph{strategic scenario}: experiment $i$ corresponds to a \emph{strategic agent}, whose cost $c_i$ is private.  For example, each $i$ may correspond to a human participant; the feature vector $x_i$ may correspond to a normalized vector of her age, weight, gender, income, \emph{etc.}, and the measurement $y_i$ may capture some biometric information (\emph{e.g.}, her red cell blood count, a genetic marker, etc.). The cost $c_i$ is the amount the participant deems sufficient to incentivize her participation in the study. 
-
 As in \cite{singer-mechanisms,chen}, we focus in a \emph{strategic scenario}:
 experiment $i$ corresponds to a \emph{strategic agent}, whose cost $c_i$ is
 private.  For example, each $i$ may correspond to a human participant; the
@@ -45,7 +43,6 @@ biometric information (\emph{e.g.}, her red cell blood count, a genetic marker,
 etc.). The cost $c_i$ is the amount the participant deems sufficient to
 incentivize her participation in the study.
 
-
 A 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$. The allocation function determines, given the
@@ -61,21 +58,21 @@ Furthermore, we want to design a mechanism which is:
     \item \emph{Truthful.} An agent has no incentive to report a cost $c_i'$
     different from his true cost $c_i$. Formally, let us write $(c_i', c_{-i})$
     the vector of costs when agent $i$ reports cost $c_i'$ (all the other costs
-    $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = f(c_i',
+    $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i',
     c_{-i})$, then the mechanism is truthful iff (a) $i\notin
     f(c_i,c_{-i})\implies i\notin f(c_i',c_{-i})$ and (b) $p_i - c_i \geq p_i'
-    - c_i$ 
+    - c_i$.
     \item \emph{Budget Feasible.} The sum of the payments should not exceed the
     budget constraint:
     \begin{displaymath}
-        \sum_{i\in\mathcal{N}} p_i \leq B
+        \sum_{i\in\mathcal{N}} p_i \leq B.
     \end{displaymath}
     \item \emph{Approximation ratio.} The value of the allocated set should not
     be too far from the optimum value of the non-strategic case
     \eqref{eq:non-strategic}. Formally, there must exist some $\alpha\geq 1$
     such that:
     \begin{displaymath}
-        OPT(V,\mathcal{N}, B) \leq \alpha V(S)
+        OPT(V,\mathcal{N}, B) \leq \alpha V(S).
     \end{displaymath}
     The approximation ratio captures the \emph{price of truthfulness}: this is
     what you loose by moving from the non-strategic case to the strategic case
-- 
cgit v1.2.3-70-g09d2

