diff options
| -rwxr-xr-x | appendix.tex | 110 | ||||
| -rwxr-xr-x | main.tex | 74 | ||||
| -rwxr-xr-x | notes.bib | 9 |
3 files changed, 106 insertions, 87 deletions
diff --git a/appendix.tex b/appendix.tex index 73e879d..1a5bcc5 100755 --- a/appendix.tex +++ b/appendix.tex @@ -15,8 +15,8 @@ V(S\cup \{i\}) - V(S)& = \frac{1}{2}\log\det(I_d + \T{X_S}X_S + x_i\T{x_i}) - \frac{1}{2}\log\det(I_d + \T{X_S}X_S)\nonumber\\ & = \frac{1}{2}\log\det(I_d + x_i\T{x_i}(I_d + -\T{X_S}X_S)^{-1}) - = \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)\label{eq:marginal_contrib} +\T{X_S}X_S)^{-1})\nonumber\\ +&= \frac{1}{2}\log(1 + \T{x_i}A(S)^{-1}x_i)\label{eq:marginal_contrib} \end{align} where $A(S) \defeq I_d+ \T{X_S}X_S$, and the last equality follows from the Sylvester's determinant identity~\cite{sylvester}. Monotonicity therefore follows from the fact that $A(S)^{-1}$ is positive semidefinite. Finally, since the inverse is decreasing over positive definite matrices, we have @@ -107,8 +107,8 @@ for all $S\subseteq\mathcal{N}\setminus\{i\}$. Hence, & \geq \frac{1}{4} \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}}^\lambda(S) - \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big) - +\frac{1}{4} + \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\ + &+\frac{1}{4} \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}} P_{\mathcal{N}}^\lambda(S\cup\{i\}) \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\ @@ -212,8 +212,8 @@ the proof of the lemma. \qed F_\lambda(\varepsilon) & = \mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}^\lambda(S')}\Big[ (\lambda_i+\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i,j\})\\ - & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\}) - + (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\ + & + (\lambda_i+\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{i\})\\ + &+ (1-\lambda_i-\varepsilon)\Big(\lambda_j-\varepsilon\frac{c_i}{c_j}\Big)V(S'\cup\{j\})\\ & + (1-\lambda_i-\varepsilon)\Big(1-\lambda_j+\varepsilon\frac{c_i}{c_j}\Big)V(S')\Big] \end{align*} Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is: @@ -264,7 +264,7 @@ Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed %For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate %approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$. %\end{lemma} -Our next technical result establishes that, using the barrier method, it is possible to construct an algorithm that computes $L^*_c$ at arbitrary accuracy in polynomial time \emph{and} is $\delta$-decreasing. 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 . $$ +We begin by a description of Algorithm~\ref{alg:monotone} which computes an approximation of $L^*_c$, which is arbitrarily accurate \emph{and} $\delta$-decreasing. 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}: \begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal} \begin{split} \text{Maximize:} &\qquad L(\lambda)\\ @@ -335,6 +335,8 @@ well-behaved with respect to changes of the cost (Lemma~\ref{lemma:monotonicity}). These lemmas together imply Proposition~\ref{prop:monotonicity}. +We note that the execution of the barrier method on the restricted set $\dom_{c,\alpha}$ is necessary. The algorithm's output when executed over the entire domain may not necessarily be $\delta$-decreasing, even when the approximation accuracy is small. This is because costs become saturated when the optimal $\lambda\in \dom_c$ lies at the boundary: increasing them has no effect on the objective. Forcing the optimization to happen ``off'' the boundary ensures that this does not occur, while taking $\alpha$ to be small ensures that this perturbation does not cost much in terms of approximation accuracy. + Note that the choice of $\alpha$ given in Algorithm~\ref{alg:monotone} implies that $\alpha<\frac{1}{n}$. This in turn implies that the feasible set $\mathcal{D}_{c, \alpha}$ of \eqref{eq:perturbed-primal} is non-empty: it @@ -561,7 +563,7 @@ $S:\reals_+^n \to 2^\mathcal{N}$ and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$. Let $s_i(c) = \id_{i\in S(c)}$ be the binary indicator of $i\in S(c)$. We seek mechanisms that have the following properties \cite{singer-mechanisms}: \begin{itemize} -\item \emph{Normalization.} Unallocated experiments receive zero payments: $s_i(c)=0\text{ implies }p_i(c)=0.\label{normal}$ +\item \emph{Normalization.} Unallocated experiments receive zero payments: $s_i(c)=0$ implies $p_i(c)=0.\label{normal}$ \item\emph{Individual Rationality.} Payments for allocated experiments exceed 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}$. @@ -590,7 +592,91 @@ Formally, there must exist some $\alpha\geq 1$ and $\beta>0$ \section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson} \input{myerson} -\section{Proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} +\section{Description of our mechanism for \EDP{} and proof of Theorem~\ref{thm:main}}\label{sec:proofofmainthm} + +We begin by a description of the methodology used to construct our mechanism. +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 +constructed greedily, by selecting elements of maximum marginal value per cost. +The general framework used by \citeN{chen} and by \citeN{singer-influence} for +the \textsc{Knapsack} and \textsc{Coverage} value functions contructs an +allocation as follows. First, a polynomial-time, monotone approximation of +$OPT$ is computed over all elements excluding $i^*$. The outcome of this +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 +\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. + +To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in Appendix~\ref{sec:myerson}. +% +%Instead, \citeN{singer-mechanisms} and \citeN{chen} +%suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the +%following properties: +%\begin{itemize} +% \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported cost and must +% be decreasing with respect to the costs. This is to ensure the monotonicity +% of the allocation function. +% \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded +% approximation ratio. +% \item $OPT'_{-i^*}$ must be computable in polynomial time. +%\end{itemize} +% +%One of the main technical contributions of \citeN{chen} and +%\citeN{singer-influence} is to come up with appropriate such quantity by +%considering relaxations of \textsc{Knapsack} and \textsc{Coverage}, +%respectively. +% +%\subsection{Our Approach} +% +%Using the results from Section~\ref{sec:approximation}, we come up with +%a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being +%$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as +%defined below. +% +%\begin{definition} +%Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator +%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is +%$\delta$-truthful iff: +%\begin{displaymath} +%\forall c\in\reals_+^n,\; +%\forall\mu\;\text{with}\; |\mu|\geq\delta,\; +%\forall i\in\{1,\ldots,n\},\; +%p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i +%\end{displaymath} +%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. +%\end{definition} +% +%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie +%by more than $\delta$ about their reported costs. In practical applications, +%the bids being discretized, if $\delta$ is smaller than the discretization +%step, the mechanism will be truthful in effect. + +%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following +%variant of Myerson's theorem. + +\begin{lemma}\label{thm:myerson-variant} + A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is +$\delta$-truthful if: +(a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq +c_i-\delta$, for any +fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i, +c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) + agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$. +\end{lemma} +Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the +above framework, yielding Theorem~\ref{thm:main}. + \begin{algorithm}[!t] \caption{Mechanism for \SEDP{}}\label{mechanism} \begin{algorithmic}[1] @@ -729,7 +815,8 @@ OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big). \end{displaymath} \end{lemma} -Using Proposition~\ref{prop:relaxation} and Lemma~\ref{lemma:greedy-bound} we can complete the proof of +Using Proposition~\ref{prop:relaxation} and Lemma~\ref{lemma:greedy-bound} we +can complete the proof of the approximation ratio of our mechanism Theorem~\ref{thm:main} by showing that, for any $\varepsilon > 0$, if $OPT_{-i}'$, the optimal value of $L$ when $i^*$ is excluded from $\mathcal{N}$, has been computed to a precision $\varepsilon$, then the set @@ -793,8 +880,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 -\section{Proof of Theorem \ref{thm:lowerbound}}\label{proofoflowerbound} - +Finally, we prove the lower bound stated in Theorem~\ref{thm:main} Suppose, for contradiction, that such a mechanism exists. From Myerson's Theorem \cite{myerson}, a single parameter auction is truthful if and only if the allocation function is monotone and agents are paid theshold payments. Consider two experiments with dimension $d=2$, such that $x_1 = e_1=[1 ,0]$, $x_2=e_2=[0,1]$ and $c_1=c_2=B/2+\epsilon$. Then, one of the two experiments, say, $x_1$, must @@ -1,72 +1,11 @@ \label{sec:main} -In this section we use the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal} 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 deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively. We briefly outline this below (see also Algorithm~\ref{mechanism} in Appendix~\ref{sec:proofofmainthm} for a detailed description). +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. %In the strategic case, Algorithm~\eqref{eq:max-algorithm} breaks incentive compatibility. Indeed, \citeN{singer-influence} notes that this allocation function is not monotone, which implies by Myerson's theorem (Theorem~\ref{thm:myerson}) that the resulting mechanism is not truthful. -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 constructed greedily, by selecting elements of maximum marginal value per cost. The general framework used by \citeN{chen} and by \citeN{singer-influence} for the \textsc{Knapsack} and \textsc{Coverage} value functions contructs an allocation as follows. First, a polynomial-time, monotone approximation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this 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 \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. - -To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof we provide in Appendix~\ref{sec:myerson}. -% -%Instead, \citeN{singer-mechanisms} and \citeN{chen} -%suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the -%following properties: -%\begin{itemize} -% \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported cost and must -% be decreasing with respect to the costs. This is to ensure the monotonicity -% of the allocation function. -% \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded -% approximation ratio. -% \item $OPT'_{-i^*}$ must be computable in polynomial time. -%\end{itemize} -% -%One of the main technical contributions of \citeN{chen} and -%\citeN{singer-influence} is to come up with appropriate such quantity by -%considering relaxations of \textsc{Knapsack} and \textsc{Coverage}, -%respectively. -% -%\subsection{Our Approach} -% -%Using the results from Section~\ref{sec:approximation}, we come up with -%a suitable approximation $OPT_{-i^*}'$ of $OPT_{-i^*}$. Our approximation being -%$\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as -%defined below. -% -%\begin{definition} -%Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator -%function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is -%$\delta$-truthful iff: -%\begin{displaymath} -%\forall c\in\reals_+^n,\; -%\forall\mu\;\text{with}\; |\mu|\geq\delta,\; -%\forall i\in\{1,\ldots,n\},\; -%p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i -%\end{displaymath} -%where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. -%\end{definition} -% -%Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie -%by more than $\delta$ about their reported costs. In practical applications, -%the bids being discretized, if $\delta$ is smaller than the discretization -%step, the mechanism will be truthful in effect. - -%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following -%variant of Myerson's theorem. - -\begin{lemma}\label{thm:myerson-variant} - A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is -$\delta$-truthful if: -(a) $S$ is $\delta$-monotone, \emph{i.e.}, for any agent $i$ and $c_i' \leq -c_i-\delta$, for any -fixed costs $c_{-i}$ of agents in $\mathcal{N}\setminus\{i\}$, $i\in S(c_i, -c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) - agents are paid \emph{threshold payments}, \emph{i.e.}, for all $i\in S(c)$, $p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}$. -\end{lemma} -Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the above framework, yielding the following theorem: -\begin{theorem}\label{thm:main} +\begin{theorem}\label{thm:main}\label{thm:lowerbound} For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$, there exists a $\delta$-truthful, individually rational and budget feasible mechanim for \EDP{} that runs in time $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$ @@ -78,14 +17,11 @@ Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the a \varepsilon \simeq 12.98V(S^*) + \varepsilon. \end{displaymath} -\end{theorem} -The proof of the theorem, as well as our proposed mechanism, can be found in Appendix~\ref{sec:proofofmainthm}. -In addition, we prove the following simple lower bound, proved in Appendix~\ref{proofoflowerbound}. - -\begin{theorem}\label{thm:lowerbound} -There is no $2$-approximate, truthful, budget feasible, individually rational +Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. \end{theorem} +The detailed description of our proposed mechanism (see Algorithm~\ref{mechanism}), as well as the proof of the theorem can be found in Appendix~\ref{sec:proofofmainthm}. + @@ -73,7 +73,7 @@ year = 2012 title = {Approximately Optimal Mechanism Design via Differential Privacy}, year = {2012}, - booktitle = {Innovations in Theoretical Computer Science (ITCS)} + booktitle = {ITCS} } @inproceedings{mcsherrytalwar, @@ -98,10 +98,8 @@ year = 2012 @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}, + booktitle={ACM STOC}, year={2008}, - organization={ACM} } @incollection{calinescu2007maximizing, title={Maximizing a submodular set function subject to a matroid constraint}, @@ -678,10 +676,9 @@ author = "Alkiviadis G. Akritas and Evgenia K. Akritas and Genadii I. Malaschono @inproceedings{briest-approximation, title = {Approximation Techniques for Utilitarian Mechanism Design}, - booktitle = {Proceedings of the thirty-seventh annual {ACM} symposium on Theory of computing}, + booktitle = {ACM STOC}, author = {Briest, Patrick and Krysta, Piotr and V\"ocking, Berthold}, year = {2005}, - pages = {39–48}, } @inproceedings{dughmi-truthful, |