diff options
| -rw-r--r-- | abstract.tex | 4 | ||||
| -rw-r--r-- | intro.tex | 5 | ||||
| -rw-r--r-- | paper.tex | 1 | ||||
| -rw-r--r-- | problem.tex | 2 | ||||
| -rw-r--r-- | related.tex | 18 |
5 files changed, 23 insertions, 7 deletions
diff --git a/abstract.tex b/abstract.tex index 9e00a95..5bdcc95 100644 --- a/abstract.tex +++ b/abstract.tex @@ -15,10 +15,10 @@ As a proxy for various practical constraints, \E{} may select only a subset of s %, to obtain the best estimate possible for $\beta$. We initiate the study of budgeted mechanisms for experimental design. In this setting, \E{} has a budget $B$. -Each subject $i$ declares associated cost $c_i >0$ to be part of the experiment, and must be paid at least their cost. Further, the subjects +Each subject $i$ declares an associated cost $c_i >0$ to be part of the experiment, and must be paid at least her cost. Further, the subjects are \emph{strategic} and may lie about their costs. In particular, we formulate the {\em Experimental Design Problem} (\SEDP) as finding a set $S$ of subjects for the experiment that maximizes $V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i})$ under the constraint $\sum_{i\in S}c_i\leq B$; our objective function corresponds to the information gain in parameter $\beta$ that is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. We present a deterministic, polynomial time, truthful, budget feasible mechanism for \SEDP{}. -By applying previous work on budget feasible mechanisms with submodular objective, one could have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. Our mechanism yields a constant factor ($\approx 12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation. We also show how to genralize our approach to a wide class of learning problems. +By applying previous work on budget feasible mechanisms with submodular objective, one could have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. Our mechanism yields a constant factor ($\approx{}12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation. We also show how to generalize our approach to a wide class of learning problems. @@ -29,10 +29,11 @@ However, we are not aware of a principled study of this setting from a strategic Our contributions are as follows. \begin{itemize} \item -We initiate the study of experimental design problem in presence of budgets and strategic subjects. +We initiate the study of experimental design problem in presence of a budget and strategic subjects. %formulate the problem of experimental design subject to a given budget, in the presence of strategic agents who may lie about their costs. %In particular, we focus on linear regression. This is naturally viewed as a budget feasible mechanism design problem, in which the objective function %is sophisticated and %is related to the covariance of the $x_i$'s. - In particular, we formulate the {\em Experimental Design Problem} (\SEDP) as follows: the experimenter \E\ wishes to find set $S$ of subjects to maximize + In particular, we formulate the {\em Experimental Design Problem} (\SEDP) as + follows: the experimenter \E\ wishes to find a set $S$ of subjects to maximize \begin{align}V(S) = \log\det\Big(I_d+\sum_{i\in S}x_i\T{x_i}\Big) \label{obj}\end{align} subject to a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget. When subjects are strategic, the above problem can be naturally approached as a \emph{budget feasible mechanism design} problem, as introduced by \citeN{singer-mechanisms}. %, and other {\em strategic constraints} we don't list here. @@ -43,6 +43,7 @@ S. Muthukrishnan \affil{Rutgers University, Microsoft Research}} %\input{conclusion} \bibliographystyle{acmsmall} \bibliography{notes} +\newpage \section*{Appendix} \input{appendix} \end{document} diff --git a/problem.tex b/problem.tex index 347bce7..358c825 100644 --- a/problem.tex +++ b/problem.tex @@ -108,7 +108,7 @@ $w_i$, to an experiment with $x_i^2=w_i$.% Moreover, \eqref{modified} is submodu Note that \eqref{modified} 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$, with -$V(\emptyset)=0$. Finally, it is also non-negative, \emph{i.e.}, $V(S)\geq 0$ +$V(\emptyset)=0$. Finally, it is non-negative, \emph{i.e.}, $V(S)\geq 0$ for all $S\subseteq\mathcal{N}$, since the matrix $\T{X_S}X_S$ is positive semi-definite for all $S\subseteq \mathcal{N}$. %Finally, we define the strategic version of \EDP{} (denoted by \SEDP) by adding the additional constraints of truthfulness, individual rationality, and normal payments, as described in the previous section. We denote by diff --git a/related.tex b/related.tex index 318a0e7..01d114c 100644 --- a/related.tex +++ b/related.tex @@ -8,7 +8,13 @@ Budget feasible mechanism design was originally proposed by \citeN{singer-mechanisms}. Singer 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. Singer 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 by providing a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization. -The above approximation guarantees hold \emph{in expectation}: for a given instance, the approximation ratio provided by the mechanism may in fact be unbounded. No deterministic, truthful, constant approximation mechanism that runs in polynomial time is presently known for submodular maximization. However, assuming access to an oracle providing the optimum in the full-information setup, Chen \emph{et al.},~provide a truthful, $8.34$-approximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, 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}. +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 +unbounded. No deterministic, truthful, constant approximation mechanism that +runs in polynomial time is presently known for submodular maximization. +However, 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 the one we consider here, 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}. \subsection{Budget Feasible Mechanism Design on Specific Problems} @@ -29,7 +35,15 @@ A different set of papers \cite{ghosh-roth:privacy-auction,roth-liggett,pranav} % also falls under the unverified database setting \cite{xiao:privacy-truthfulness}. In the \emph{verified} database setting, \citeN{ghosh-roth:privacy-auction} and~\citeN{pranav} consider budgeted auctions where users have a utility again captured by differential privacy. Our work departs from the above setups in that utilities do not involve privacy, whose effects are assumed to be internalized in the costs reported by the users; crucially, we also assume that experiments are tamper-proof, and individuals can misreport their costs but not their values. \sloppy -Our work is closest to the survey setup of~\citeN{roth-schoenebeck}, who also consider how to sample individuals with different features who report a hidden value at a certain cost. The authors assume a joint distribution between costs $c_i$ and features $x_i$, and wish to obtain an unbiased estimate of the expectation of the hidden value over the population, under the constraints of truthfulness, budget feasibility and individual rationality. Our work departs by learning a more general statistic (a linear model) rather than data means. We note that, as in \cite{roth-schoenebeck}, costs $c_i$ and features $x_i$ can be arbitrarily correlated in our work-the experimenter's objective \eqref{obj} does not depend on their joint distribution. +Our work is closest to the survey setup of~\citeN{roth-schoenebeck}, who also +consider how to sample individuals with different features who report a hidden +value at a certain cost. The authors assume a joint distribution between costs +$c_i$ and features $x_i$, and wish to obtain an unbiased estimate of the +expectation of the hidden value over the population, under the constraints of +truthfulness, budget feasibility and individual rationality. Our work departs +by learning a more general statistic (a linear model) rather than data means. +We note that, as in \cite{roth-schoenebeck}, costs $c_i$ and features $x_i$ can +be arbitrarily correlated in our work---the experimenter's objective \eqref{obj} does not depend on their joint distribution. \fussy |