diff options
| -rw-r--r-- | counterexample.tex | 13 | ||||
| -rw-r--r-- | main.tex | 2 | ||||
| -rw-r--r-- | myerson.tex | 28 | ||||
| -rw-r--r-- | paper.tex | 4 | ||||
| -rw-r--r-- | problem.tex | 5 |
5 files changed, 43 insertions, 9 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}. @@ -9,7 +9,7 @@ Recall from Section~\ref{sec:fullinfo} that $i^*\defeq \arg\max_{i\in \mathcal{N Provided that the relaxation used within a constant from $OPT$, the above allocation can be shown to also yield a constant approximation to $OPT$. Furthermore, this allocation combined with \emph{threshold payments}, the mechanism can be shown to be truthful when the relaxation is monotone. The relaxations used in \cite{chen,singer-influence} are linear programs, and thus their optimal values are monotone and can be computed exactly in weakly polynomial time. In contrast, we extend these results by showing that the convex relaxation \eqref{eq:primal}, which can be solved by an $\epsilon$-accurate, $\delta$-decreasing algorithm, can be used to construct a $\delta$-truthful, constant approximation mechanism. -To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\note{FIXME!!!} +To obtain this result, we use the following modified version of Myerson's theorem \cite{myerson}, whose proof can be found in Appendix~\ref{sec:myerson}. % %Instead, \citeN{singer-mechanisms} and \citeN{chen} %suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the diff --git a/myerson.tex b/myerson.tex index 8b13789..bcfedc4 100644 --- a/myerson.tex +++ b/myerson.tex @@ -1 +1,29 @@ +Using the notations of Lemma~\ref{thm:myerson-variant}, we want to prove that +if $c_i$ and $c_i'$ are two different costs reported by user $i$ with $|c_i +- c_i'|\geq \delta$, and if $c_{-i}$ is any vector of costs reported by the +other users: +\begin{equation}\label{eq:local-foobar} + p_i(c_i, c_{-i}) - s_i(c_i, c_{-i})\cdot c_i \geq p_i(c_i', c_{-i}) + - s_i(c_i', c_{-i})\cdot c_i +\end{equation} +We distinguish four cases depending on the value of $s_i(c_i, c_{-i})$ and +$s_i'(c_i', c_{-i})$. + +Since the mechanism is normalized, if $s_i(c_i, c_{-i})= s_i(c_i', c_{-i})=0$, +we have $p_i(c_i, c_{-i}) = p_i(c_i', c_{-i})= 0$ and \eqref{eq:local-foobar} +is true. + +Note that $i$ is paid her threshold payment when allocated, and since this +payment does not depend on $i$'s reported cost, \eqref{eq:local-foobar} is true +(and is in fact an equality) when $s_i(c_i', c_{-i}) = s_i(c_i, c_{-i}) = 1$. + +If $s_i(c_i', c_{-i}) = 0$ and $s_i(c_i, c_{-i}) = 1$, we have $p_i(c_i', +c_{-i}) = 0$ by normalization and \eqref{eq:local-foobar} follows from +individual rationality. + +Finally, let us assume that $s_i(c_i', c_{-i}) = 1$ and $s_i(c_i, c_{-i}) = 0$. +By $\delta$-decreasingness of $s_i$, $c_i \geq c_i'+\delta$, and $s_i(c_i, +c_{-i}) = 0$ implies that $i$'s threshold payment is less than $c_i$, +\emph{i.e.} $p_i(c_i', c_{-i}) \leq c_i$. This last inequality is equivalent to +\eqref{eq:local-foobar} in this final case. @@ -41,10 +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{Non-Truthfulness of the Maximum Mechanism}\label{sec:non-monotonicity} +\input{counterexample} \section{Extensions}\label{sec:ext} \input{general} diff --git a/problem.tex b/problem.tex index 033c7e1..0b10107 100644 --- a/problem.tex +++ b/problem.tex @@ -207,6 +207,11 @@ Ideally, we would like the allocation $S$ to be of maximal value; however, truth \end{itemize} %\emph{W.l.o.g.}, we assume in the sequel that costs are at most $B$, \emph{i.e.}, $c_i\in[0,B]$, for all $i\in \mathcal{N}$. This is because, by individual rationality, any $i$ for which $c_i>B$ clearly cannot be allocated; as such, any mechanism that satisfies the above properties ignores such subjects. +Note that the algorithm given in \eqref{eq:max-algorithm} cannot be used in the +strategic case. Indeed, it is known that using the MAX operator breaks +truthfulness in general. A counterexample for the specific value function $V$ +defined in \eqref{obj} is provided in Appendix~\ref{sec:non-monotonicity}. + \begin{comment} As noted in \cite{singer-mechanisms, chen}, budget feasible reverse auctions are \emph{single parameter} auctions: each agent has only one private value (namely, $c_i$). As such, Myerson's Theorem \cite{myerson} gives |