path: root/appendix.tex

\section{Properties of the Value Function $V$} \label{app:properties}
For the sake of concreteness, we prove below the positivity, monotonicity, and submodularity of $V(S) = \log\det(I_d+X_S^TX_S)$ from basic principles. We note however that these properties hold more generally for the information gain under a wider class of models than the linear model with Gaussian noise and prior that we study here: we discuss this in more detail in Appendix~\ref{sec:ext}.

For two symmetric matrices $A$ and $B$, we write $A\succ B$ ($A\succeq B$) if
$A-B$ is positive definite (positive semi-definite).  This order allows us to
define the notion of a \emph{decreasing} as well as  \emph{convex} matrix
function, similarly to their real counterparts. With this definition, matrix
inversion is decreasing and convex over symmetric positive definite
matrices (see Example 3.48 p. 110 in \cite{boyd2004convex}).

Recall that the determinant of a matrix equals the product of its eigenvalues. The positivity of $V(S)$ follows from the fact that $X_S^TX_S$ is positive semi-definite and, as such $I_d+X_S^TX_S\succeq I_d$, so all its eigenvalues are larger than or equal to one, and they are all one if $S=\emptyset$. The marginal contribution of item $i\in\mathcal{N}$ to set
    $S\subseteq \mathcal{N}$ can be written as 
\begin{align}
V(S\cup \{i\}) - V(S)& =   \frac{1}{2}\log\det(I_d 
    + \T{X_S}X_S + x_i\T{x_i})
    - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\nonumber\\
    &  = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d +
\T{X_S}X_S)^{-1})\nonumber\\
&= \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)\label{eq:marginal_contrib}
\end{align}
where $A(S) \defeq I_d+ \T{X_S}X_S$, and the last equality follows from the
Sylvester's determinant identity~\cite{sylvester}. Monotonicity therefore follows from the fact that $A(S)^{-1}$ is positive semidefinite. Finally, since the inverse is decreasing over positive definite matrices, we have
\begin{gather}
        \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \succeq A(S\cup\{i\})^{-1}. \label{eq:inverse}
\end{gather}
and submodularity also follows, as a function is submodular if and only if the marginal contributions are non-increasing in $S$. \qed


%\begin{proof}
%\end{proof}

%We now prove that $F$ admits the following exchange property: let $\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one fractional component of $\lambda$ for another until one of them becomes integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n \lambda_i c_i \leq B$.  This rounding property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or $\varepsilon$-convexity by \citeN{pipage}.

%\begin{lemma}[Rounding]\label{lemma:rounding}
%    For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible
%    $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is
%    fractional %, that is, lies in $(0,1)$ and:
%     and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$.
%\end{lemma}
%\begin{proof}
%\end{proof}

%The $\log\det$ function is concave and self-concordant (see
%\cite{boyd2004convex}), in this case, the analysis of the barrier method in
%in \cite{boyd2004convex} (Section 11.5.5) can be summarized in the following
%lemma:

%\begin{lemma}\label{lemma:barrier}
%For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate
%approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$.
%\end{lemma}
%Note, that the feasible set in Problem~\eqref{eq:primal} increases (for the
%inclusion) when the cost decreases. 
%non-increasing.

%Furthermore, \eqref{eq:primal} being a convex optimization problem, using
%standard convex optimization algorithms (Lemma~\ref{lemma:barrier} gives
%a formal statement for our specific problem) we can compute
%a $\varepsilon$-accurate approximation of its optimal value as defined below.

%\begin{definition}
%$a$ is an $\varepsilon$-accurate approximation of $b$ iff $|a-b|\leq \varepsilon$.
%\end{definition}

%Note however that an $\varepsilon$-accurate approximation of a non-increasing
%function is not in general non-increasing itself. The goal of this section is
%to approximate $L^*_c$ while preserving monotonicity. The estimator we
%construct has a weaker form of monotonicity that we call
%\emph{$\delta$-monotonicity}.

%\begin{definition}
%Let $f$ be a function from $\reals^n$ to $\reals$, we say that $f$ is
%\emph{$\delta$-increasing along the $i$-th coordinate} iff:
%\begin{equation}\label{eq:dd}
%    \forall x\in\reals^n,\;
%    \forall \mu\geq\delta,\;
%    f(x+\mu e_i)\geq f(x)
%\end{equation}
%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. By extension,
%$f$ is $\delta$-increasing iff it is $\delta$-increasing along all coordinates.

%We define \emph{$\delta$-decreasing} functions by reversing the inequality in
%\eqref{eq:dd}.
%\end{definition}

%We consider a perturbation of \eqref{eq:primal} by introducing:
%\begin{equation}\tag{$P_{c, \alpha}$}\label{eq:perturbed-primal}
%    L^*_{c,\alpha} \defeq \max_{\lambda\in[\alpha, 1]^{n}}
%    \left\{L(\lambda) \Big| \sum_{i=1}^{n} \lambda_i c_i
%    \leq B\right\}
%\end{equation}
%Note that we have $L^*_c = L^*_c(0)$.  We will also assume that
%$\alpha<\frac{1}{nB}$ so that \eqref{eq:perturbed-primal} has at least one
%feasible point: $(\frac{1}{nB},\ldots,\frac{1}{nB})$. By computing
%an approximation of $L^*_{c,\alpha}$ as in Algorithm~\ref{alg:monotone}, we
%obtain a $\delta$-decreasing approximation of $L^*_c$.

\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} 
$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$ 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{$(\alpha,\beta)$-approximation.} 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$ and $\beta>0$
    such that $OPT \leq \alpha V(S(p))+\beta$, 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}

%
%Instead, \citeN{singer-mechanisms} and \citeN{chen}
%suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
%following properties:
%\begin{itemize}
%    \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported cost and must
%    be decreasing with respect to the costs. This is to ensure the monotonicity
%    of the allocation function.
%    \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded
%    approximation ratio.
%    \item $OPT'_{-i^*}$ must be computable in polynomial time.
%\end{itemize}
%
%One of the main technical contributions of \citeN{chen} and
%\citeN{singer-influence} is to come up with appropriate such quantity by
%considering relaxations of \textsc{Knapsack} and \textsc{Coverage},
%respectively.
%
%\subsection{Our Approach}
%
%Using the results from Section~\ref{sec:approximation}, we come up with
%a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being
%$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
%defined below.
%
%\begin{definition}
%Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator
%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
%$\delta$-truthful iff:
%\begin{displaymath}
%\forall c\in\reals_+^n,\;
%\forall\mu\;\text{with}\; |\mu|\geq\delta,\;
%\forall i\in\{1,\ldots,n\},\;
%p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
%\end{displaymath}
%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
%\end{definition}
%
%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
%by more than $\delta$ about their reported costs. In practical applications,
%the bids being discretized, if $\delta$ is smaller than the discretization
%step, the mechanism will be truthful in effect.

%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following
%variant of Myerson's theorem.