diff options
| -rwxr-xr-x | appendix.tex | 49 | ||||
| -rwxr-xr-x | approximation.tex | 31 | ||||
| -rwxr-xr-x | conclusion.tex | 2 | ||||
| -rwxr-xr-x | intro.tex | 2 | ||||
| -rwxr-xr-x | main.tex | 38 | ||||
| -rwxr-xr-x | notes.bib | 10 | ||||
| -rwxr-xr-x | paper.tex | 1 | ||||
| -rwxr-xr-x | problem.tex | 8 | ||||
| -rwxr-xr-x | related.tex | 33 |
9 files changed, 96 insertions, 78 deletions
diff --git a/appendix.tex b/appendix.tex index 6926e00..63a8dd8 100755 --- a/appendix.tex +++ b/appendix.tex @@ -264,14 +264,7 @@ Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed %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} -We begin by a description of Algorithm~\ref{alg:monotone} which computes an approximation of $L^*_c$, which is arbitrarily accurate \emph{and} $\delta$-decreasing. We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let $$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq \dom_c . $$ -Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concave relaxation \eqref{eq:primal}: -\begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal} -\begin{split} \text{Maximize:} &\qquad L(\lambda)\\ -\text{subject to:} & \qquad\lambda \in \dom_{c,\alpha} -\end{split} -\end{align} - +We begin by a description of Algorithm~\ref{alg:monotone} which computes an approximation of $L^*_c$, which is arbitrarily accurate \emph{and} $\delta$-decreasing. %Note, that the feasible set in Problem~\eqref{eq:primal} increases (for the %inclusion) when the cost decreases. %non-increasing. @@ -594,31 +587,6 @@ Formally, there must exist some $\alpha\geq 1$ and $\beta>0$ \section{Description of our mechanism for \EDP{} and proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} -We begin by a description of the methodology used to construct our mechanism. -Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in -\mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set -constructed greedily, by selecting elements of maximum marginal value per cost. -The general framework used by \citeN{chen} and by \citeN{singer-influence} for -the \textsc{Knapsack} and \textsc{Coverage} value functions contructs an -allocation as follows. First, a polynomial-time, monotone approximation of -$OPT$ is computed over all elements excluding $i^*$. The outcome of this -approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the -mechanism constructs an allocation $S_G$ greedily; otherwise, the only item -allocated is the singleton $\{i^*\}$. Provided that the approximation used is -within a constant from $OPT$, the above allocation can be shown to also yield -a constant approximation to $OPT$. Furthermore, using Myerson's -Theorem~\cite{myerson}, it can be shown that this allocation combined with -\emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below) -constitute a truthful mechanism. - -The approximation algorithms used in \cite{chen,singer-influence} are LP -relaxations, and thus their outputs are monotone and can be computed exactly in -polynomial time. We show that the convex relaxation \eqref{eq:primal}, which -can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be -used to construct a $\delta$-truthful, constant approximation mechanism, by -being incorporated in the same framework. - -To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in Appendix~\ref{sec:myerson}. % %Instead, \citeN{singer-mechanisms} and \citeN{chen} %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the @@ -665,17 +633,6 @@ To obtain this result, we use the following modified version of Myerson's theore %$\delta$-truthfulness will follow from $\delta$-monotonicity by the following %variant of Myerson's theorem. -\begin{lemma}\label{thm:myerson-variant} - A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is -$\delta$-truthful if: -(a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq -c_i-\delta$, for any -fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i, -c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) - agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$. -\end{lemma} -Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the -above framework, yielding Theorem~\ref{thm:main}. \begin{algorithm}[!t] \caption{Mechanism for \SEDP{}}\label{mechanism} @@ -706,11 +663,11 @@ above framework, yielding Theorem~\ref{thm:main}. \end{algorithm} -We now present the proof of Theorem~\ref{thm:main}. +We present here the proof of Theorem~\ref{thm:main}. Our mechanism for \EDP{} is composed of (a) the allocation function presented in Algorithm~\ref{mechanism}, and (b) the payment function which pays each allocated agent $i$ her threshold -payment as described in Myerson's Theorem. In the case where $\{i^*\}$ is the +payment as described in Myerson's Theorem (see Lemma~\ref{thm:myerson-variant}). In the case where $\{i^*\}$ is the allocated set, her threshold payment is $B$. %(she would be have been dropped on %line 1 of Algorithm~\ref{mechanism} had she reported a higher cost). A closed-form formula for threshold payments when $S_G$ is the allocated set can diff --git a/approximation.tex b/approximation.tex index dc39e5b..2747d5a 100755 --- a/approximation.tex +++ b/approximation.tex @@ -73,7 +73,7 @@ For all $\lambda\in[0,1]^{n},$ \,L(\lambda)\leq F(\lambda)\leq L(\lambda)$. \end{lemma} -The proof of this lemma can be found in Appendix~\ref{proofofrelaxation-ratio}. In short, exploiting the concavity of the $\log\det$ function over the set of positive semi-definite matrices, we first bound the ratio of all partial derivatives of $F$ and $L$. We then show that the bound on the ratio of the derivatives also implies a bound on the ratio $F/L$. +The proof of this lemma can be found in \cite{arxiv}. In short, exploiting the concavity of the $\log\det$ function over the set of positive semi-definite matrices, we first bound the ratio of all partial derivatives of $F$ and $L$. We then show that the bound on the ratio of the derivatives also implies a bound on the ratio $F/L$. Armed with this result, we subsequently use pipage rounding to show that any $\lambda$ that maximizes the multi-linear extension $F$ can be rounded to an ``almost'' integral solution. More specifically, given a set of costs $c\in \reals^n_+$, we say that a $\lambda\in [0,1]^n$ is feasible if it belongs to the set $\dom_c =\{\lambda \in [0,1]^n: \sum_{i\in \mathcal{N}} c_i\lambda_i\leq B\}$. Then, the following lemma holds: @@ -82,7 +82,7 @@ Armed with this result, we subsequently use pipage rounding to show that any $\ $\bar{\lambda}\in \dom_c$ such that (a) $F(\lambda)\leq F(\bar{\lambda})$, and (b) at most one of the coordinates of $\bar{\lambda}$ is fractional. %, that is, lies in $(0,1)$ and: \end{lemma} -The proof of this lemma is in Appendix \ref{proofoflemmarounding}, and follows the main steps of the pipage rounding method of \citeN{pipage}. % 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}. +The proof of this lemma is in \cite{arxiv}, and follows the main steps of the pipage rounding method of \citeN{pipage}. % 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}. Together, Lemma~\ref{lemma:relaxation-ratio} and Lemma~\ref{lemma:rounding} imply that $OPT$, the optimal value of \EDP, can be approximated by solving the following convex optimization problem: \begin{align}\tag{$P_c$}\label{eq:primal} \text{Maximize:} \quad L(\lambda)\quad \text{subject to:} \quad\lambda \in \dom_c @@ -91,7 +91,7 @@ In particular, for $L_c^*\defeq \max_{\lambda\in \dom_c} L(\lambda)$, the follow \begin{proposition}\label{prop:relaxation} $OPT\leq L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$. \end{proposition} -The proof of this proposition can be found in Appendix~\ref{proofofproprelaxation}. As we discuss in the next section, $L^*_c$ can be computed by a poly-time algorithm at arbitrary accuracy. However, the outcome of this computation may not necessarily be monotone; we address this by converting this poly-time estimator of $L^*_c$ to one that is ``almost'' monotone.%The optimization program \eqref{eq:non-strategic} extends naturally to such +The proof of this proposition can be found in \cite{arxiv}. As we discuss in the next section, $L^*_c$ can be computed by a poly-time algorithm at arbitrary accuracy. However, the outcome of this computation may not necessarily be monotone; we address this by converting this poly-time estimator of $L^*_c$ to one that is ``almost'' monotone.%The optimization program \eqref{eq:non-strategic} extends naturally to such %a relaxation. We define: %\begin{equation}\tag{$P_c$}\label{eq:primal} % L^*_c \defeq \max_{\lambda\in[0, 1]^{n}} @@ -123,12 +123,25 @@ Nevertheless, we prove that it is possible to use the barrier method to construc for all $i\in \mathcal{N},x\in\reals^n, \mu\geq\delta,$ %\end{equation} where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. -In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\delta$ or more at input $x$ ensures that the output will be at most $f(x)$. The following holds: +In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\delta$ or more at input $x$ ensures that the output will be at most $f(x)$. + +%Our next technical result establishes that, using the barrier method, it is possible to construct an algorithm that computes $L^*_c$ at arbitrary accuracy in polynomial time and is $\delta$-decreasing. + +We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let +$$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq \dom_c . $$ +Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concave relaxation \eqref{eq:primal}: +\begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal} +\begin{split} \text{Maximize:} &\qquad L(\lambda)\\ +\text{subject to:} & \qquad\lambda \in \dom_{c,\alpha} +\end{split} +\end{align} \begin{proposition}\label{prop:monotonicity} - For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$, - there exists an algorithm which computes a $\delta$-decreasing, - $\varepsilon$-accurate approximation of $L^*_c$. The running time of the - algorithm is $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$. + For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$, using the barrier + method to solve \eqref{eq:perturbed-primal} for $\alpha\defeq\varepsilon + (\delta/B+n^2)^{-1}$ with accuracy $\frac{1}{2^{n+1}B}\alpha\delta b$ + yields a $\delta$-decreasing, $\varepsilon$-accurate approximation of + $L^*_c$. The running time of the algorithm is $O\big(poly(n, d, + \log\log\frac{B}{b\varepsilon\delta})\big)$. \end{proposition} -The proof and the algorithm (Algorithm~\ref{alg:monotone}) are in Appendix~\ref{proofofpropmonotonicity}. +The proof and the formal description of the algorithm are in \cite{arxiv}. diff --git a/conclusion.tex b/conclusion.tex index 6b17237..4db1030 100755 --- a/conclusion.tex +++ b/conclusion.tex @@ -5,7 +5,7 @@ polynomial time. %Our objective function, commonly known as the Bayes $D$-optima A natural question to ask is to what extent ou results %we present here generalize to other machine learning tasks beyond linear regression. We outline -a path to such a generalization in Appendix~\ref{sec:ext}: %. In +a path to such a generalization in \cite{arxiv}: %. In %particular, although the information gain is not generally a submodular %function, we show that for a wide class of models in which experiment @@ -61,7 +61,7 @@ Our convex relaxation of \EDP{} involves maximizing a self-concordant function s %Our approach to mechanisms for experimental design --- by % optimizing the information gain in parameters like $\beta$ which are estimated through the data analysis process --- is general. We give examples of this approach beyond linear regression to a general class that includes logistic regression and learning binary functions, and show that the corresponding budgeted mechanism design problem is also expressed through a submodular optimization. Hence, prior work \cite{chen,singer-mechanisms} immediately applies, and gives randomized, universally truthful, polynomial time, constant factor approximation mechanisms for problems in this class. Getting deterministic, truthful, polynomial time mechanisms with a constant approximation factor for this class or specific problems in it, like we did for \EDP, remains an open problem. -In what follows, we describe related work in Section~\ref{sec:related}. We briefly review experimental design and budget feasible mechanisms in Section~\ref{sec:peel} and define \SEDP\ formally. We present our convex relaxation to \EDP{} in Section~\ref{sec:approximation} and use it to construct our mechanism in Section~\ref{sec:main}. We conclude in Section~\ref{sec:concl}. All proofs of our technical results are provided in the appendix. %we present our mechanism for \SEDP\ and state our main results. %A generalization of our framework to machine learning tasks beyond linear regression is presented in Section~\ref{sec:ext}. +In what follows, we describe related work in Section~\ref{sec:related}. We briefly review experimental design and budget feasible mechanisms in Section~\ref{sec:peel} and define \SEDP\ formally. We present our convex relaxation to \EDP{} in Section~\ref{sec:approximation} and use it to construct our mechanism in Section~\ref{sec:main}. We conclude in Section~\ref{sec:concl}. All proofs of our technical results are provided in the full version of this paper \cite{arxiv}. %we present our mechanism for \SEDP\ and state our main results. %A generalization of our framework to machine learning tasks beyond linear regression is presented in Section~\ref{sec:ext}. \junk{ @@ -2,6 +2,42 @@ The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} can be used to design a mechanism for \SEDP. The construction follows a methodology proposed in \cite{singer-mechanisms} and employed by \citeN{chen} and \citeN{singer-influence} to construct \junk{deterministic, truthful} mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. The following theorem summarizes the properties of our merchanism. +Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in +\mathcal{N}} V(\{i\})$ is the element of maximum value, and $S_G$ is a set +constructed greedily, by selecting elements of maximum marginal value per cost. +The general framework used by \citeN{chen} and by \citeN{singer-influence} for +the \textsc{Knapsack} and \textsc{Coverage} value functions contructs an +allocation as follows. First, a polynomial-time, monotone approximation of +$OPT$ is computed over all elements excluding $i^*$. The outcome of this +approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the +mechanism constructs an allocation $S_G$ greedily; otherwise, the only item +allocated is the singleton $\{i^*\}$. Provided that the approximation used is +within a constant from $OPT$, the above allocation can be shown to also yield +a constant approximation to $OPT$. Furthermore, using Myerson's +Theorem~\cite{myerson}, it can be shown that this allocation combined with +\emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below) +constitute a truthful mechanism. + +The approximation algorithms used in \cite{chen,singer-influence} are LP +relaxations, and thus their outputs are monotone and can be computed exactly in +polynomial time. We show that the convex relaxation \eqref{eq:primal}, which +can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be +used to construct a $\delta$-truthful, constant approximation mechanism, by +being incorporated in the same framework. + +To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in \cite{arxiv}. + +\begin{lemma}\label{thm:myerson-variant} + A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is +$\delta$-truthful if: +(a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq +c_i-\delta$, for any +fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i, +c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) + agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$. +\end{lemma} +Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the +above framework, yielding the following theorem: %In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive compatibility. Indeed, \citeN{singer-influence} notes that this allocation function is not monotone, which implies by Myerson's theorem (Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful. @@ -20,7 +56,7 @@ The $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimi Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. \end{theorem} -The detailed description of our proposed mechanism (Algorithm~\ref{mechanism}), as well as the proof of the theorem can be found in Appendix~\ref{sec:proofofmainthm}. +The detailed description of our proposed mechanism as well as the proof of the theorem can be found in \cite{arxiv}. @@ -706,3 +706,13 @@ author = "Alkiviadis G. Akritas and Evgenia K. Akritas and Genadii I. Malaschono year = {2004}, pages = {129–150}, } + +@article{arxiv, + author = {Thibaut Horel and + Stratis Ioannidis and + S. Muthukrishnan}, + title = {Budget Feasible Mechanisms for Experimental Design}, + year = {2013}, + note = {\url{http://arxiv.org/abs/1302.5724}}, +} + @@ -29,7 +29,6 @@ \section{Introduction} \input{intro} - \section{Preliminaries}\label{sec:peel} \input{problem} \section{Approximation Results}\label{sec:approximation} diff --git a/problem.tex b/problem.tex index 0e9c75f..46e72c5 100755 --- a/problem.tex +++ b/problem.tex @@ -91,7 +91,7 @@ d}.$ Intuitively, this corresponds to the simplest prior, in which no direction of $\reals^d$ is a priori favored; equivalently, it also corresponds to the case where ridge regression estimation \eqref{ridge} performed by $\E$ has a penalty term $\norm{\beta}_2^2$. A generalization of our results to arbitrary -covariance matrices $R$ can be found in Appendix~\ref{sec:ext}. +covariance matrices $R$ can be found in \cite{arxiv}. %Note that \eqref{dcrit} is a submodular set function, \emph{i.e.}, %$V(S)+V(T)\geq V(S\cup T)+V(S\cap T)$ for all $S,T\subseteq \mathcal{N}$; it is also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subset T$. @@ -118,7 +118,7 @@ the optimal value achievable in the full-information case. reduces to EDP with $d=1$ by mapping the weight of each item, say, $w_i$, to an experiment with $x_i^2=w_i$.% Moreover, \eqref{modified} is submodular, monotone and satisfies $V(\emptyset) = 0$. -The value function \eqref{modified} has the following properties, which are proved in Appendix~\ref{app:properties}. First, it is non-negative, \emph{i.e.}, $V(S)\geq 0$ +The value function \eqref{modified} has the following properties, which are proved in \cite{arxiv}. First, it is non-negative, \emph{i.e.}, $V(S)\geq 0$ for all $S\subseteq\mathcal{N}$. Second, it is also monotone, \emph{i.e.}, $V(S)\leq V(T)$ for all $S\subseteq T$, with $V(\emptyset)=0$. Finally, it is submodular, \emph{i.e.}, @@ -150,7 +150,7 @@ 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. 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). -Experimental design thus 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} $S:\reals_+^n \to 2^\mathcal{N}$, determining the set +Experimental design thus reduces to a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}; we review the formal definition in \cite{arxiv}. 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} $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. @@ -159,7 +159,7 @@ We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring t 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 are \emph{$(\alpha,\beta)$-approximate}, \emph{i.e.}, there exist $\alpha\geq 1$ and $\beta>0$ s.t.~$OPT \leq \alpha V(S(c))+\beta$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time. We note that the constant approximation 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. +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 \cite{arxiv}. 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 diff --git a/related.tex b/related.tex index 19b245b..a78693b 100755 --- a/related.tex +++ b/related.tex @@ -5,31 +5,29 @@ } \noindent\emph{Budget Feasible Mechanisms for General Submodular Functions.} Budget feasible mechanism design was originally proposed by \citeN{singer-mechanisms}, who considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model. %, \emph{i.e.} assuming an oracle providing the value of the submodular objective on any given set. -He shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen} improve this result to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization. +He shows that there exists a randomized, 112-approximation mechanism that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen} improve this result to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms. The above approximation guarantees hold for the expected value of the randomized mechanism: for a given -instance, the approximation ratio provided by the mechanism may in fact be +instance, the approximation ratio provided by the mechanism may be unbounded. No deterministic, truthful, constant approximation mechanism that runs in polynomial time is presently known for submodular maximization. Assuming access to an oracle providing the optimum in the -full-information setup, Chen \emph{et al.}~propose a truthful, $8.34$-approximate mechanism; in cases for which the full information problem is NP-hard, as \EDP, this mechanism is not poly-time, unless P=NP. Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. - +full-information setup, Chen \emph{et al.}~propose a truthful, $8.34$-approximate mechanism; in cases for which the full-information problem is NP-hard, as \EDP, this mechanism is not poly-time, unless P=NP. Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. \noindent\emph{Budget Feasible Mechanism Design on Specific Problems.} -Improved bounds \emph{and} deterministic polynomial mechanisms are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}. - +Improved uper and lower bounds \emph{and} deterministic polynomial mechanisms are known for specific submodular objectives \cite{singer-mechanisms, chen, singer-influence}. +\junk{For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}.} The deterministic mechanisms for \textsc{Knapsack} \cite{chen} and \textsc{Coverage} \cite{singer-influence} follow the same general framework, -which we also employ (see Appendix~\ref{sec:proofofmainthm}). In these two cases, the framework approximates the -optimal solution to the underlying combinatorial problem by a well-known linear program (LP) relaxation~\cite{pipage}, which is solved exactly in polynomial time. No +which we also employ. In these two cases, the framework approximates the +optimal solution to the underlying combinatorial problem by a linear program (LP) relaxation~\cite{pipage}. No such relaxation exists for \EDP, which is unlikely to be approximable through an LP due to its logarithmic objective. We develop instead a convex relaxation to \EDP; though, contrary to the above LP relaxations, this cannot be solved exactly, we show how to incorporate it in the framework of \cite{chen,singer-influence} to yield a $\delta$-truthful mechanism for \EDP. - %Our results therefore add \SEDP{} to the set of problems for which a deterministic, polynomial time, constant approximation mechanism is known. \noindent\emph{Beyond Submodular Objectives.} @@ -41,11 +39,14 @@ Posted price, rather than direct revelation mechanisms, are also studied in \cit \noindent\emph{Monotone Approximations in Combinatorial Auctions.} Relaxations of combinatorial problems are prevalent -in \emph{combinatorial auctions}, % \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}, -in which an auctioneer aims at maximizing a set function which is the sum of utilities of strategic bidders (\emph{i.e.}, the social welfare). As noted by \citeN{archer-approximate}, -approximations to this maximization must preserve incentive compatibility and truthfulness. Most approximation -algorithms do not preserve these properties, hence specific relaxations, and corresponding roundings to an integral solution, must be -constructed. \citeN{archer-approximate} propose a randomized rounding of the LP relaxation of the \textsc{SetPacking} problem, yielding a mechanism +in \emph{combinatorial auctions}, +in which an auctioneer aims at maximizing the social welfare..e.}. As noted by \citeN{archer-approximate}, +approximations to this maximization must preserve incentive compatibility. Most approximation +algorithms do not preserve this property, hence specific relaxations, and corresponding roundings to an integral solution, must be +constructed \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}. Because of the specificity of our relaxation, and because we seek a determinist mechanism and $\delta$-truthfulness, not truthfulness-in-expectation, none of the techniques present in these works apply to our setting. + + +\junk{\citeN{archer-approximate} propose a randomized rounding of the LP relaxation of the \textsc{SetPacking} problem, yielding a mechanism which is \emph{truthful-in-expectation}. %and in high probability. \citeN{lavi-truthful} construct randomized truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation @@ -57,7 +58,9 @@ the bidders' utilities are matroid rank sum functions (applied earlier to the \t on solving a convex optimization problem which can only be solved approximately. As in \cite{lavi-truthful}, they also treat the fractional solution as a distribution over which they sample integral solutions. The authors ensure that a solver is applied to a ``well-conditioned'' problem, which resembles the technical challenge we face in Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation. In addition, our objective is not a matroid rank sum function. As such, both the methodology for dealing with problems that are not ``well-conditioned'' as well as the approximation guarantees of the convex relaxation in \cite{dughmi2011convex} do not readily extend to \EDP. -\citeN{briest-approximation} construct monotone FPTAS for problems that can be approximated through rounding techniques, which in turn can be used to construct truthful, deterministic, constant-approximation mechanisms for corresponding combinatorial auctions. \EDP{} is not readily approximable through such rounding techniques; as such, we rely on a relaxation to approximate it. +\citeN{briest-approximation} construct monotone FPTAS for problems that can be approximated through rounding techniques, which in turn can be used to construct truthful, deterministic, constant-approximation mechanisms for corresponding combinatorial auctions.} + +%\EDP{} is not readily approximable through such rounding techniques; as such, we rely on a relaxation to approximate it. \noindent\emph{$\delta$-Truthfulness and Differential Privacy.} The notion of $\delta$-truthfulness has attracted considerable attention recently in the context of differential privacy (see, \emph{e.g.}, the survey by \citeN{pai2013privacy}). \citeN{mcsherrytalwar} were the first to observe that any $\epsilon$-differentially private mechanism must also be $\delta$-truthful in expectation, for $\delta=2\epsilon$. This property was used to construct $\delta$-truthful (in expectation) mechanisms for a digital goods auction~\cite{mcsherrytalwar} and for $\alpha$-approximate equilibrium selection \cite{kearns2012}. \citeN{approximatemechanismdesign} propose a framework for converting a differentially private mechanism to a truthful-in-expectation mechanism by randomly selecting between a differentially private mechanism with good approximation guarantees, and a truthful mechanism. They apply their framework to the \textsc{FacilityLocation} problem. We depart from the above works in seeking a deterministic mechanism for \EDP, and using a stronger notion of $\delta$-truthfulness. |