diff options
| -rw-r--r-- | proof.tex | 54 |
1 files changed, 50 insertions, 4 deletions
@@ -205,7 +205,8 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$: \begin{displaymath} \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)} \sim_{\lambda\rightarrow 0} - \frac{\sum_{i\in S}\partial_i F_\mathcal{N}(0)}{\sum_{i\in S}\partial_i L_\mathcal{N}(0)} + \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F_\mathcal{N}(0)} + {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L_\mathcal{N}(0)} \end{displaymath} and that an interior critical point of the ratio $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$ is defined by: @@ -324,8 +325,8 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$: \begin{lemma} \begin{displaymath} - OPT(L_\mathcal{N}, B) \leq \frac{1}{C}OPT(V,\mathcal{N},B) - + \max_{i\in\mathcal{N}}V(i) + OPT(L_\mathcal{N}, B) \leq \frac{1}{C_\kappa}\big(2 OPT(V,\mathcal{N},B) + + \max_{i\in\mathcal{N}}V(i)\big) \end{displaymath} \end{lemma} @@ -362,10 +363,55 @@ The mechanism is budget feasible. \begin{lemma} Let us denote by $S_M$ the set returned by the mechanism. Then: \begin{displaymath} - V(S_M) \geq C\cdot OPT(V, \mathcal{N}, B) + V(S_M) \geq ?\cdot OPT(V, \mathcal{N}, B) \end{displaymath} \end{lemma} +\begin{proof} + + If the condition on line 3 of the algorithm holds, then: + \begin{displaymath} + V(i^*) \geq \frac{1}{C}L(x^*) \geq + \frac{1}{C}OPT(V,\mathcal{N}\setminus\{i\}, B) + \end{displaymath} + + But: + \begin{displaymath} + OPT(V,\mathcal{N},B) \leq OPT(V,\mathcal{N}\setminus\{i\}, B) + V(i^*) + \end{displaymath} + + Hence: + \begin{displaymath} + V(i^*) \geq \frac{C}{C+1} OPT(V,\mathcal{N}, B) + \end{displaymath} + + If the condition of the algorithm does not hold: + \begin{align*} + V(i^*) & \leq \frac{1}{C}L(x^*) \leq \frac{1}{C\cdot C_\kappa} + \big(2 OPT(V,\mathcal{N}, B) + V(i^*)\big)\\ + & \leq \frac{1}{C\cdot C_\kappa}\left(\frac{2e}{e-1}\big(3 V(S_M) + + 2 V(i^*)\big) + + V(i^*)\right) + \end{align*} + + Thus: + \begin{align*} + V(i^*) \leq \frac{6e}{C\cdot C_\kappa(e-1)- 5e + 1} V(S_M) + \end{align*} + + Finally, using again that: + \begin{displaymath} + OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big(3 V(S_M) + 2 V(i^*)\big) + \end{displaymath} + + We get: + \begin{displaymath} + OPT(V, \mathcal{N}, B) \leq \frac{e}{e-1}\left( 3 + \frac{12e}{C\cdot + C_\kappa(e-1) -5e +1}\right) V(S_M) + \end{displaymath} + +\end{proof} + \begin{theorem} The mechanism is individually rational, truthful and has an approximation ratio of |