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
60
61
|
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$,
$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
$c_4=\frac{2}{3}$. We also assume that the budget of the auctioneer is
$B=\frac{5}{2}$.
Note that $V(x_i) = \log(1+\|x_i\|^2)$, so $x_1$ is the point of maximum value.
Let us now compute the output of the greedy heuristic. We have:
\begin{equation}\label{eq:local-bazinga}
\frac{V(x_1)}{c_1} \simeq 0.277,\;
\frac{V(x_2)}{c_2}= \frac{V(x_3)}{c_3} \simeq 0.405,\;
\frac{V(x_4)}{c_4} \simeq 0.335
\end{equation}
so the greedy heuristic will start by selecting $x_2$ or $x_3$. Without loss of
generality, we can assume that it selected $x_2$. From the Sherman-Morrison
formula we get:
\begin{displaymath}
V(\{x_i, x_j\}) - V(x_i) = \log\bigg(1+ \|x_j\|^2
- \frac{\ip{x_i}{x_j}^2}{1+\|x_i\|^2}\bigg)
\end{displaymath}
In particular, when $x_i$ and $x_j$ are orthogonal $V(\{x_i, x_j\}) = V(x_j)$.
This allows us to compute:
\begin{displaymath}
\frac{V(\{x_2,x_3\})-V(x_2)}{c_3}=\log\bigg(1+\frac{1}{2}
- \frac{1}{6}\cos^2\frac{\pi}{5}\bigg)\simeq 0.329
\end{displaymath}
\begin{displaymath}
\frac{V(\{x_2,x_4\})-V(x_2)}{c_4}=\frac{3}{2}\log\bigg(1+\frac{1}{4}
- \frac{1}{12}\sin^2\frac{\pi}{5}\bigg)\simeq 0.299
\end{displaymath}
Note that at this point $x_1$ cannot be selected without exceding the budget.
Hence, the greedy heuristic will add $x_3$ to the greedy solution and returns
the set $\{x_2, x_3\}$ with value:
\begin{displaymath}
V(\{x_2, x_3\}) = V(x_2) + V(\{x_2, x_3\}) - V(x_2)\simeq 0.734
\end{displaymath}
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
\eqref{eq:local-bazinga} that the greedy heuristic will start by adding her to
the greedy solution. Furthermore:
\begin{displaymath}
\frac{V(\{x_3,x_2\})-V(x_3)}{c_2}=\log\bigg(1+\frac{1}{2}
- \frac{1}{6}\cos^2\frac{\pi}{5}\bigg)\simeq 0.329
\end{displaymath}
\begin{displaymath}
\frac{V(\{x_3,x_4\})-V(x_3)}{c_4}
=\frac{3}{2}\log\bigg(1+\frac{1}{4}\bigg)\simeq 0.334
\end{displaymath}
Hence, the greedy solution will be $\{x_3, x_4\}$ with value:
\begin{displaymath}
V(\{x_3, x_4\}) = V(x_3) + V(\{x_3, x_4\}) - V(x_3)\simeq 0.628
\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.
|
