compactified budg feas mechs, moved details to appendix

1 files changed, 36 insertions, 0 deletions

diff --git a/appendix.tex b/appendix.tex
index a162a4f..3c2fed8 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -479,6 +479,42 @@ Note that:
 Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed
 \end{enumerate}
 
+\section{Budget Feasible Reverse Auction Mechanisms}\label{app:budgetfeasible}
+We review in this appendix the formal definition of a budget feasible reverse auction mechanisms, as introduced by \citeN{singer-mechanisms}. We depart from the definitions in \cite{singer-mechanisms} only in considering $\delta$-truthful, rather than truthful, mechanisms.
+
+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$. 
+ 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,
+ $ 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}$
+
+
+   \item \emph{Approximation Ratio.} The value of the allocated set  should not
+    be too far from the optimum value of the full information case, as given by  \eqref{eq:non-strategic}. 
+Formally, there must exist some $\alpha\geq 1$
+    such that $OPT \leq \alpha V(S(p))$, where     $OPT = \max_{S\subseteq\mathcal{N}} \left\{V(S) \;\mid \;
+    \sum_{i\in S}c_i\leq B\right\}$.
+
+ %   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}
+
+
 \section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm}
 
 We now present the proof of Theorem~\ref{thm:main}. We use the notation $OPT_{-i^*}$ to denote the optimal value of \EDP{} when the maximum value element $i^*$ is  excluded. We also use $OPT'_{-i^*}$ the approximation computed by the $\delta$-decreasing, $\epsilon$-accurate approximation of $L^*_{c_{-i^*}}$, as defined in Algorithm~\ref{mechanism}.