From f884186cb1e840c7b6abd343978b62cbac206cd8 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 11 Feb 2013 12:02:10 -0800
Subject: problem

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

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index aaca0cc..536481a 100644
--- a/problem.tex
+++ b/problem.tex
@@ -138,11 +138,11 @@ We study the strategic case, in wich the costs $c_i$ are {\em not} common knowle
 
 
 
-When the experiment subjects are strategic, the experimental design problem becomes a special case of  a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}. Formally, a \emph{mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function}
+When the experiment subjects are strategic, the experimental design problem becomes a special case of  a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}. Formally, given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function}
 $S:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function}
 $p:\reals_+^n\to \reals_+^n$. Given the
-vector or costs $c=[c_i]_{i\in\mathcal{N}}$, the allocation function $S$ determines the set in
-$ \mathcal{N}$ of items to be purchased, while the payment function
+vector of costs $c=[c_i]_{i\in\mathcal{N}}$, the allocation function $S$ determines the set in
+$ \mathcal{N}$ of experiments to be purchased, while the payment function
 returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$.
  Let $s_i(c) = \id_{i\in S(c)}$ be the binary indicator of  $i\in S(c)$. Mechanism design in budget feasible reverse auctions seeks mechanisms that have the following properties \cite{singer-mechanisms,chen}:
 \begin{itemize}
@@ -150,19 +150,19 @@ returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$.
  \begin{align}s_i(c)=0\text{ implies }p_i(c)=0.\label{normal}\end{align}
 \item\emph{Individual Rationality.} Payments for allocated experiments exceed costs, \emph{i.e.},
  \begin{align} p_i(c)\geq c_i\cdot s_i(c).\label{ir}\end{align}
-\item \emph{No Positive Transfers.} Payments are non-negative,\emph{i.e.},
+\item \emph{No Positive Transfers.} Payments are non-negative, \emph{i.e.},
 \begin{align}p_i(c)\geq 0\label{pt}.\end{align} 
-    \item \emph{Truthfulness/Incentive Compatibility.} An agent has no incentive to missreport her true cost. Formally, let $c_{-i}$
+    \item \emph{Truthfulness/Incentive Compatibility.} An experiment subject has no incentive to missreport her true cost. Formally, let $c_{-i}$
  be a vector of costs of all agents except $i$. Then, %    $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i',
 %    c_{-i})$, then the 
-\begin{align}  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\label{truthful}\end{align} for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$.
+\begin{align}  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, \label{truthful}\end{align} for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$.
     \item \emph{Budget Feasibility.} The sum of the payments should not exceed the
     budget constraint, \emph{i.e.}
     %\begin{displaymath}
      \begin{align}   \sum_{i\in\mathcal{N}} p_i(c) \leq B.\label{budget}\end{align}
     %\end{displaymath}
 \end{itemize}
-We define the \emph{Strategic} version of \EDP as
+We define the \emph{Strategic} version of \EDP{} as
 \begin{center}
 \textsc{StrategicExperimentalDesignProblem} (SEDP)
 %\begin{subequations}
@@ -174,7 +174,7 @@ We define the \emph{Strategic} version of \EDP as
 \end{center}
 Given that the full information problem \EDP{} is NP-hard, we further seek mechanisms that have the following two additional properties:
 \begin{itemize}
-    \item \emph{Approximation ratio.} The value of the allocated set  should not
+    \item \emph{Approximation Ratio.} The value of the allocated set  should not
     be too far from the optimum value of the full information case
     \eqref{eq:non-strategic}. Formally, there must exist some $\alpha\geq 1$
     such that:
@@ -183,7 +183,7 @@ Given that the full information problem \EDP{} is NP-hard, we further seek mecha
     \end{displaymath}
  %   The approximation ratio captures the \emph{price of truthfulness}, \emph{i.e.},  the relative value loss incurred by adding the truthfulness constraint. % to the value function maximization.
     We stress here that the approximation ratio is defined with respect \emph{to the maximal value in the full information case}.
-    \item \emph{Computational efficiency.} The allocation and payment function
+    \item \emph{Computational Efficiency.} The allocation and payment function
     should be computable in polynomial time in the number of
     agents $n$. %\thibaut{Should we say something about the black-box model for $V$?  Needed to say something in general, but not in our case where the value function can be computed in polynomial time}.
 \end{itemize}
-- 
cgit v1.2.3-70-g09d2

