From 9b26f56120422dec9537505f3971ce67dd46c68f Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sat, 6 Jul 2013 15:54:48 +0200 Subject: Add proof of Myerson's lemma. Introduce the counterexample in the body. --- counterexample.tex | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) (limited to 'counterexample.tex') 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}. -- cgit v1.2.3-70-g09d2