Moving the proofs to the appendix, improving the flow

1 files changed, 15 insertions, 32 deletions

diff --git a/problem.tex b/problem.tex
index 6bfac6b..a5db2ac 100644
--- a/problem.tex
+++ b/problem.tex
@@ -146,22 +146,20 @@ $ \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)$. As usual, we seek mechanisms that have the following properties \cite{singer-mechanisms}:
 \begin{itemize}
-\item \emph{Normalization.} Unallocated experiments receive zero payments, \emph{i.e.},
- \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.},
-\begin{align}p_i(c)\geq 0\label{pt}.\end{align} 
-    \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_i(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}
+\item \emph{Normalization.} Unallocated experiments receive zero payments: $s_i(c)=0\text{ implies }p_i(c)=0.\label{normal}$
+\item\emph{Individual Rationality.} Payments for allocated experiments exceed
+costs: $p_i(c)\geq c_i\cdot s_i(c).\label{ir}$
+\item \emph{No Positive Transfers.} Payments are non-negative: $p_i(c)\geq 0\label{pt}$.
+\item \emph{Truthfulness/Incentive Compatibility.} Reporting her true cost is
+a dominant strategy for an experiment subject. Formally, let $c_{-i}$
+ be a vector of costs of all agents except $i$. Then, $p_i(c_i,c_{-i})
+ - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s_i(c_i',c_{-i})\cdot c_i,
+ \label{truthful}$ 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.} $\sum_{i\in\mathcal{N}} p_i(c) \leq
+    B.\label{budget}$
 \end{itemize}
+
 %We define the \emph{Strategic} version of \EDP{} as
 %\begin{center}
 %\textsc{StrategicExperimentalDesignProblem} (SEDP)
@@ -172,15 +170,13 @@ returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$.
 %\end{align*}
 %%\end{subequations}
 %\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
     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:
-    \begin{displaymath}
-        OPT \leq \alpha V(S).
-    \end{displaymath}
+    such that $OPT \leq \alpha V(S)$.
  %   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
@@ -614,19 +610,6 @@ TODO? Explain what are the points which are the most valuable : points which
 are aligned along directions where the spread over the already existing points
 is small.
 
-\subsection{Auction}
-
-TODO Explain the optimization problem, why it has to be formulated as an auction
-problem. Explain the goals:
-\begin{itemize}
-    \item truthful
-    \item individually rational
-    \item budget feasible
-    \item has a good approximation ratio
-
-TODO Explain what is already known: it is ok when the function is submodular. When
-should we introduce the notion of submodularity?
-\end{itemize}
 
 \end{comment}