diff options
| -rwxr-xr-x | approximation.tex | 12 | ||||
| -rwxr-xr-x | main.tex | 11 | ||||
| -rwxr-xr-x | paper.tex | 15 |
3 files changed, 19 insertions, 19 deletions
diff --git a/approximation.tex b/approximation.tex index bab2c93..87d67d9 100755 --- a/approximation.tex +++ b/approximation.tex @@ -34,7 +34,7 @@ In the first part of this section, we address this issue by designing a convex r A classical way of relaxing combinatorial optimization problems is \emph{relaxing by expectation}, using the so-called \emph{multi-linear} extension of the objective function $V$ (see, \emph{e.g.}, \cite{calinescu2007maximizing,vondrak2008optimal,dughmi2011convex}). -This is because this extension can yield approximation guarantees for a wide class of combinatorial problems through \emph{pipage rounding}, a technique proposed by \citeN{pipage}. In general, such relaxations preserve monotonicity which, as discussed, is required in mechanism design. +This is because this extension can yield approximation guarantees for a wide class of combinatorial problems through \emph{pipage rounding}, a technique by \citeN{pipage}. In general, such relaxations preserve monotonicity which, as discussed, is required in mechanism design. Formally, let $P_\mathcal{N}^\lambda$ be a probability distribution over $\mathcal{N}$ parametrized by $\lambda\in [0,1]^n$, where a set $S\subseteq \mathcal{N}$ sampled from $P_\mathcal{N}^\lambda$ is constructed as follows: each $i\in \mathcal{N}$ is selected to be in $S$ independently with probability $\lambda_i$, \emph{i.e.}, %\begin{displaymath} @@ -82,16 +82,16 @@ Armed with this result, we subsequently use pipage rounding to show that any $\ $\bar{\lambda}\in \dom_c$ such that (a) $F(\lambda)\leq F(\bar{\lambda})$, and (b) at most one of the coordinates of $\bar{\lambda}$ is fractional. %, that is, lies in $(0,1)$ and: \end{lemma} -The proof of this lemma is in \cite{arxiv}, and follows the main steps of the pipage rounding method of \citeN{pipage}. % this rounding property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or $\varepsilon$-convexity by \citeN{pipage}. +The proof, also in \cite{arxiv}, follows the main steps of the pipage rounding method of \citeN{pipage}. % this rounding property is referred to in the literature as \emph{cross-convexity} (see, \emph{e.g.}, \cite{dughmi}), or $\varepsilon$-convexity by \citeN{pipage}. Together, Lemma~\ref{lemma:relaxation-ratio} and Lemma~\ref{lemma:rounding} imply that $OPT$, the optimal value of \EDP, can be approximated by solving the following convex optimization problem: \begin{align}\tag{$P_c$}\label{eq:primal} \text{Maximize:} \quad L(\lambda)\quad \text{subject to:} \quad\lambda \in \dom_c \end{align} -In particular, for $L_c^*\defeq \max_{\lambda\in \dom_c} L(\lambda)$, the following holds: +In particular, for $L_c^*\defeq \max_{\lambda\in \dom_c} L(\lambda)$, the following holds \cite{arxiv}: \begin{proposition}\label{prop:relaxation} $OPT\leq L^*_c \leq 2 OPT + 2\max_{i\in\mathcal{N}}V(i)$. \end{proposition} -The proof of this proposition can be found in \cite{arxiv}. As we discuss in the next section, $L^*_c$ can be computed by a poly-time algorithm at arbitrary accuracy. However, the outcome of this computation may not necessarily be monotone; we address this by converting this poly-time estimator of $L^*_c$ to one that is ``almost'' monotone.%The optimization program \eqref{eq:non-strategic} extends naturally to such +As we discuss in the next section, $L^*_c$ can be computed by a poly-time algorithm at arbitrary accuracy. However, the outcome of this computation may not necessarily be monotone; we address this by converting this poly-time estimator of $L^*_c$ to one that is ``almost'' monotone.%The optimization program \eqref{eq:non-strategic} extends naturally to such %a relaxation. We define: %\begin{equation}\tag{$P_c$}\label{eq:primal} % L^*_c \defeq \max_{\lambda\in[0, 1]^{n}} @@ -108,7 +108,7 @@ The proof of this proposition can be found in \cite{arxiv}. As we discuss in the %proposition which is also proved in the Appendix. \subsection{Polynomial-Time, Almost-Monotone Approximation}\label{sec:monotonicity} - The $\log\det$ objective function of \eqref{eq:primal} is strictly concave and \emph{self-concordant} \cite{boyd2004convex}. The maximization of a concave, self-concordant function subject to a set of linear constraints can be performed through the \emph{barrier method} (see, \emph{e.g.}, \cite{boyd2004convex} Section 11.5.5 for general self-concordant optimization as well as \cite{vandenberghe1998determinant} for a detailed treatment of the $\log\det$ objective). The performance of the barrier method is summarized in our case by the following lemma: +The $\log\det$ objective function of \eqref{eq:primal} is strictly concave and \emph{self-concordant}~\cite{boyd2004convex}. The maximization of a concave, self-concordant function subject to a set of linear constraints can be performed through the \emph{barrier method} (see, \emph{e.g.},~\cite{boyd2004convex} Section 11.5.5 for general self-concordant optimization as well as \cite{vandenberghe1998determinant} for a detailed treatment of the $\log\det$ objective). The performance of the barrier method is summarized in our case by the following lemma: \begin{lemma}[\citeN{boyd2004convex}]\label{lemma:barrier} For any $\varepsilon>0$, the barrier method computes an approximation $\hat{L}^*_c$ that is $\varepsilon$-accurate, \emph{i.e.}, it satisfies $|\hat L^*_c- L^*_c|\leq \varepsilon$, in time $O\left(poly(n,d,\log\log\varepsilon^{-1})\right)$. The same guarantees apply when maximizing $L$ subject to an arbitrary set of $O(n)$ linear constraints. @@ -136,6 +136,8 @@ Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbed problem: \end{split} \end{align} +The restricted set $\dom_{c,\alpha}$ ensures that the partial derivatives of the optimal solution to $P_{c,\alpha}$ with respect to the costs are bounded from below. This implies that an approximate solution to $P_{c,\alpha}$ given by the barrier method is $\delta$-decreasing with respect to the costs. On the other hand, by taking $\alpha$ small enough, we ensure that the approximate solution to $P_{c,\alpha}$ is still an $\epsilon$-accurate approximation of $L_c^*$. This methodology is summarized in the following proposition whose proof can be found in \cite{arxiv}. + \begin{proposition}\label{prop:monotonicity} For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$, using the barrier method to solve \eqref{eq:perturbed-primal} for $\alpha\defeq\varepsilon @@ -13,17 +13,16 @@ approximation is compared to $V(\{i^*\})$: if it exceeds $V(\{i^*\})$, then the mechanism constructs an allocation $S_G$ greedily; otherwise, the only item allocated is the singleton $\{i^*\}$. Provided that the approximation used is within a constant from $OPT$, the above allocation can be shown to also yield -a constant approximation to $OPT$. Furthermore, using Myerson's -Theorem~\cite{myerson}, it can be shown that this allocation combined with +a constant approximation to $OPT$. Furthermore, Myerson's +Theorem~\cite{myerson} implies that this allocation combined with \emph{threshold payments} (see Lemma~\ref{thm:myerson-variant} below) constitute a truthful mechanism. The approximation algorithms used in \cite{chen,singer-influence} are LP relaxations, and thus their outputs are monotone and can be computed exactly in -polynomial time. We show that the convex relaxation \eqref{eq:primal}, which -can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be -used to construct a $\delta$-truthful, constant approximation mechanism, by -being incorporated in the same framework. +polynomial time. We show that the convex relaxation \eqref{eq:primal}, solved +by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to +construct a $\delta$-truthful, constant approximation \mbox{mechanism.} To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in \cite{arxiv}. @@ -1,12 +1,11 @@ \documentclass{llncs} -\pagestyle{plain} \usepackage[numbers, sectionbib]{natbib} \usepackage[utf8]{inputenc} \usepackage{amsmath,amsfonts} \usepackage{algorithm, algpseudocode} \usepackage{bbm,color,verbatim} \input{definitions} -\usepackage[pagebackref=true,breaklinks=true,colorlinks=true,pagebackref=false]{hyperref} +%\usepackage[pagebackref=true,breaklinks=true,colorlinks=true,pagebackref=false]{hyperref} \title{Budget Feasible Mechanisms \\for Experimental Design} \author{ Thibaut Horel\inst{1} @@ -43,12 +42,12 @@ \begin{footnotesize} \bibliography{notes} \end{footnotesize} -\appendix -\input{appendix} -\section{Extensions}\label{sec:ext} -\input{general} -\section{Non-Truthfulness of the Maximum Operator}\label{sec:non-monotonicity} -\input{counterexample} +%\appendix +%\input{appendix} +%\section{Extensions}\label{sec:ext} +%\input{general} +%\section{Non-Truthfulness of the Maximum Operator}\label{sec:non-monotonicity} +%\input{counterexample} \end{document} |