From 24fdab84d29f2d2fb0bd78a4c7ad7131100afe94 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 16 Dec 2013 17:23:26 -0500 Subject: More space saving --- related.tex | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) (limited to 'related.tex') diff --git a/related.tex b/related.tex index 274f4fa..4c17d1f 100755 --- a/related.tex +++ b/related.tex @@ -3,11 +3,9 @@ \junk{\subsection{Experimental Design} The classic experimental design problem, which we review in Section~\ref{sec:edprelim}, deals with which $k$ experiments to conduct among a set of $n$ possibilities. It is a well studied problem both in the non-Bayesian \cite{pukelsheim2006optimal,atkinson2007optimum,boyd2004convex} and Bayesian setting \cite{chaloner1995bayesian}. Beyond $D$-optimality, several other objectives are encountered in the literature \cite{pukelsheim2006optimal}; many involve a function of the covariance of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by its tractability and its relationship to the information gain. %are encountered in the literature, though they do not relate to entropy as $D$-optimality. We leave the task of approaching the maximization of such objectives from a strategic point of view as an open problem. } -\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 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 +\noindent\emph{General Submodular Functions.} +\citeN{singer-mechanisms} 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 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 be unbounded. No deterministic, truthful, constant approximation mechanism that @@ -15,7 +13,7 @@ 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}. -\noindent\emph{Budget Feasible Mechanism Design on Specific Problems.} +\noindent\emph{Specific Problems.} 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 @@ -40,7 +38,7 @@ 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}, -in which an auctioneer aims at maximizing the social welfare. As noted by \citeN{archer-approximate}, +in which an auctioneer aims at maximizing social welfare. 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. -- cgit v1.2.3-70-g09d2