diff options
| -rwxr-xr-x | approximation.tex | 4 | ||||
| -rwxr-xr-x | main.tex | 2 | ||||
| -rwxr-xr-x | problem.tex | 5 | ||||
| -rwxr-xr-x | related.tex | 12 |
4 files changed, 10 insertions, 13 deletions
diff --git a/approximation.tex b/approximation.tex index 2747d5a..bab2c93 100755 --- a/approximation.tex +++ b/approximation.tex @@ -129,7 +129,7 @@ In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\del 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}: +Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbed problem: \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} @@ -144,4 +144,4 @@ Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concav $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 formal description of the algorithm are in \cite{arxiv}. +The proof can be found in \cite{arxiv}. @@ -1,6 +1,6 @@ \label{sec:main} -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. +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. We briefly outline this below (see \cite{arxiv} for a detailed description). 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 diff --git a/problem.tex b/problem.tex index 46e72c5..6033e86 100755 --- a/problem.tex +++ b/problem.tex @@ -31,8 +31,7 @@ $\sigma^2$ is the noise variance). Then, \E\ estimates $\beta$ through \emph{maximum a posteriori estimation}: \emph{i.e.}, finding the parameter which maximizes the posterior distribution of $\beta$ given the observations $y_S$. Under the linearity assumption and the Gaussian prior on $\beta$, -maximum a posteriori estimation leads to the following maximization -\cite{hastie}: +maximum a posteriori estimation leads to \cite{hastie}: \begin{align} \begin{split} \hat{\beta} = \textstyle\argmax_{\beta\in\reals^d} \prob(\beta\mid y_S) @@ -159,7 +158,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 \cite{arxiv}. 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}, motivating 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 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. |