diff options
| -rw-r--r-- | main.tex | 60 |
1 files changed, 27 insertions, 33 deletions
@@ -196,8 +196,8 @@ The mechanism is monotone. \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$, all the other costs staying the same. - Suppose that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus\{i^*\}}(x^*) \geq C V(i^*)$; as $s_i(c_i,c_{-i})$, $i\in S_G$. + a cost $c_i'\leq c_i$ while all other costs stay the same. + Suppose that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus\{i^*\}}(x^*) \geq C V(i^*)$; then, as $s_i(c_i,c_{-i})=1$, $i\in S_G$. By reporting a cost $c_i'\leq 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: @@ -208,14 +208,14 @@ The mechanism is monotone. %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 greedily 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 + (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\})} + \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'$. Moreover, as $L_{\mathcal{N}\setminus \{i^*\}}(x^*)$ is the optimal value of \eqref{relax} under relaxation $L_{\mathcal{N}}$, reducing the costs can only increase this value, so under $c'_i\leq c_i$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$. - Suppose now that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus \{i^*\}}(x^*) < C V(i^*)$. Then $s_i(c_i,c_{-1})=1$ iff $i = i^*$. + by the monotonicity and submodularity of $V$. Hence $i\in S_G'$. As $L_{\mathcal{N}\setminus \{i^*\}}(x^*)$ is the optimal value of \eqref{relax} under relaxation $L_{\mathcal{N}}$, reducing the costs can only increase this value, so under $c'_i\leq c_i$ the greedy set is still allocated and $s_i(c_i',c_{-i}) =1$. + Suppose now that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus \{i^*\}}(x^*) < 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 $L_{\mathcal{N}\setminus \{i^*\}}(x^*) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. \end{proof} @@ -225,28 +225,24 @@ The mechanism is budget feasible. \end{lemma} \begin{proof} -Let us denote by $S_G$ the set selected by the greedy heuristic in the -mechanism of Algorithm~\ref{mechanism}. Let $i\in S_G$, let us also denote by -$S_i$ the solution set that was selected by the greedy heuristic before $i$ was -added. We use the following result from Chen et al. \cite{chen}, which bounds -the reported cost of an agent selected by the greedy heuristic, and holds for -any submodular function $V$: +Suppose that $L_{\mathcal{N}\setminus\{i^*\}}(x^*) < C V(i^*)$. Then the mechanism selects $i^*$; as the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible. +Suppose thus that $L_{\mathcal{N}\setminus\{i^*\}}(x^*) \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, 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} - c_i \leq \frac{V(S_i\cup\{i\}) - V(S)}{V(S_G)} B + \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} - -Assume now that our mechanism selects point $i^*$. In this case, his payment -his $B$ and the mechanism is budget-feasible. - -Otherwise, the mechanism selects the set $S_G$. In this case, \eqref{eq:budget} -shows that the threshold payment of user $i$ is bounded by: -\begin{displaymath} -\frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B -\end{displaymath} - -Hence, the total payment is bounded by: +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_M} \frac{V(S_i\cup\{i\}) - V(S_i)}{V(S_G)} B \leq B\qed + \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\qed \end{displaymath} \end{proof} @@ -262,10 +258,9 @@ Hence, the total payment is bounded by: The function $\log\det$ is concave and self-concordant (see \cite{boyd2004convex}), so for any $\varepsilon$, its maximum can be find - to a precision $\varepsilon$ in a number of iterations of Newton's method - $O(\log\log\varepsilon^{-1})$. Each iteration of Newton's method can be + to a precision $\varepsilon$ in $O(\log\log\varepsilon^{-1})$ of iterations of Newton's method. Each iteration can be done in time $O(\text{poly}(n, d))$. Thus, line 2 of - algorithm~\ref{mechanism}, can be computed in time + Algorithm~\ref{mechanism} can be computed in time $O(\text{poly}(n, d, \log\log \varepsilon^{-1}))$. \end{proof} @@ -275,11 +270,10 @@ $L_\mathcal{N}$. Its proof is our main technical contribution and is done in section \ref{sec:relaxation}. \begin{lemma}\label{lemma:relaxation} - We have: - \begin{displaymath} - OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B) + %\begin{displaymath} + $ OPT(L_\mathcal{N}, B) \leq 4 OPT(V,\mathcal{N},B) + 2\max_{i\in\mathcal{N}}V(i) - \end{displaymath} + %\end{displaymath} \end{lemma} \begin{lemma}\label{lemma:approx} |