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
|
\begin{proof}
We want to prove that
if $c_i$ and $c_i'$ are two different costs reported by user $i$ with $|c_i
- c_i'|\geq \delta$, and if $c_{-i}$ is any vector of costs reported by the
other users:
\begin{equation}\label{eq:local-foobar}
p_i(c_i, c_{-i}) - s_i(c_i, c_{-i})\cdot c_i \geq p_i(c_i', c_{-i})
- s_i(c_i', c_{-i})\cdot c_i
\end{equation}
We distinguish four cases depending on the value of $s_i(c_i, c_{-i})$ and
$s_i'(c_i', c_{-i})$.
\begin{enumerate}
\item $s_i(c_i, c_{-i})= s_i(c_i', c_{-i})=0$.
Since the mechanism is normalized
we have $p_i(c_i, c_{-i}) = p_i(c_i', c_{-i})= 0$ and \eqref{eq:local-foobar}
is true.
\item $s_i(c_i', c_{-i}) = s_i(c_i, c_{-i}) = 1$.
Note that $i$ is paid her threshold payment when allocated, and since this
payment does not depend on $i$'s reported cost, \eqref{eq:local-foobar} is true
(and is in fact an equality).
\item $s_i(c_i', c_{-i}) = 0$ and $s_i(c_i, c_{-i}) = 1$.
We then have $p_i(c_i',
c_{-i}) = 0$ by normalization and \eqref{eq:local-foobar} follows from
individual rationality.
\item $s_i(c_i', c_{-i}) = 1$ and $s_i(c_i, c_{-i}) = 0$.
By $\delta$-decreasingness of $s_i$, $c_i \geq c_i'+\delta$, and $s_i(c_i,
c_{-i}) = 0$ implies that $i$'s threshold payment is less than $c_i$,
\emph{i.e.} $p_i(c_i', c_{-i}) \leq c_i$. This last inequality is equivalent to
\eqref{eq:local-foobar} in this final case. \qed
\end{enumerate}
\end{proof}
|
