diff options
| -rw-r--r-- | intro.tex | 5 | ||||
| -rw-r--r-- | notes.bib | 12 | ||||
| -rw-r--r-- | paper.tex | 3 | ||||
| -rw-r--r-- | problem.tex | 21 | ||||
| -rw-r--r-- | related.tex | 10 |
5 files changed, 31 insertions, 20 deletions
@@ -24,8 +24,13 @@ Our contributions are as follows. We formulate the problem of experimental design subject to a given budget, in presence of strategic agents who specify their costs. In particular, we focus on linear regression. This is naturally viewed as a budget feasible mechanism design problem. 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} (\EDP) as follows: the experimenter \E\ wishes to find set $S$ of subjects to maximize \begin{align}V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i}) \label{obj}\end{align} with a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget. %, and other {\em strategic constraints} we don't list here. +<<<<<<< HEAD The objective function, which is the key, is obtained by optimizing the information gain in $\beta$ when it is learned through linear regression methods, and is the so-called $D$-objective criterion in the literature. +======= + The objective function, which is the key, is motivated from the so-called $D$-optimality criterion; in particular, it captures the reduction in the entropy of $\beta$ when the latter is learned through linear regression methods. + +>>>>>>> c29302b25adf190f98019eb8ce5f79b10b66d54d \item The above objective is submodular. There are several recent results in budget feasible @@ -596,18 +596,6 @@ - -@article{approximatemechanismdesign, - author = {Kobbi Nissim and - Rann Smorodinsky and - Moshe Tennenholtz}, - title = {Approximately Optimal Mechanism Design via Differential - Privacy}, - year = {2010}, - ee = {http://arxiv.org/abs/1004.2888}, -} - - @techreport{xiao:privacy-truthfulness, author = "David Xiao", title = "Is privacy compatible with truthfulness?", @@ -9,6 +9,9 @@ \maketitle +\begin{abstract} +TODO +\end{abstract} \section{Intro} \input{intro} diff --git a/problem.tex b/problem.tex index 47991e3..a0a4419 100644 --- a/problem.tex +++ b/problem.tex @@ -55,7 +55,7 @@ B$. We write: \end{equation} for the optimal value achievable in the full-information case. %\stratis{Should be $OPT(V,c,B)$\ldots better drop the arguments here and introduce them wherever necessary.} -In the \emph{strategic case}, each items in $\mathcal{N}$ is held by a different strategic agent, whose cost is a-priori private. +In the \emph{strategic case}, each items in $\mathcal{N}$ is held by a different strategic agent, whose cost is \emph{a priori} private. A \emph{mechanism} $\mathcal{M} = (f,p)$ comprises (a) an \emph{allocation function} $f:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. Given the @@ -68,10 +68,10 @@ no positive transfers ($p_i(c)\geq 0$). In addition to the above, mechanism design in budget feasible reverse auctions seeks mechanisms that have the following properties \cite{singer-mechanisms,chen}: \begin{itemize} - \item \emph{Truthfulness.} An agent has no incentive to missreport her true cost. Formally, let $c_{-i}$ + \item \emph{Truthfulness.} An agent has no incentive to misreport her true cost. Formally, let $c_{-i}$ be a vector of costs of all agents except $i$. % $c_{-i}$ being the same). Let $[p_i']_{i\in \mathcal{N}} = p(c_i', % c_{-i})$, then the -A mechanism is truthful iff every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$ +A mechanism is truthful iff for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$ $p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s(c_i',c_{-i})\cdot c_i$. \item \emph{Budget Feasibility.} The sum of the payments should not exceed the budget constraint: @@ -108,10 +108,18 @@ c_{-i})$ implies $i\in f(c_i', c_{-i})$, and (b) %\end{enumerate} \end{lemma} \fussy +<<<<<<< HEAD Myerson's Theorem % is particularly useful when designing a budget feasible truthful mechanism, as it allows us to focus on designing a monotone allocation function. Then, the mechanism will be truthful as long as we give each agent her threshold payment---the caveat being that the latter need to sum to a value below $B$. +======= +Myerson's Theorem is particularly useful when designing a budget feasible truthful +mechanism. One can focus on designing a monotone allocation function, and the +resulting mechanism will be truthful as long as each agent is given her +threshold payment---the caveat being that the latter need to sum to a value +below $B$. +>>>>>>> c29302b25adf190f98019eb8ce5f79b10b66d54d \subsection{Budget Feasible Experimental Design} @@ -132,10 +140,17 @@ etc.). The cost $c_i$ is the amount the subject deems sufficient to incentivize her participation in the study. Note that, in this setup, the feature vectors $x_i$ are public information that the experimenter can consult prior the experiment design. Moreover, though a subject may lie about her true cost $c_i$, she cannot lie about $x_i$ (\emph{i.e.}, all features are verifiable upon collection) or $y_i$ (\emph{i.e.}, she cannot falsify her measurement). %\subsection{D-Optimality Criterion} +<<<<<<< HEAD Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes or approximates \eqref{dcrit} . Since \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation one would consider the (equivalent) maximization of $V(S) = \det\T{X_S}X_S$. %, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. However, the following lower bound implies that such an optimization goal cannot be attained under the constraints of truthfulness, budget feasibility, and individual rationality. \begin{lemma} For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individionally rational mechanism for a budget feasible reverse auction with $V(S) = \det{\T{X_S}X_S}$. +======= +Ideally, motivated by the $D$-optimality criterion, we would like to design a mechanism that maximizes \eqref{dcrit} within a good approximation ratio. As \eqref{dcrit} may take arbitrarily small negative values, to define a meaningful approximation one would consider the (equivalent) maximization of $V(S) = \det\T{X_S}X_S$. %, for some strictly increasing, on-to function $f:\reals_+\to\reals_+$. +However, the following lower bound implies that such an optimization goal cannot be attained under the constraints of truthfulness, budget feasibility, and individual rationality. +\begin{lemma} +For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individually rational mechanism for a budget feasible reverse auction with value function $V(S) = \det{\T{X_S}X_S}$. +>>>>>>> c29302b25adf190f98019eb8ce5f79b10b66d54d \end{lemma} \begin{proof} \input{proof_of_lower_bound1} diff --git a/related.tex b/related.tex index ec22041..9573309 100644 --- a/related.tex +++ b/related.tex @@ -6,19 +6,19 @@ Budget feasible mechanism design was originally proposed by Singer \cite{singer- In contrast to the above results, no 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$-appoximate 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 mechanisms, improving upon an earlier bound of 2 by Singer \cite{singer-mechanisms}. -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, Chen \emph{et al.}~\cite{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-mechanisms,singer-influence}. +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, Chen \emph{et al.}~\cite{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-mechanisms,singer-influence}. Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists a truthful, $O(\log^3 n)$-approximate mechanism -\cite{dobz2011-mechanisms} as well as a a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization. +\cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization \cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations) - A series of recent papers \cite{mcsherrytalwar,approximatemechanismdesign,xiao:privacy-truthfulness,chen:privacy-truthfulness} consider the related problem of conducting retreive data from an \textit{unverified} database: the buyer of the data cannot verify the data reported by individuals and therefore must incentivize them to report truthfully. -McSherry and Talwar \cite{mcsherrytalwar} argue that \emph{differentially private} mechanisms also offer a form of \emph{approximate truthfulness}, as the mechanism's output is only slightly purturbed when an individual unilaterally changes her data value; as a result, reporting untruthfully can only increase an individual's utility by a small amount. Xiao \cite{xiao:privacy-truthfulness}, improving upon earlier work by Nissim et al.~\cite{approximatemechanismdesign} construct mechanisms that + A series of recent papers \cite{mcsherrytalwar,approximatemechanismdesign,xiao:privacy-truthfulness,chen:privacy-truthfulness} consider the related problem of conducting retrieve data from an \textit{unverified} database: the buyer of the data cannot verify the data reported by individuals and therefore must incentivize them to report truthfully. +McSherry and Talwar \cite{mcsherrytalwar} argue that \emph{differentially private} mechanisms also offer a form of \emph{approximate truthfulness}, as the mechanism's output is only slightly perturbed when an individual unilaterally changes her data value; as a result, reporting untruthfully can only increase an individual's utility by a small amount. Xiao \cite{xiao:privacy-truthfulness}, improving upon earlier work by Nissim \emph{et al.}~\cite{approximatemechanismdesign} construct mechanisms that simultaneously achieve exact truthfulness as well as differential privacy. Eliciting private data through a \emph{survey} \cite{roth-liggett}, whereby individuals first decide whether to participate in the survey and then report their data, also fall under the unverified database setting \cite{xiao:privacy-truthfulness}. Our work differs from the above works in that it does not capture user utility through differential privacy; crucially, we also assume that experiments conducted are \emph{tamper-proof}, and individuals can missreport their costs but not their values. -Our work is closest to Roth and Schoenebeck \cite{roth-shoenebeck}, who also consider how to sample individuals from a population to obtain an unbiased estimate of a reported value. The authors assume a prior on the joint distribution +Our work is closest to Roth and Schoenebeck \cite{roth-schoenebeck}, who also consider how to sample individuals from a population to obtain an unbiased estimate of a reported value. The authors assume a prior on the joint distribution \stratis{to be continued} |