1 files changed, 10 insertions, 68 deletions
diff --git a/problem.tex b/problem.tex
index c3c7c09..6c717af 100644
--- a/problem.tex
+++ b/problem.tex
@@ -142,75 +142,17 @@ yields an approximation ratio  of $\frac{5 e }{e-1}~$\cite{singer-mechanisms}; t
 
  \subsection{Budget-Feasible Experimental Design: Strategic Case}
 We study the following \emph{strategic} setting, in which the costs $c_i$ are {\em not} common knowledge and their reporting can be manipulated by the experiment subjects. The latter are strategic and wish to maximize their utility, which is the difference of the payment they receive and their true cost. We note that, though subjects may misreport $c_i$, they cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement).
-%The subjects report $c_i$ in order to maximize their expected {\em utility} which is $p_i-c_i$.
+In this setting,  experimental design reduces to a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}; we review the formal definition  in Appendix~\ref{app:budgetfeasible}. In short, given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{reverse auction mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function}\footnote{Note that $S$ would be more aptly termed as a \emph{selection} function, as this is a reverse auction, but we retain the term ``allocation'' to align with the familiar term from standard auctions.}
+$S:\reals_+^n \to 2^\mathcal{N}$,  determining the set 
+ of experiments to be purchased, and (b) a \emph{payment function}
+$p:\reals_+^n\to \reals_+^n$, determining the payments $[p_i(c)]_{i\in \mathcal{N}}$ received by experiment subjects.
+  
+We seek mechanisms that are \emph{normalized} (unallocated experiments receive zero payments), \emph{individually rational} (payments for allocated experiments exceed costs), have \emph{no positive transfers} (payments are non-negative), and are \emph{budget feasible} (the sum of payments does not exceed the budget $B$). 
+We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring that reporting one's true cost is an \emph{almost-dominant} strategy: no subject increases their payoff by reporting a cost that differs more than $\delta$ from their true cost. Under this definition, a mechanism is truthful if $\delta=0$. 
+In addition, we would like the allocation $S(c)$ to be of maximal value; however, $\delta$-truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with that yield a \emph{constant approximation ratio}, \emph{i.e.}, there exists $\alpha\geq 1$ s.t.~$OPT \leq \alpha V(S(c))$, and are \emph{computationally efficient}, in that the allocation and payment functions can be computed in polynomial time.
 
-
-  %comprises a set of items $\mathcal{N}=\{1,\ldots,n\}$ as well as a single buyer. Each item has a cost $c_i\in\reals_+$. Moreover, the buyer has a positive value function  $V:2^{\mathcal{N}}\to \reals_+$, as well as a budget $B\in \reals_+$. In the \emph{full information case}, the costs $c_i$ are common
-%knowledge; the objective of the buyer in this context is to select 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 = \max_{S\subseteq\mathcal{N}} \Big\{V(S) \;\Big| \;
-%    \sum_{i\in S}c_i\leq B\Big\}
-%\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 this case, the costs $c_i$ are not common knowledge and their reporting can be manipulated by the experiment subjects.
-% Moreover, though a subject may lie about her true cost $c_i$, she cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement).
-
-
-
-
-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}\footnote{Note that $S$ would be more aptly termed as a \emph{selection} function, as this is a reverse auction, but we retain the term ``allocation'' to align with the familiar term from standard auctions.}
-$S:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function}
-$p:\reals_+^n\to \reals_+^n$. Given the
-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)$. We seek mechanisms that have the following properties \cite{singer-mechanisms}:
-\begin{itemize}
-\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{$\delta$-Truthfulness.} Reporting one's true cost is
-an \emph{almost-dominant} \cite{schummer2004almost} strategy. 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})$ such that $|c_i-c_i'|>\delta.$ The mechanism is \emph{truthful} if $\delta=0$.
- \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)
-%%\begin{subequations}
-%\begin{align*}
-%\text{Maximize:}&\quad V(S) = \log\det(I_d+\T{X_{S}}X_{S}) \\ %\label{modified} \\
-%\text{subject to:}&\quad \mathcal{M}=(S,p)\text{ satisfies }\eqref{normal}-\eqref{budget}   
-%\end{align*}
-%%\end{subequations}
-%\end{center}
-
-Ideally, we would like the allocation $S$ to be of maximal value; however, truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with 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 $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
-    should be computable in time polynomial in various parameters. 
-    %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}
-%\emph{W.l.o.g.}, we assume in the sequel that costs are at most $B$, \emph{i.e.}, $c_i\in[0,B]$, for all $i\in \mathcal{N}$. This is because, by individual rationality,  any $i$ for which $c_i>B$ clearly cannot be allocated; as such, any mechanism that satisfies the above properties ignores such subjects.
-
-Note that the algorithm given in \eqref{eq:max-algorithm} cannot be used in the
-strategic case. Indeed, it is known that using the MAX operator breaks
-truthfulness in general. A counterexample for the specific value function $V$
-defined in \eqref{obj} is provided in Appendix~\ref{sec:non-monotonicity}.
+We note that the $\max$ operator in  the greedy algorithm \eqref{eq:max-algorithm} breaks
+truthfulness. Though this is not true for all submodular functions (see, \emph{e.g.}, \cite{singer-mechanisms}), it is true for the objective of \EDP{}: we show this in Appendix~\ref{sec:non-monotonicity}. This motivates our study of more complex mechanisms.
 
 \begin{comment}
 As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are  \emph{single parameter} auctions: each agent has only one