diff options
| -rw-r--r-- | appendix.tex | 10 | ||||
| -rw-r--r-- | approximation.tex | 13 | ||||
| -rw-r--r-- | main.tex | 31 | ||||
| -rw-r--r-- | problem.tex | 5 |
4 files changed, 29 insertions, 30 deletions
diff --git a/appendix.tex b/appendix.tex index 682fce2..bf163b4 100644 --- a/appendix.tex +++ b/appendix.tex @@ -476,12 +476,12 @@ Using Lemma~\ref{lemma:barrier} concludes the proof of the running time.\qed \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 -payments. $\delta$-monotonicity and budget feasibility follow the same steps as the -analysis of \citeN{chen}; for the sake of completeness, we restate their proof -here. +We now present the proof of Theorem~\ref{thm:main}. We use the notation $OPT_{-i^*}$ to denote the optimal value of \EDP{} when the maximum value element $i^*$ is excluded. We also use $OPT'_{-i^*}$ the approximation computed by the $\delta$-decreasing, $\epsilon$-accurate approximation of $L^*_{c_{-i^*}}$, as defined in Algorithm~\ref{mechanism}. +The properties of $\delta$-truthfulness and +individual rationality follow from $\delta$-monotonicity and threshold +payments. $\delta$-monotonicity and budget feasibility follow similar steps as the +analysis of \citeN{chen}, adapted to account for $\delta$-monotonicity: \begin{lemma}\label{lemma:monotone} Our mechanism for \EDP{} is $\delta$-monotone and budget feasible. \end{lemma} diff --git a/approximation.tex b/approximation.tex index de1fecd..1a4b44b 100644 --- a/approximation.tex +++ b/approximation.tex @@ -1,4 +1,5 @@ -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 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. +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 in the estimation of $OPT$; %In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{}, +the monotonicity property precludes using traditional approximation algorithms. In the fist part of this section, we address this issue by designing a convex relaxation of \EDP{}, and showing that its solution can be used to approximate $OPT$. The objective of this relaxation is concave and self-concordant \cite{boyd2004convex} and, as such, there 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. @@ -33,7 +34,7 @@ In the fist part of this section, we address this issue by designing a convex re 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}. Crucially for our purposes, such relaxations preserve monotonicity which, as we discussed, is necessary for our mechanism design. +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}. Crucially for our purposes, such relaxations in general 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} @@ -71,7 +72,7 @@ For all $\lambda\in[0,1]^{n},$ \,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 semi-definite matrices to bound the ratio of all partial derivatives of $F$ and $L$; to conclude the proof, we then show that the bound on the ratio of the derivatives also implies a bound on the ratio $F/L$. +The proof of this lemma can be found in Appendix~\ref{proofofrelaxation-ratio}. In short, exploiting the concavity of the $\log\det$ function over the set of positive semi-definite matrices, we first bound the ratio of all partial derivatives of $F$ and $L$. We then show that the bound on the ratio of the derivatives also implies a bound on the ratio $F/L$. Armed with this result, we subsequently use pipage rounding to show 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: @@ -116,7 +117,7 @@ approximation $\hat{L}^*_c$ that is $\varepsilon$-accurate, \emph{i.e.}, it sati Clearly, the optimal value $L^*_c$ of \eqref{eq:primal} is monotone in $c$. Formally, for any two $c,c'\in \reals_+^n$ s.t.~$c\leq c'$ coordinate-wise, $\dom_{c'}\subseteq \dom_c$ and thus $L^*_c\geq L^*_{c'}$. Hence, the map $c\mapsto L^*_c$ is non-increasing. Unfortunately, the same is not true for the output $\hat{L}_c^*$ of the barrier method: there is no guarantee that the $\epsilon$-accurate approximation $\hat{L}^*_c$ exhibits any kind of monotonicity. -Nevertheless, it is possible to use the barrier method to construct an approximation of $L^*_{c}$ that is ``almost'' monotone. More specifically, given $\delta>0$, we will say that $f:\reals^n\to\reals$ is +Nevertheless, we prove that it is possible to use the barrier method to construct an approximation of $L^*_{c}$ that is ``almost'' monotone. More specifically, given $\delta>0$, we will say that $f:\reals^n\to\reals$ is \emph{$\delta$-decreasing} if \begin{equation}\label{eq:dd} f(x) \geq f(x+\mu e_i), \qquad @@ -182,14 +183,14 @@ Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concav \begin{algorithm}[t] \caption{}\label{alg:monotone} \begin{algorithmic}[1] - \Require{ $B\in \reals_+$,$c\in\reals^n_+$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ } + \Require{ $B\in \reals_+$,$c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ } \State $\alpha \gets \min\left(\varepsilon B^{-1}(\delta+n^2)^{-1},\frac{1}{nB}\right) $ \State Use the barrier method to solve \eqref{eq:perturbed-primal} with accuracy $\varepsilon'=\frac{1}{2^{n+1}}\alpha\delta b$; denote the output by $\hat{L}^*_{c,\alpha}$ \State \textbf{return} $\hat{L}^*_{c,\alpha}$ \end{algorithmic} \end{algorithm} -Our construction of a $\delta$-decreasing, $\varepsilon$-accurate approximator of $\hat{L}_c^*$ proceeds as follows: first, it computes an appropriately selected lower bound $\alpha$; using this bound, it proceeds by solving the perturbed problem \eqref{eq:perturbed-primal} using the barrier method, also at an appropriately selected accuracy $\varepsilon'$, obtaining thusly a $\varepsilon'$-accurate approximation of $L^*_{c,\alpha}\defeq \max_{\lambda\in \dom_{c,\alpha}} L(\lambda)$ . The corresponding output is returned as an approximation of $L^*_c$. A summary of algorithm and the specific choices of $\alpha$ and $\varepsilon'$ are given in Algorithm~\ref{alg:monotone}. The following proposition, which is proved in Appendix~\ref{proofofpropmonotonicity}, establishes that this algorithm has the desirable properties: +Our construction of a $\delta$-decreasing, $\varepsilon$-accurate approximator of $\hat{L}_c^*$ proceeds as follows: first, it computes an appropriately selected lower bound $\alpha$; using this bound, it proceeds by solving the perturbed problem \eqref{eq:perturbed-primal} using the barrier method, also at an appropriately selected accuracy $\varepsilon'$, obtaining thusly a $\varepsilon'$-accurate approximation of $L^*_{c,\alpha}\defeq \max_{\lambda\in \dom_{c,\alpha}} L(\lambda)$ . The corresponding output is returned as an approximation of $L^*_c$. A summary of the algorithm and the specific choices of $\alpha$ and $\varepsilon'$ are given in Algorithm~\ref{alg:monotone}. The following proposition, which is proved in Appendix~\ref{proofofpropmonotonicity}, establishes that this algorithm has both properties we desire: \begin{proposition}\label{prop:monotonicity} For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$, Algorithm~\ref{alg:monotone} computes a $\delta$-decreasing, @@ -1,15 +1,15 @@ \label{sec:main} -In this section we present our mechanism for \SEDP, uses the $\delta$-decreasing, $\epsilon$-accurate algorithm solving the convex optimization problem \eqref{eq:primal}. The construction follows a methodology employed by \citeN{Chen} and \citeN{singer-influence} to construct deterministic, truthful mechanisms for \textsc{Knapsack} and \textsc{Coverage} respectively, which we first describe below. +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 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. %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 relaxation of $OPT$ is computed over all elements excluding $i^*$. The outcome of this relaxation 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 relaxation used within a constant approximation of $OPT$, the above allocation can be shown to have a constant approximation. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and can be solved exactly in weakly polynomial time. The challenge in our setting is dealing with a convex relaxationsolved by an $\epsilon$-accurate, $\delta$-decreasing algorithm. In our setting, this yields a $\delta$-truthful, constant approximation mechanism. +Provided that the relaxation used within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and thus their optimal values are monotone and can be computed exactly in weakly polynomial time. In contrast, we extend these results by showing 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. -To obtain this result, we use the following modified version of Myerson's theorem, whose proof can be found in Appendix~\note{FIXME!!!} +To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\note{FIXME!!!} % %Instead, \citeN{singer-mechanisms} and \citeN{chen} %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the @@ -59,7 +59,7 @@ To obtain this result, we use the following modified version of Myerson's theore \begin{lemma}\label{thm:myerson-variant} \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is $\delta$-truthful if: -(a) $S$ is $\delta$-decreasing, \emph{i.e.}, for any agent $i$ and $c_i' \leq +(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) @@ -68,18 +68,17 @@ c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) \begin{algorithm}[t] \caption{Mechanism for \SEDP{}}\label{mechanism} \begin{algorithmic}[1] - \State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$ + %\State $\mathcal{N} \gets \mathcal{N}\setminus\{i\in\mathcal{N} : c_i > B\}$ + \Require{ $B\in \reals_+$,$c\in[0,B]^n$, $\delta\in (0,1]$, $\epsilon\in (0,1]$ } \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$ \State $OPT'_{-i^*} \gets$ using Proposition~\ref{prop:monotonicity}, compute a $\varepsilon$-accurate, $\delta$-decreasing - approximation of $\max_{\lambda\in[0,1]^{n}} \{L(\lambda) - \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$ + approximation of $$\textstyle L^*_{c_{-i^*}}\defeq\max_{\lambda\in[0,1]^{n}} \{L(\lambda) + \mid \lambda_{i^*}=0,\sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$$ \Statex - \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c} - \State \textbf{return} $\{i^*\}$ + \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c} \textbf{return} $\{i^*\}$ \Else - \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$ - \State $S_G \gets \emptyset$ + \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$; $S_G \gets \emptyset$ \While{$c_i\leq \frac{B}{2}\frac{V(S_G\cup\{i\})-V(S_G)}{V(S_G\cup\{i\})}$} \State $S_G \gets S_G\cup\{i\}$ \State $i \gets \argmax_{j\in\mathcal{N}\setminus S_G} @@ -92,15 +91,13 @@ c_{-i})$ implies $i\in S(c_i', c_{-i})$, and (b) \fussy Our mechanism for \EDP{} is composed of -\begin{itemize} -\item the allocation function presented in Algorithm~\ref{mechanism}, and -\item the payment function which pays each allocated agent $i$ her threshold +(a) the allocation function presented in Algorithm~\ref{mechanism}, and +(b) the payment function which pays each allocated agent $i$ her threshold payment as described in Myerson's Theorem. In the case where $\{i^*\}$ is the -allocated set, her threshold payment is $B$ (she would be have been dropped on -line 1 of Algorithm~\ref{mechanism} had she reported a higher cost). +allocated set, her threshold payment is $B$. %(she would be have been dropped on +%line 1 of Algorithm~\ref{mechanism} had she reported a higher cost). A closed-form formula for threshold payments when $S_G$ is the allocated set can be found in~\cite{singer-mechanisms}. -\end{itemize} We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}: \begin{theorem}\label{thm:main} diff --git a/problem.tex b/problem.tex index 6f07d29..033c7e1 100644 --- a/problem.tex +++ b/problem.tex @@ -100,7 +100,7 @@ In the full-information case, the experiment costs are common knowledge; as such \text{subject to}\quad \sum_{i\in S} c_i&\leq B \end{align}\label{edp} \end{subequations} -We denote by +\emph{W.l.o.g.}, we assume that $c_i\in [0,B]$ for all $i\in \mathcal{N}$, as no $i$ with $c_i>B$ can be in $S$. We denote by \begin{equation}\label{eq:non-strategic} OPT = \max_{S\subseteq\mathcal{N}} \Big\{V(S) \;\Big| \; \sum_{i\in S}c_i\leq B\Big\} @@ -141,7 +141,7 @@ yields an approximation ratio of $\frac{5 e }{e-1}~$\cite{singer-mechanisms}; t \subsection{Budget-Feasible Experimental Design: Strategic Case} -Rather than the above full information case, we study the strategic case, in which the costs $c_i$ are {\em not} common knowledge and their reporting can be manipulated by the experiment subjects. The latter are strategic and wish to maximize their utility, which is the difference of the payment they receive and their true cost. We note that, though subjects may misreport $c_i$, they cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement). +We study the following \emph{strategic} setting, in which the costs $c_i$ are {\em not} common knowledge and their reporting can be manipulated by the experiment subjects. The latter are strategic and wish to maximize their utility, which is the difference of the payment they receive and their true cost. We note that, though subjects may misreport $c_i$, they cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement). %The subjects report $c_i$ in order to maximize their expected {\em utility} which is $p_i-c_i$. @@ -205,6 +205,7 @@ Ideally, we would like the allocation $S$ to be of maximal value; however, truth should be computable in time polynomial in various parameters. %time in the number of agents $n$. %\thibaut{Should we say something about the black-box model for $V$? Needed to say something in general, but not in our case where the value function can be computed in polynomial time}. \end{itemize} +%\emph{W.l.o.g.}, we assume in the sequel that costs are at most $B$, \emph{i.e.}, $c_i\in[0,B]$, for all $i\in \mathcal{N}$. This is because, by individual rationality, any $i$ for which $c_i>B$ clearly cannot be allocated; as such, any mechanism that satisfies the above properties ignores such subjects. \begin{comment} As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one |