diff options
| -rw-r--r-- | approximation.tex | 2 | ||||
| -rw-r--r-- | intro.tex | 6 | ||||
| -rw-r--r-- | paper.tex | 2 | ||||
| -rw-r--r-- | problem.tex | 12 | ||||
| -rw-r--r-- | related.tex | 12 |
5 files changed, 14 insertions, 20 deletions
diff --git a/approximation.tex b/approximation.tex index 6cc9e49..b1d3453 100644 --- a/approximation.tex +++ b/approximation.tex @@ -1,7 +1,7 @@ Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any cost $c_i$ leads to an increase in the estimation of $OPT$; %In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{}, the monotonicity property precludes using traditional approximation algorithms. -In the fist part of this section, we address this issue by designing a convex relaxation of \EDP{}, and showing that its solution can be used to approximate $OPT$. The objective of this relaxation is concave and self-concordant \cite{boyd2004convex} and, as such, there exists an algorithm that solves this relaxed problem with arbitrary accuracy in polynomial time. Unfortunately, the output of this algorithm may not necessarily be monotone. Nevertheless, in the second part of this section, we show how a solver of the relaxed problem can be used to construct a solver that is ``almost'' monotone: in Section~\ref{sec:main}, we show how this algorithm can be used to design a $\delta$-truthful mechanism for \EDP. +In the fist part of this section, we address this issue by designing a convex relaxation of \EDP{}, and showing that its solution can be used to approximate $OPT$. The objective of this relaxation is concave and self-concordant \cite{boyd2004convex} and, as such, there exists an algorithm that solves this relaxed problem with arbitrary accuracy in polynomial time. Unfortunately, the output of this algorithm may not necessarily be monotone. Nevertheless, in the second part of this section, we show that a solver of the relaxed problem can be used to construct a solver that is ``almost'' monotone. In Section~\ref{sec:main}, we show that this algorithm can be used to design a $\delta$-truthful mechanism for \EDP. %As noted above, \EDP{} is NP-hard. Designing a mechanism for this problem, as @@ -61,10 +61,10 @@ We note that the objective \eqref{obj} is submodular. Using this fact, applying %From a technical perspective, we present a convex relaxation of \eqref{obj}, and show that its optimal value is within a constant factor from the so-called multi-linear relaxation of \eqref{obj}, which in turn can be related to \eqref{obj} through pipage rounding. We establish the constant factor to the multi-linear relaxation by bounding the partial derivatives of these two functions; we achieve the latter by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices. -From a technical perspective, we propose a convex optimization problem and establish that its optimal value within a constant factor from the optimal value of \EDP. +From a technical perspective, we propose a convex optimization problem and establish that its optimal value is within a constant factor from the optimal value of \EDP. In particular, we show our relaxed objective is within a constant factor from the so-called multi-linear extension of \eqref{obj}, which in turn can be related to \eqref{obj} through pipage rounding. We establish the constant factor to the multi-linear extension by bounding the partial derivatives of these two functions; we achieve the latter by exploiting convexity properties of matrix functions over the convex cone of positive semidefinite matrices. -Our convex relaxation of \EDP{} involves maximizing a self-concordant function subject to linear constraints. Its optimal value can be computed with arbitrary accuracy in polynomial time using the so-called barrier method. However, the outcome of this computation may not necessarily be monotone, a property needed in designing a truthful mechanism. Nevetheless, we construct an algorithm that solves the above convex relaxation and is ``almost'' monotone; we achieve this by applying the barrier method on a set perturbed constraints, over which our objective is ``sufficiently'' concave. In turn, we also show that this algorithm can be employed to design a $\delta$-truthful mechanism for \EDP{}. +Our convex relaxation of \EDP{} involves maximizing a self-concordant function subject to linear constraints. Its optimal value can be computed with arbitrary accuracy in polynomial time using the so-called barrier method. However, the outcome of this computation may not necessarily be monotone, a property needed in designing a truthful mechanism. Nevetheless, we construct an algorithm that solves the above convex relaxation and is ``almost'' monotone; we achieve this by applying the barrier method on a set perturbed constraints, over which our objective is ``sufficiently'' concave. In turn, we show how to employ this algorithm to design a poly-time, $\delta$-truthful, constant-approximation mechanism for \EDP{}. %This allows us to adopt the approach followed by prior work in budget feasible mechanisms by Chen \emph{et al.}~\cite{chen} and Singer~\cite{singer-influence}. %{\bf FIX the last sentence} @@ -73,7 +73,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, finally, show how it can be used to construct our mechanism in Section~\ref{sec:main}; 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 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}. \junk{ @@ -35,7 +35,7 @@ \input{approximation} \section{Mechanism for \SEDP{}}\label{sec:mechanism} \input{main} -\section{Conclusions} +\section{Conclusions}\label{sec:concl} \input{conclusion} \bibliographystyle{abbrvnat} \bibliography{notes} diff --git a/problem.tex b/problem.tex index 1001d7b..8d5b262 100644 --- a/problem.tex +++ b/problem.tex @@ -84,13 +84,9 @@ covariance matrices $R$ can be found in Appendix~\ref{sec:ext}. \subsection{Budget-Feasible Experimental Design: Full Information Case}\label{sec:fullinfo} -Beyond the cardinality constraint in classical experimental design discussed above, a - budgeted version can also be considered. -%depart from the above classic experimental design setting by assuming that -Each experiment is associated with a cost $c_i\in\reals_+$. Moreover, the experimenter $\E$ is limited by a budget $B\in \reals_+$. -The cost $c_i$ can capture, \emph{e.g.}, the amount the subject $i$ deems sufficient to -incentivize her participation in the experiment. -In the full-information case, the experiment costs are common knowledge; as such, the optimization problem that the experimenter wishes to solve is: +Instead of the cardinality constraint in classical experimental design discussed above, we consider a budget-constrained version. +Each experiment is associated with a cost $c_i\in\reals_+$. +The cost $c_i$ can capture, \emph{e.g.}, the amount the subject $i$ deems sufficient to incentivize her participation in the experiment. The experimenter $\E$ is limited by a budget $B\in \reals_+$. In the full-information case, experiment costs are common knowledge; as such, the experimenter wishes to solve: \medskip\\\hspace*{\stretch{1}}\textsc{ExperimentalDesignProblem} (\EDP)\hspace*{\stretch{1}} \begin{subequations} \begin{align} @@ -149,7 +145,7 @@ We seek mechanisms that are \emph{normalized} (unallocated experiments receive z 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 utility by reporting a cost that differs more than $\delta>0$ 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 $S$ and $p$ can be computed in polynomial time. -We note that the $\max$ operator in the greedy algorithm \eqref{eq:max-algorithm} breaks +We note that 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} diff --git a/related.tex b/related.tex index 6cf059f..b25b91b 100644 --- a/related.tex +++ b/related.tex @@ -19,12 +19,11 @@ full-information setup, Chen \emph{et al.},~propose a truthful, $8.34$-approxima \paragraph{Budget Feasible Mechanism Design on Specific Problems} Improved bounds, as well as 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 also 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 above deterministic mechanisms for \textsc{Knapsack} \cite{chen} and +The deterministic mechanisms for \textsc{Knapsack} \cite{chen} and \textsc{Coverage} \cite{singer-influence} follow the same general framework, -which we also employ. We describe this framework in detail in +which we also employ in our mechanism for \EDP. We describe this framework in detail in Section~\ref{sec:main}. Both of these mechanisms rely on approximating the -optimal solution to the underlying combinatorial problem by a well-known LP -relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No +optimal solution to the underlying combinatorial problem by a well-known linear program (LP) relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No such relaxation exists for \EDP, whose logarithmic objective is unlikely to be approximable through an LP. We develop instead a convex relaxation to \EDP; though, contrary to the above LP relaxations, this cannot be solved exactly, we @@ -47,12 +46,11 @@ in \emph{combinatorial auctions}, % \cite{archer-approximate,lavi-truthful,dughm 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 linear -programming relaxation of the \textsc{SetPacking} problem, yielding a mechanism +constructed. \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 -ratio in \cite{archer-approximate}, by treating the fractional solution of a linear program as a probability distribution over integral solutions. +ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution over integral solutions. Beyond LP relaxations, \citeN{dughmi2011convex} propose |