diff options
| -rw-r--r-- | appendix.tex | 68 | ||||
| -rw-r--r-- | approximation.tex | 116 | ||||
| -rw-r--r-- | definitions.tex | 15 | ||||
| -rw-r--r-- | notes.bib | 49 | ||||
| -rw-r--r-- | paper.tex | 8 | ||||
| -rw-r--r-- | problem.tex | 2 |
6 files changed, 144 insertions, 114 deletions
diff --git a/appendix.tex b/appendix.tex index ca6d1df..67ae7cc 100644 --- a/appendix.tex +++ b/appendix.tex @@ -1,22 +1,16 @@ -\subsection{Proof of Proposition~\ref{prop:relaxation}} +\section{Proof of Proposition~\ref{prop:relaxation}} -\begin{lemma}\label{lemma:relaxation-ratio} -For all $\lambda\in[0,1]^{n},$ - $ \frac{1}{2} - \,L(\lambda)\leq - F(\lambda)\leq L(\lambda)$. -\end{lemma} - -\begin{proof} +\subsection{Proof of Lemma~\ref{lemma:relaxation-ratio}}\label{proofofrelaxation-ratio} +%\begin{proof} The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}}(\lambda)$ follows by the concavity of the $\log\det$ function and Jensen's inequality. To show the lower bound, we first prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i - F(\lambda)/\partial_i L(\lambda)$, where - $\partial_i\, \cdot$ denotes the partial derivative with respect to the - $i$-th variable. + F(\lambda)/\partial_i L(\lambda)$, where we use + $\partial_i\, \cdot$ as a shorthand for $\frac{\partial}{\partial \lambda_i}$, the partial derivative with respect to the + $i$-th variable. - Let us start by computing the derivatives of $F$ and - $L$ with respect to the $i$-th component. + Let us start by computing the partial derivatives of $F$ and + $L$ with respect to the $i$-th component. Observe that \begin{displaymath} \partial_i P_\mathcal{N}^\lambda(S) = \left\{ @@ -149,8 +143,8 @@ from below by 1/2 for small enough $\lambda$. Second, if the minimum of the ratio $F(\lambda)/L(\lambda)$ is attained at a vertex of the hypercube $[0,1]^n$ different from 0. $F$ and $L$ being relaxations of the value function $V$, they are equal to $V$ on the vertices -which are exactly the binary points. Hence the minimum is equal to 1 in this -case. In particular it is greater than $1/2$. +which are exactly the binary points. Hence, the minimum is equal to 1 in this +case; in particular, it is greater than $1/2$. Finally, if the minimum is attained at a point $\lambda^*$ with at least one coordinate belonging to $(0,1)$, let $i$ be one such coordinate and consider @@ -162,34 +156,26 @@ the function $G_i$: Then this function attains a minimum at $\lambda^*_i\in(0,1)$ and its derivative is zero at this point. Hence: \begin{displaymath} - 0 = G_i'(\lambda^*_i) = \partial_i\left(\frac{F}{L}\right)(\lambda^*) -\end{displaymath}. + 0 = G_i'(\lambda^*_i) = \partial_i\left(\frac{F}{L}\right)(\lambda^*). +\end{displaymath} But $\partial_i(F/L)(\lambda^*)=0$ implies that \begin{displaymath} \frac{F(\lambda^*)}{L(\lambda^*)} = \frac{\partial_i F(\lambda^*)}{\partial_i L(\lambda^*)}\geq \frac{1}{2} \end{displaymath} using the lower bound on the ratio of the partial derivatives. This concludes -the proof of the lemma. -\end{proof} - -We now prove that $F$ admits the following exchange property: let -$\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one -fractional component of $\lambda$ for another until one of them becomes -integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and -for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point -$\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n -\lambda_i c_i \leq B$. 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 of the lemma. \qed +%\end{proof} -\begin{lemma}[Rounding]\label{lemma:rounding} - For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible - $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is - fractional %, that is, lies in $(0,1)$ and: - and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$. -\end{lemma} +%We now prove that $F$ admits the following exchange property: let $\lambda$ be a feasible element of $[0,1]^n$, it is possible to trade one fractional component of $\lambda$ for another until one of them becomes integral, obtaining a new element $\tilde{\lambda}$ which is both feasible and for which $F(\tilde{\lambda})\geq F(\lambda)$. Here, by feasibility of a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{i=1}^n \lambda_i c_i \leq B$. 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}. +%\begin{lemma}[Rounding]\label{lemma:rounding} +% For any feasible $\lambda\in[0,1]^{n}$, there exists a feasible +% $\bar{\lambda}\in[0,1]^{n}$ such that at most one of its components is +% fractional %, that is, lies in $(0,1)$ and: +% and $F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})$. +%\end{lemma} +\subsection{Proof of Lemma~\ref{lemma:rounding}}\label{proofoflemmarounding} \begin{proof} We give a rounding procedure which, given a feasible $\lambda$ with at least two fractional components, returns some feasible $\lambda'$ with one less fractional @@ -232,7 +218,7 @@ $\varepsilon$-convexity by \citeN{pipage}. $\lambda_\varepsilon$ becomes integral. \end{proof} -\subsubsection*{End of the proof of Proposition~\ref{prop:relaxation}} +\subsection*{End of the proof of Proposition~\ref{prop:relaxation}} Let us consider a feasible point $\lambda^*\in[0,1]^{n}$ such that $L(\lambda^*) = L^*_c$. By applying Lemma~\ref{lemma:relaxation-ratio} and @@ -258,7 +244,7 @@ one fractional component such that \end{equation} Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qedhere -\subsection{Proof of Proposition~\ref{prop:monotonicity}} +\section{Proof of Proposition~\ref{prop:monotonicity}} The $\log\det$ function is concave and self-concordant (see \cite{boyd2004convex}), in this case, the analysis of the barrier method in @@ -464,7 +450,7 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$. with $\lambda^{'*}$ optimal for $(P_{c', \alpha})$. Since $c_i'\leq 1$, using Lemma~\ref{lemma:derivative-bounds}, we get that $\xi^*\geq \frac{b}{2^n}$, which concludes the proof. \end{proof} -\subsubsection*{End of the proof of Proposition~\ref{prop:monotonicity}} +\subsection*{End of the proof of Proposition~\ref{prop:monotonicity}} Let $\tilde{L}^*_c$ be the approximation computed by Algorithm~\ref{alg:monotone}. @@ -498,7 +484,7 @@ Note that: Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed \end{enumerate} -\subsection{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} +\section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} We now present the proof of Theorem~\ref{thm:main}. $\delta$-truthfulness and individual rationality follow from $\delta$-monotonicity and threshold @@ -663,7 +649,7 @@ Placing the expression of $C$ in \eqref{eq:bound1} and \eqref{eq:bound2} gives the approximation ratio in \eqref{approxbound}, and concludes the proof of Theorem~\ref{thm:main}.\hspace*{\stretch{1}}\qed -\subsection{Proof of Theorem \ref{thm:lowerbound}} +\section{Proof of Theorem \ref{thm:lowerbound}} Suppose, for contradiction, that such a mechanism exists. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ diff --git a/approximation.tex b/approximation.tex index 7c3c47d..20af216 100644 --- a/approximation.tex +++ b/approximation.tex @@ -1,75 +1,89 @@ -Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any of the costs $c_i$ leads to an increase of the estimate of $OPT$. In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{}, monotonicity prevents using traditional approximation algorithms. +Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any cost $c_i$ leads to an increase of in the estimation of $OPT$. In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{}, monotonicity precludes using traditional approximation algorithms. -We address this issue by designing a convex relaxation of \EDP{}, and showing that it well approximates $OPT$. +In the fist part of this section, we address this issue by designing a convex relaxation of \EDP{}, and showing that its solution well approximates $OPT$. The objective of this relaxation is concave and self-concordant \cite{boyd2004convex}, and, as such, the exists an algorithm that solves this relaxed problem with arbitrary accuracy in polynomial time. Unfortunately, the output of this algorithm may not necessarily be monotone. Nevertheless, in the second part of this section, we show how a solver of the relaxed problem can be used to construct a solver that is ``almost'' monotone: in Section~\ref{sec:main}, we show how this algorithm can be used to design a $\delta$-truthful mechanism for \EDP. -As noted above, \EDP{} is NP-hard. Designing a mechanism for this problem, as -we will see in Section~\ref{sec:mechanism}, will involve being able to find an approximation of its optimal value -$OPT$ defined in \eqref{eq:non-strategic}. In addition to being computable in -polynomial time and having a bounded approximation ratio to $OPT$, we will also -require this approximation to be non-increasing in the following sense: -\begin{definition} -Let $f$ be a function from $\reals^n$ to $\reals$. We say that $f$ is -\emph{non-decreasing (resp. non-increasing) along the $i$-th coordinate} iff: -\begin{displaymath} -\forall x\in\reals^n,\; -t\mapsto f(x+ te_i)\; \text{is non-decreasing (resp. non-increasing)} -\end{displaymath} -where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. +%As noted above, \EDP{} is NP-hard. Designing a mechanism for this problem, as +%we will see in Section~\ref{sec:mechanism}, will involve being able to find an approximation of its optimal value +%$OPT$ defined in \eqref{eq:non-strategic}. In addition to being computable in +%polynomial time and having a bounded approximation ratio to $OPT$, we will also +%require this approximation to be non-increasing in the following sense: -We say that $f$ is \emph{non-decreasing} (resp. \emph{non-increasing}) iff it -is non-decreasing (resp. non-increasing) along all coordinates. -\end{definition} +%\begin{definition} +%Let $f$ be a function from $\reals^n$ to $\reals$. We say that $f$ is +%\emph{non-decreasing (resp. non-increasing) along the $i$-th coordinate} iff: +%\begin{displaymath} +%\forall x\in\reals^n,\; +%t\mapsto f(x+ te_i)\; \text{is non-decreasing (resp. non-increasing)} +%\end{displaymath} +%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. + +%We say that $f$ is \emph{non-decreasing} (resp. \emph{non-increasing}) iff it +%is non-decreasing (resp. non-increasing) along all coordinates. +%\end{definition} -Such an approximation will be obtained by introducing a concave optimization -problem with a constant approximation ratio to \EDP{} -(Proposition~\ref{prop:relaxation}) and then showing how to approximately solve -this problem in a monotone way. +%Such an approximation will be obtained by introducing a concave optimization +%problem with a constant approximation ratio to \EDP{} +%(Proposition~\ref{prop:relaxation}) and then showing how to approximately solve +%this problem in a monotone way. -\subsection{A Concave Relaxation of \EDP}\label{sec:concave} +\subsection{A Convex Relaxation of \EDP}\label{sec:concave} 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$. +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 optimization problems through \emph{pipage rounding}, a technique proposed by \citeN{pipage}. Let $P_\mathcal{N}^\lambda(S)$ be the probability of choosing the set $S$ if we select each element $i$ in $\mathcal{N}$ independently with -probability $\lambda_i$: -\begin{displaymath} - P_\mathcal{N}^\lambda(S) \defeq \prod_{i\in S} \lambda_i - \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i). -\end{displaymath} -Then, the \emph{multi-linear} extension $F$ of $V$ is defined as the +probability $\lambda_i$, \emph{i.e.}, +%\begin{displaymath} +$ P_\mathcal{N}^\lambda(S) \defeq \prod_{i\in S} \lambda_i + \prod_{i\in\mathcal{N}\setminus S}( 1 - \lambda_i).$ +%\end{displaymath} +Then, the \emph{multi-linear} extension $F:[0,1]^n\to\reals$ of $V$ is defined as the expectation of $V$ under the probability distribution $P_\mathcal{N}^\lambda$: \begin{equation}\label{eq:multi-linear} F(\lambda) \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big] - = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) + % = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) += \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right] \end{equation} - -This function is an extension of $V$ in the following sense: $F(\id_S) = V(S)$ for all -$S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. - -\citeN{pipage} have shown how to use this extension to obtain approximation -guarantees for an interesting class of optimization problems through the -\emph{pipage rounding} framework, which has been successfully applied -in \citeN{chen, singer-influence}. - -For the specific function $V$ defined in \eqref{modified}, the -multi-linear extension cannot be computed (and \emph{a fortiori} maximized) in -polynomial time. Hence, we introduce a new function $L$: +Function $F$ is an extension of $V$ in the domain $[0,1]^n$, as it agrees with $V$ at integer inputs: $F(\id_S) = V(S)$ for all +$S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. %\citeN{pipage} have shown how to use this extension to obtain approximation guarantees for an interesting class of optimization problems through the \emph{pipage rounding} framework, which has been successfully applied in \citeN{chen, singer-influence}. +Unfortunately, for $V$ the information gain function that we study, the +multi-linear extension cannot be computed---let alone maximized---in +polynomial time. Hence, we introduce a new extention $L:[0,1]^n\to\reals$: \begin{equation}\label{eq:our-relaxation} \forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq -\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right), +\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right)= +\log\det\left(\mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right). \end{equation} -Note that this relaxation, -follows naturally from the \emph{multi-linear} extension by swapping the -expectation and $V$ in \eqref{eq:multi-linear}: -\begin{displaymath} - L(\lambda) = \log\det\left(\mathbb{E}_{S\sim - P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right). -\end{displaymath} +Note that $L$ also extends $V$, and follows naturally from the multi-linear extension by swapping the +expectation and $\log \det$ in \eqref{eq:multi-linear}. Crucially, it \emph{strictly concave} on $[0,1]^n$, a fact that, we exploit in the next section to maximize $L$ subject to the budget constraint in a polynomial time. +%\begin{displaymath} +% L(\lambda) = +%\end{displaymath} + +Our first technical lemma relates the concave extension $L$ to the multi-linear extension $F$: +\begin{lemma}\label{lemma:relaxation-ratio} +For all $\lambda\in[0,1]^{n},$ + $ \frac{1}{2} + \,L(\lambda)\leq + F(\lambda)\leq L(\lambda)$. +\end{lemma} +The proof of this lemma can be found in Appendix~\ref{proofofrelaxation-ratio}. In short, we prove this by exploiting the concavity of the $\log\det$ function over the set of positive semidefinite matrices to bound the ratio of all partial derivatives of $F$ and $L$; we subsequently show that the bound on ratio of the derivatives also implies a bound over the ratio $F/L$ in $[0,1]$. + +Armed with this result, we can then show using pipage rounding that any $\lambda$ that maximizes the multi-linear extension $F$ can be rounded to an ``almost'' integral solution. More specifically, given a set of costs $c\in \reals^n_+$, we say that a $\lambda\in [0,1]^n$ is feasible if it belongs to the set +\begin{align}\dom_c =\{\lambda \in [0,1]^n: \sum_{i\in \mathcal{N}} c_i\lambda_i\leq B\}.\label{fdom}\end{align} Then, the following lemma holds: +\begin{lemma}[Rounding]\label{lemma:rounding} + For any feasible $\lambda\in \dom_c$, there exists a feasible + $\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 Appendix \ref{proofoflemmarounding}, 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 optimization program \eqref{eq:non-strategic} extends naturally to such a relaxation. We define: diff --git a/definitions.tex b/definitions.tex index d474853..555c02e 100644 --- a/definitions.tex +++ b/definitions.tex @@ -1,14 +1,14 @@ \newcommand{\mutual}{\ensuremath{{I}}} \newcommand{\entropy}{\ensuremath{{H}}} \newtheorem{lemma}{Lemma} -\newtheorem{proposition}[lemma]{Proposition} -\newtheorem{fact}[lemma]{Fact} -\newtheorem{example}[lemma]{Example} -\newtheorem{prop}[lemma]{Proposition} -\newtheorem{theorem}[lemma]{Theorem} -\newtheorem{corollary}[lemma]{Corollary} +\newtheorem{proposition}{Proposition} +\newtheorem{fact}{Fact} +\newtheorem{example}{Example} +\newtheorem{prop}{Proposition} +\newtheorem{theorem}{Theorem} +\newtheorem{corollary}{Corollary} \theoremstyle{definition} -\newtheorem{definition}[lemma]{Definition} +\newtheorem{definition}{Definition} \newcommand{\citeN}{\citet} %\newcommand*{\defeq}{\stackrel{\text{def}}{=}} \newcommand*{\defeq}{\equiv} @@ -34,3 +34,4 @@ \newcommand{\id}{\mathbbm{1}} \newcommand{\junk}[1]{} \newcommand{\edp}{{\tt EDP}} +\newcommand{\dom}{\mathcal{D}} @@ -5,6 +5,29 @@ publisher={Cambridge University Press} } +@inproceedings{dughmi2011convex, + title={From convex optimization to randomized mechanisms: toward optimal combinatorial auctions}, + author={Dughmi, Shaddin and Roughgarden, Tim and Yan, Qiqi}, + booktitle={Proceedings of the 43rd annual ACM symposium on Theory of computing}, + pages={149--158}, + year={2011}, + organization={ACM} +} + + +@article{schummer2004almost, + title={Almost-dominant strategy implementation: exchange economies}, + author={Schummer, James}, + journal={Games and Economic Behavior}, + volume={48}, + number={1}, + pages={154--170}, + year={2004}, + publisher={Elsevier} +} + + + @inproceedings{roth-schoenebeck, author = {Roth, Aaron and Schoenebeck, Grant}, title = {Conducting truthful surveys, cheaply}, @@ -58,6 +81,22 @@ year = 2012 year={1998}, publisher={SIAM} } +@inproceedings{vondrak2008optimal, + title={Optimal approximation for the submodular welfare problem in the value oracle model}, + author={Vondrak, Jan}, + booktitle={Proceedings of the 40th annual ACM symposium on Theory of computing}, + pages={67--74}, + year={2008}, + organization={ACM} +} +@incollection{calinescu2007maximizing, + title={Maximizing a submodular set function subject to a matroid constraint}, + author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan}, + booktitle={Integer programming and combinatorial optimization}, + pages={182--196}, + year={2007}, + publisher={Springer} +} @book{pukelsheim2006optimal, @@ -447,16 +486,6 @@ year = 2012 publisher={MIT press} } -@article{determinant, - title={Determinant maximization with linear matrix inequality constraints}, - author={Vandenberghe, L. and Boyd, S. and Wu, S.P.}, - journal={SIAM journal on matrix analysis and applications}, - volume={19}, - number={2}, - pages={499--533}, - year={1998}, - publisher={SIAM} -} @inproceedings{dobz2011-mechanisms, author = {Shahar Dobzinski and @@ -35,13 +35,13 @@ \input{approximation} \section{Mechanism for \SEDP{}}\label{sec:mechanism} \input{main} -\section{Extensions}\label{sec:ext} -\input{general} %\section{Conclusion} %\input{conclusion} \bibliographystyle{abbrvnat} \bibliography{notes} -\newpage -\section{Appendix} +\appendix \input{appendix} +\section{Extensions}\label{sec:ext} +\input{general} + \end{document} diff --git a/problem.tex b/problem.tex index 4e31ac1..bb69120 100644 --- a/problem.tex +++ b/problem.tex @@ -175,7 +175,7 @@ returns a vector of payments $[p_i(c)]_{i\in \mathcal{N}}$. costs: $p_i(c)\geq c_i\cdot s_i(c).\label{ir}$ \item \emph{No Positive Transfers.} Payments are non-negative: $p_i(c)\geq 0\label{pt}$. \item \emph{$\delta$-Truthfulness.} Reporting one's true cost is -a $\delta$-dominant strategy. Formally, let $c_{-i}$ +an \emph{almost-dominant} \cite{schummer2004almost} strategy. Formally, let $c_{-i}$ be a vector of costs of all agents except $i$. Then, $p_i(c_i,c_{-i}) - s_i(c_i,c_{-i})\cdot c_i \geq p_i(c_i',c_{-i}) - s_i(c_i',c_{-i})\cdot c_i, \label{truthful}$ for every $i \in \mathcal{N}$ and every two cost vectors $(c_i,c_{-i})$ and $(c_i',c_{-i})$ such that $|c_i-c_i'|>\delta.$ The mechanism is \emph{truthful} if $\delta=0$. |