diff options
| -rw-r--r-- | main.tex | 28 |
1 files changed, 13 insertions, 15 deletions
@@ -133,10 +133,10 @@ The resulting mechanism for \EDP{} is presented in Algorithm~\ref{mechanism}. Th \caption{Mechanism for \EDP{}}\label{mechanism} \begin{algorithmic}[1] \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$ - \State $x^* \gets \argmax_{x\in[0,1]^{n}} \{L_{\mathcal{N}\setminus\{i^*\}}(x) - \mid c(x)\leq B\}$, with precision $\epsilon>0$ + \State $\xi \gets \argmax_{\lambda\in[0,1]^{n}} \{L_{\mathcal{N}\setminus\{i^*\}}(\lambda) + \mid \sum_{i \in \mathcal{N}\setminus\{i^*\}}c_i\lambda_i\leq B\}$, with precision $\epsilon>0$ \Statex - \If{$L_{\mathcal{N}\setminus\{i^*\}}(x^*) < C \cdot V(i^*)$} \label{c} + \If{$L_{\mathcal{N}\setminus\{i^*\}}(\xi) < 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}$ @@ -197,7 +197,7 @@ The mechanism is monotone. 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$ 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$. + Suppose that when $i$ reports $c_i$, $L_{\mathcal{N}\setminus\{i^*\}}(\xi) \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: @@ -214,10 +214,10 @@ The mechanism is monotone. \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'$. 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^*$. + by the monotonicity and submodularity of $V$. Hence $i\in S_G'$. As $L_{\mathcal{N}\setminus \{i^*\}}(\xi)$ 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^*\}}(\xi) < 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$. + $L_{\mathcal{N}\setminus \{i^*\}}(xi) \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$. \end{proof} \begin{lemma}\label{lemma:budget-feasibility} @@ -225,8 +225,8 @@ The mechanism is budget feasible. \end{lemma} \begin{proof} -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^*)$. +Suppose that $L_{\mathcal{N}\setminus\{i^*\}}(\xi) < 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^*\}}(\xi) \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 @@ -266,16 +266,14 @@ Hence, the total payment is bounded by the telescopic sum: Finally, we prove the approximation ratio of the mechanism. We use the following lemma, which gives an approximation ratio of the function -$L_\mathcal{N}$. Its proof is our main technical contribution and is done in -section \ref{sec:relaxation}. - +$L_\mathcal{N}$. \begin{lemma}\label{lemma:relaxation} %\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{lemma} - +Its proof is our main technical contribution, and can be found in Section \ref{sec:relaxation}. \begin{lemma}\label{lemma:approx} %C_{\textrm{max}} = \max\left(1+C,\frac{3e}{e-1}\left( 1 + \frac{8e}{C %(e-1) -10e +2}\right)\right) @@ -288,8 +286,8 @@ section \ref{sec:relaxation}. \end{lemma} \begin{proof} - We assume that on line 2 of algorithm~\ref{mechanism}, a quantity - $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L(x^*) \leq + Let $x^*\in [0,1]^{n-1}$ be the true maximizer of $L_{\mathcal{N}\setminus\{i^*\}}$ subject to the budget constraints. Assume that on line 2 of algorithm~\ref{mechanism}, a quantity + $\tilde{L}$ such that $\tilde{L}-\varepsilon\leq L_{\mathcal{N}\setminus {i^*}}(x^*) \leq \tilde{L}+\varepsilon$ has been computed (lemma~\ref{lemma:complexity} states that this can be done in a time within our complexity guarantee). |