diff options
| -rw-r--r-- | proof.tex | 29 |
1 files changed, 25 insertions, 4 deletions
@@ -8,6 +8,7 @@ \newtheorem{fact}{Fact} \newtheorem{example}{Example} \newtheorem{prop}{Proposition} +\newtheorem{theorem}{Theorem} \newcommand{\var}{\mathop{\mathrm{Var}}} \newcommand{\condexp}[2]{\mathop{\mathbb{E}}\left[#1|#2\right]} \newcommand{\expt}[1]{\mathop{\mathbb{E}}\left[#1\right]} @@ -172,8 +173,8 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$: Thus, $F_\lambda$ is a degree 2 polynomial whose dominant coefficient is: \begin{multline*} \frac{c_i}{c_j}\mathbb{E}_{S'\sim P_{\mathcal{N}\setminus\{i,j\}}(S',\lambda)}\Big[ - V(S'\cup\{i\})+f(S'\cup\{i\})\\ - -V(S'\cup\{i,j\})-f(S')\Big] + V(S'\cup\{i\})+V(S'\cup\{i\})\\ + -V(S'\cup\{i,j\})-V(S')\Big] \end{multline*} which is positive by submodularity of $V$. Hence, the maximum of $F_\lambda$ over the interval given in \eqref{eq:convex-interval} is @@ -335,10 +336,10 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$: \State $x^* \gets \argmax_{x\in[0,1]^n} \{L_{\mathcal{N}\setminus\{i^*\}}(x) \,|\, c(x)\leq\frac{B}{2}\}$ \Statex - \If{$L(x^*) < CV(\{i^*\})$} + \If{$L(x^*) < CV(i^*)$} \State \textbf{return} $\{i^*\}$ \Else - \State $i \gets \argmax_{1\leq j\leq n}\frac{V(\{j\})}{c_j}$ + \State $i \gets \argmax_{1\leq j\leq n}\frac{V(j)}{c_j}$ \State $S \gets \emptyset$ \While{$c_i\leq \frac{B}{2}\frac{V(S\cup\{i\})-V(S)}{V(S\cup\{i\})}$} \State $S \gets S\cup\{i\}$ @@ -349,4 +350,24 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$: \EndIf \end{algorithmic} \end{algorithm} + +\begin{lemma} +The mechanism is monotone. +\end{lemma} + +\begin{lemma} +The mechanism is budget feasible. +\end{lemma} + +\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) + \end{displaymath} +\end{lemma} + +\begin{theorem} + The mechanism is individually rational, truthful and has an approximation + ratio of +\end{theorem} \end{document} |