Add proof of Myerson's lemma. Introduce the counterexample in the body.

1 files changed, 7 insertions, 6 deletions

diff --git a/counterexample.tex b/counterexample.tex
index 95f6a45..896d672 100644
--- a/counterexample.tex
+++ b/counterexample.tex
@@ -1,7 +1,7 @@
-We give a counterxample of the monotonicity of the maximum allocation rule
-defined in \eqref{eq:max-algorithm} for the value function $V$ defined in
-\eqref{obj}. We denote by $(e_1, e_2, e_3)$ the canonical basis of $\reals^3$
-and define the following feature vectors: $x_1=e_1$,
+We give a counterxample of the truthfulness of the maximum mechanism whose
+allocation rule is defined in \eqref{eq:max-algorithm} when the value function
+$V$ is as defined in \eqref{obj}. We denote by $(e_1, e_2, e_3)$ the canonical
+basis of $\reals^3$ and define the following feature vectors: $x_1=e_1$,
 $x_2=\frac{1}{\sqrt{2}}\cos\frac{\pi}{5}e_2
 + \frac{1}{\sqrt{2}}\sin\frac{\pi}{5}e_3$, $x_3=\frac{1}{\sqrt{2}}e_2$ and $x_4
 = \frac{1}{2}e_3$, with associated costs $c_1 = \frac{5}{2}$, $c_2=c_3 = 1$ and
@@ -41,7 +41,7 @@ the set $\{x_2, x_3\}$ with value:
 In contrast, $V(x_1) \simeq 0.693$ so the mechanism will allocate to $\{x_2,
 x_3\}$.
 
-Let us now assume that user $3$ reduces her cost. It comes from
+Let us now assume that user $3$ reduces her cost. It follows from
 \eqref{eq:local-bazinga} that the greedy heuristic will start by adding her to
 the greedy solution. Furthermore:
 \begin{displaymath}
@@ -58,4 +58,5 @@ Hence, the greedy solution will be $\{x_3, x_4\}$ with value:
 \end{displaymath}
 As a consequence the mechanism will allocate to user $1$ in this case. By
 reducing her cost, user 3, who was previously allocated, is now rejected by the
-mechanism. This contradicts its monotonicity.
+mechanism. This contradicts the monotonicity of the allocation rule, hence its
+truthfulness by Myerson's theorem \cite{myerson}.