1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
\begin{lemma}\label{lemma:monotone}
Our mechanism for \EDP{} is monotone and budget feasible.
\end{lemma}
\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$ while all other costs stay the same.
Suppose that when $i$ reports $c_i$, $OPT'_{-i^*} \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:
%\begin{displaymath}
% i = \argmax_{j\in\mathcal{N}\setminus S} \frac{V(S\cup\{j\})
% - V(S)}{c_j}
%\end{displaymath}
%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 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\})}
\end{align*}
by the monotonicity and submodularity of $V$. Hence $i\in S_G'$. As
$OPT'_{-i^*}$, is the optimal value of \eqref{eq:primal} under relaxation $L$ when $i^*$ is excluded from $\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$, $OPT'_{-i^*} < 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
$OPT'_{-i^*} \leq C V(i^*)$; thus $s_{i^*}(c_{i^*}',c_{-i^*})=1$, so the mechanism is monotone.
%\end{proof}
%\begin{lemma}\label{lemma:budget-feasibility}
%The mechanism is budget feasible.
%\end{lemma}
%\begin{proof}
To show budget feasibility, suppose that $OPT'_{-i^*} < C V(i^*)$. Then the mechanism selects $i^*$. Since the bid of $i^*$ does not affect the above condition, the threshold payment of $i^*$ is $B$ and the mechanism is budget feasible.
Suppose that $OPT'_{-i^*} \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,
Then 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}
\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}
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_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}
|
