From fb9fa7fc2a39eb415e3348b6756d397e6b820d09 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 2 Nov 2012 16:54:00 +0100
Subject: Strating addressing Stratis' comments

---
 problem.tex | 28 +++++++++++++++++++++++-----
 1 file changed, 23 insertions(+), 5 deletions(-)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index 03ce49b..0ba9db9 100644
--- a/problem.tex
+++ b/problem.tex
@@ -34,7 +34,21 @@ Value function \eqref{dcrit} has several appealing properties. To begin with, it
 
 
 \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$.
+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$. We write:
+\begin{equation}\label{eq:non-strategic}
+    OPT(V,\mathcal{N}, B) = \max_{S\subseteq\mathcal{N}} \left\{V(S) \mid
+    \sum_{i\in S}\leq B\right\}
+\end{equation}
+the best value we can reach under the budget constraint $B$ when selecting
+experiments from the set $\mathcal{N}$.
 
 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
@@ -55,7 +69,7 @@ returns a vector of payments $[p_i]_{i\in \mathcal{N}}$. As in
 ($i\notin S$ implies $p_i=0$), individually rational ($p_i\geq c_i$) and have
 no positive transfers $p_i\geq 0$. 
 
-Furthermore, we want to design a mechanism which is:
+Moreover, we want to design a mechanism which has the following properties:
 \begin{itemize}
     \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})$
@@ -93,16 +107,20 @@ a characterization of truthful mechanisms.
 \begin{theorem}[Myerson \cite{myerson}]\label{thm:myerson}
 A normalized mechanism $\mathcal{M} = (f,p)$ for a single parameter auction is
 truthful iff:
-\begin{itemize}
+\begin{enumerate}
 \item $f$ is \emph{monotone}: for any agent $i$ and $c_i' \leq c_i$, for any
 fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in f(c_i,
 c_{-i})\implies i\in f(c_i', c_{-i})$.
 \item agents are paid their \emph{threshold payments}: agent $i$ receives
 $\inf\{c_i: i\in f(c_i, c_{-i})\}$.
-\end{itemize}
+\end{enumerate}
 \end{theorem}
 
-\stratis{Explain why this is important and what it implies about the things we need to prove. Also, don't overuse bullets.}
+This theorem is particularly useful when designing a truthful mechanism: we
+can focus on designing a monotone allocation function. Then the mechanism will
+be truthful as long as we give each agent her threshold payment. Finally, it
+suffices to prove that the sum of threshold payments does not exceed the budget
+to ensure budget feasibility.
 
 \begin{comment}
 \subsection{Experimental Design}
-- 
cgit v1.2.3-70-g09d2

