diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 158 |
1 files changed, 58 insertions, 100 deletions
@@ -1,112 +1,70 @@ \label{sec:main} -In this section we present our mechanism for \SEDP. -\begin{comment} -Prior approaches to budget -feasible mechanisms for submodular maximization build upon the full information -case, which we discuss first. +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. -\subsection{Submodular Maximization in the Full Information Case} -In the full-information case, submodular maximization under a budget constraint -\eqref{eq:non-strategic} relies on a greedy heuristic in which elements are -added to the solution set according to the following greedy selection rule. -Assume that $S\subseteq\mathcal{N}$ is the set constructed thus far, the next -element $i$ to be included is the one which maximizes the -\emph{marginal-value-per-cost}: -\begin{align} - i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy} -\end{align} -This is repeated until the sum of costs of elements in $S$ reaches the budget -constraint $B$. Denote by $S_G$ the set constructed by this heuristic and let -$i^*=\argmax_{i\in\mathcal{N}} V(\{i\})$ be the element of maximum value. Then, -the following algorithm: -\begin{equation}\label{eq:max-algorithm} -\textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\} -\;\textbf{else return}\; S_G -\end{equation} -has a constant approximation ratio \cite{singer-mechanisms}. -\end{comment} +%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. -\subsection{Submodular Maximization in the Strategic Case} +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^*\}$. -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. +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. -Let us denote by $OPT_{-i^*}$ the optimal value achievable in the -full-information case after removing $i^*$ from the set $\mathcal{N}$: -\begin{equation}\label{eq:opt-reduced} - OPT_{-i^*} \defeq \max_{S\subseteq\mathcal{N}\setminus\{i^*\}} \Big\{V(S) \;\Big| \; - \sum_{i\in S}c_i\leq B\Big\} -\end{equation} -\citeN{singer-mechanisms} and \citeN{chen} prove that the following -allocation: -\begin{displaymath} -\textbf{if}\; V(\{i^*\}) \geq C \cdot OPT_{-i^*}\; \textbf{return}\; \{i^*\} -\;\textbf{else return}\; S_G -\end{displaymath} -yields a 8.34-approximation mechanism for an appropriate $C$ (see also -Algorithm~\ref{mechanism}). However, $OPT_{-i^*}$, the maximum value attainable -in the full-information case, cannot be computed in poly-time when the -underlying problem is NP-hard (unless P=NP), as is the case for \SEDP{}. +To obtain this result, we use the following modified version of Myerson's theorem, 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 +%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. -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. +%$\delta$-truthfulness will follow from $\delta$-monotonicity by the following +%variant of Myerson's theorem. \begin{lemma}\label{thm:myerson-variant} \sloppy A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is -$\delta$-truthful iff: +$\delta$-truthful if: (a) $S$ is $\delta$-decreasing, \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} - \begin{algorithm}[t] \caption{Mechanism for \SEDP{}}\label{mechanism} \begin{algorithmic}[1] @@ -144,25 +102,25 @@ 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: +We can now state our main result, which is proved in Appendix~\ref{sec:proofofmainthm}: \begin{theorem}\label{thm:main} \sloppy - For any $\delta$, the allocation described in Algorithm~\ref{mechanism}, + For any $\delta>0$ the allocation described in Algorithm~\ref{mechanism}, along with threshold payments, is $\delta$-truthful, individually rational and budget feasible. Furthermore, there exists an absolute constant $C$ such that, for any $\varepsilon>0$, the mechanism runs in time $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$ and returns a set $S^*$ such that: - \begin{align*} - OPT - & \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+ +% \begin{align*} + $ OPT + \leq \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} V(S^*)+ \varepsilon - \simeq 12.98V(S^*) + \varepsilon - \end{align*} + \simeq 12.98V(S^*) + \varepsilon.$ +% \end{align*} \end{theorem} The value of the constant $C$ is given by \eqref{eq:constant} in -Section~\ref{sec:proofofmainthm}. +Appendix~\ref{sec:proofofmainthm}. In addition, we prove the following simple lower bound. \begin{theorem}\label{thm:lowerbound} |