diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 239 |
1 files changed, 230 insertions, 9 deletions
@@ -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. We briefly outline this below (see \cite{arxiv} 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. 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 @@ -24,7 +24,7 @@ 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}. +To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}. \begin{lemma}\label{thm:myerson-variant} A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is @@ -35,14 +35,51 @@ 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: +\input{myerson} + +\begin{algorithm} + \caption{Mechanism for \SEDP{}}\label{mechanism} + \begin{algorithmic}[1] + %\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 \label{relaxexec}$OPT'_{-i^*} \gets$ using Proposition~\ref{prop:monotonicity}, + compute a $\varepsilon$-accurate, $\delta$-decreasing + 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 + \State $C \gets \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}$ -%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. + \If{$OPT'_{-i^*} < C \cdot V(i^*)$} \label{c} + \State \textbf{return} $\{i^*\}$ + \Else + \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$ + \State $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} + \frac{V(S_G\cup\{j\})-V(S_G)}{c_j}$ + \EndWhile + \State \textbf{return} $S_G$ + \EndIf + \end{algorithmic} +\end{algorithm} + +Lemma~\ref{thm:myerson-variant} allows us to incorporate our relaxation in the +above framework. Our mechanism for \EDP{} is composed of +(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 (see Lemma~\ref{thm:myerson-variant}). 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). +A closed-form formula for threshold payments when $S_G$ is the allocated set can +be found in~\cite{singer-mechanisms}. The guarantees of the resulting mechanism +are summarized in the following Theorem. \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 + For any $\delta\in(0,1]$, and any $\epsilon\in (0,1]$, the mechanism + described in Algorithm~\ref{mechanism} is $\delta$-truthful, individually rational + and budget feasible mechanim for \EDP{}. Furthermore, it runs in time $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$ and allocates a set $S^*$ such that @@ -52,11 +89,195 @@ above framework, yielding the following theorem: \varepsilon \simeq 12.98V(S^*) + \varepsilon. \end{displaymath} -Furthemore, there is no $2$-approximate, truthful, budget feasible, individually rational +\end{theorem} + +A corresponding lower bound is given by the following theorem. + +\begin{theorem} +There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP. \end{theorem} -The detailed description of our proposed mechanism as well as the proof of the theorem can be found in \cite{arxiv}. +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^*}$ to denote +the approximation computed by the $\delta$-decreasing, $\epsilon$-accurate +approximation of $L^*_{c_{-i^*}}$, as defined in Algorithm~\ref{alg:monotone}. + + +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} + The mechanism for \EDP{} described in Algorithm~\ref{mechanism} is + $\delta$-monotone and budget feasible. +\end{lemma} + +\begin{proof} + Consider an agent $i$ with cost $c_i$ that is + selected by the mechanism, and suppose that she reports + a cost $c_i'\leq c_i-\delta$ while all other costs stay the same. + Suppose that when $i$ reports $c_i$, $OPT'_{-i^*} \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$. + By reporting cost $c_i'$, $i$ may be selected at an earlier iteration of the greedy algorithm. + %using the submodularity of $V$, we see that $i$ will satisfy the greedy + %selection rule: + %\begin{displaymath} + % i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\}) + % - V(S)}{c_j} + %\end{displaymath} + %in an earlier iteration of the greedy heuristic. + Denote by $S_i$ + (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$ + (resp. $c_i'$). We have $S_i'\subseteq S_i$; in addition, $S_i'\subseteq S_G'$, the set selected by the greedy algorithm under $(c_i',c_{-i})$; if not, then greedy selection would terminate prior to selecting $i$ also when she reports $c_i$, a contradiction. Moreover, we have + \begin{align*} + c_i' & \leq c_i \leq + \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})} + \leq \frac{B}{2}\frac{V(S_i'\cup\{i\})-V(S_i')}{V(S_i'\cup\{i\})} + \end{align*} + by the monotonicity and submodularity of $V$. Hence $i\in S_G'$. By + $\delta$-decreasingness of + $OPT'_{-i^*}$, under $c'_i\leq c_i-\delta$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$. + Suppose now that when $i$ reports $c_i$, $OPT'_{-i^*} < C V(i^*)$. Then $s_i(c_i,c_{-i})=1$ iff $i = i^*$. + Reporting $c_{i^*}'\leq c_{i^*}$ does not change $V(i^*)$ nor + $OPT'_{-i^*} \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone. + +To show budget feasibility, suppose that $OPT'_{-i^*} < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible. +Suppose that $OPT'_{-i^*} \geq C V(i^*)$. +Denote by $S_G$ the set selected by the greedy algorithm, and for $i\in S_G$, denote by +$S_i$ the subset of the solution set that was selected by the greedy algorithm just prior to the addition of $i$---both sets determined for the present cost vector $c$. +%Chen \emph{et al.}~\cite{chen} show that, +Then for any submodular function $V$, and for all $i\in S_G$: +%the reported cost of an agent selected by the greedy heuristic, and holds for +%any submodular function $V$: +\begin{equation}\label{eq:budget} + \text{if}~c_i'\geq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B~\text{then}~s_i(c_i',c_{-i})=0 +\end{equation} +In other words, if $i$ increases her cost to a value higher than $\frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)}$, she will cease to be in the selected set $S_G$. As a result, +\eqref{eq:budget} +implies that the threshold payment of user $i$ is bounded by the above quantity. +%\begin{displaymath} +%\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} = B +%\end{displaymath} +Hence, the total payment is bounded by the telescopic sum: +\begin{displaymath} + \sum_{i\in S_G} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B = \frac{V(S_G)-V(\emptyset)}{V(S_G)} B=B\qedhere +\end{displaymath} +\end{proof} + +The complexity of the mechanism is given by the following lemma. + +\begin{lemma}[Complexity]\label{lemma:complexity} + For any $\varepsilon > 0$ and any $\delta>0$, the complexity of the + mechanism described in Algorithm~\ref{mechanism} is + $O\big(poly(n, d, \log\log\frac{B}{b\varepsilon\delta})\big)$. +\end{lemma} + +\begin{proof} + The value function $V$ in \eqref{modified} can be computed in time + $O(\text{poly}(n, d))$ and the mechanism only involves a linear + number of queries to the function $V$. + By Proposition~\ref{prop:monotonicity}, line \ref{relaxexec} of Algorithm~\ref{mechanism} + can be computed in time + $O(\text{poly}(n, d, \log\log \frac{B}{b\varepsilon\delta}))$. Hence the allocation + function's complexity is as stated. + %Payments can be easily computed in time $O(\text{poly}(n, d))$ as in prior work. +\junk{ + Using Singer's characterization of the threshold payments + \cite{singer-mechanisms}, one can verify that they can be computed in time + $O(\text{poly}(n, d))$. + } +\end{proof} + +Finally, we prove the approximation ratio of the mechanism. +We use the following lemma from \cite{chen} which bounds $OPT$ in terms of +the value of $S_G$, as computed in Algorithm \ref{mechanism}, and $i^*$, the +element of maximum value. + +\begin{lemma}[\cite{chen}]\label{lemma:greedy-bound} +Let $S_G$ be the set computed in Algorithm \ref{mechanism} and let +$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$. We have: +\begin{displaymath} +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 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 +$S^*$ allocated by the mechanism is such that: +\begin{equation} \label{approxbound} +OPT +\leq \frac{10e\!-\!3 + \sqrt{64e^2\!-\!24e\!+\!9}}{2(e\!-\!1)} V(S^*)\! ++ \! \varepsilon . +\end{equation} +\begin{proof} +Let $L^*_{c_{-i^*}}$ be the maximum value of $L$ subject to +$\lambda_{i^*}=0$, $\sum_{i\in \mathcal{N}\setminus{i^*}}c_i\leq B$. From line +\ref{relaxexec} of Algorithm~\ref{mechanism}, we have +$L^*_{c_{-i^*}}-\varepsilon\leq OPT_{-i^*}' \leq L^*_{c_{-i^*}}+\varepsilon$. +If the condition on line \ref{c} of the algorithm holds then, from the lower bound in Proposition~\ref{prop:relaxation}, +\begin{displaymath} + V(i^*) \geq \frac{1}{C}L^*_{c_{-i^*}}-\frac{\varepsilon}{C} \geq + \frac{1}{C}OPT_{-i^*} -\frac{\varepsilon}{C}. +\end{displaymath} +Also, $OPT \leq OPT_{-i^*} + V(i^*)$, +hence, +\begin{equation}\label{eq:bound1} + OPT\leq (1+C)V(i^*) + \varepsilon. +\end{equation} +If the condition on line \ref{c} does not hold, by observing that $L^*_{c_{-i^*}}\leq L^*_c$ and +the upper bound of Proposition~\ref{prop:relaxation}, we get +\begin{displaymath} + V(i^*)\leq \frac{1}{C}L^*_{c_{-i^*}} + \frac{\varepsilon}{C} + \leq \frac{1}{C} \big(2 OPT + 2 V(i^*)\big) + \frac{\varepsilon}{C}. +\end{displaymath} +Applying Lemma~\ref{lemma:greedy-bound}, +\begin{displaymath} + V(i^*) \leq \frac{1}{C}\left(\frac{2e}{e-1}\big(3 V(S_G) + + 2 V(i^*)\big) + 2 V(i^*)\right) + \frac{\varepsilon}{C}. +\end{displaymath} +Note that $C$ satifies $C(e-1) -6e +2 > 0$, hence +\begin{align*} + V(i^*) \leq \frac{6e}{C(e-1)- 6e + 2} V(S_G) + + \frac{(e-1)\varepsilon}{C(e-1)- 6e + 2}. +\end{align*} +Finally, using Lemma~\ref{lemma:greedy-bound} again, we get +\begin{equation}\label{eq:bound2} + OPT \leq + \frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2}\right) V(S_G) + + \frac{2e\varepsilon}{C(e-1)- 6e + 2}. +\end{equation} +Our choice of $C$, namely, +\begin{equation}\label{eq:constant} + C = \frac{8e-1 + \sqrt{64e^2-24e + 9}}{2(e-1)}, +\end{equation} + is precisely to minimize the maximum among the coefficients of $V_{i^*}$ and $V(S_G)$ in \eqref{eq:bound1} +and \eqref{eq:bound2}, respectively. Indeed, consider: +\begin{displaymath} + \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{4e}{C (e-1) -6e +2} + \right)\right). +\end{displaymath} +This function has two minima, only one of those is such that $C(e-1) -6e ++2 \geq 0$. This minimum is precisely \eqref{eq:constant}. +For this minimum, $\frac{2e\varepsilon}{C(e-1)- 6e + 2}\leq \varepsilon.$ +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 +\end{proof} +\begin{proof} +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 +be in the set selected by the mechanism, otherwise the ratio is unbounded, +a contradiction. If $x_1$ lowers its value to $B/2-\epsilon$, by monotonicity +it remains in the solution; by threshold payment, it is paid at least +$B/2+\epsilon$. So $x_2$ is not included in the solution by budget feasibility +and individual rationality: hence, the selected set attains a value $\log2$, +while the optimal value is $2\log 2$.\hspace*{\stretch{1}}\qed +\end{proof} |