diff options
Diffstat (limited to 'counterexample.tex')
| -rw-r--r-- | counterexample.tex | 13 |
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}. |