Adding counterexample

3 files changed, 68 insertions, 2 deletions

diff --git a/counterexample.tex b/counterexample.tex
new file mode 100644
index 0000000..95f6a45
--- /dev/null
+++ b/counterexample.tex
@@ -0,0 +1,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.
diff --git a/myerson.tex b/myerson.tex
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/myerson.tex
@@ -0,0 +1 @@
+
diff --git a/paper.tex b/paper.tex
index 4b21d00..3ff5607 100644
--- a/paper.tex
+++ b/paper.tex
@@ -10,11 +10,11 @@
 \usepackage[pagebackref=true,breaklinks=true,colorlinks=true]{hyperref}
 \title{Budget Feasible Mechanisms for Experimental Design}
 \author{
-    Thibaut Horel\\École Normale Supérieure\\\texttt{thibaut.horel@ens.fr}
+    Thibaut Horel\\École Normale Supérieure\\\texttt{thibaut.horel@normalesup.org}
     \and
     Stratis Ioannidis\\Technicolor\\\texttt{stratis.ioannidis@technicolor.com}
     \and
-    S. Muthukrishnan\\Rutgers University\\\texttt{muthu@cs.rutgers.edu}
+    S. Muthukrishnan\\Rutgers University--Microsoft Research\\\texttt{muthu@cs.rutgers.edu}
 }
 
 \begin{document}
@@ -41,6 +41,10 @@
 \bibliography{notes}
 \appendix
 \input{appendix}
+\section{Non-Monotonicity of the Maximum Allocation Rule}\label{sec:monotonicity}
+\input{counterexample}
+\section{Proof of Lemma~\ref{thm:myerson-variant}}\label{sec:myerson}
+\input{myerson}
 \section{Extensions}\label{sec:ext}
 \input{general}