From de119c1bfc64a0c34fa4239b8c50a80c08244d94 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Wed, 31 Oct 2012 18:58:14 +0100 Subject: Add the properties we seek for mechanisms. Add Myerson's theorem. --- main.tex | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) (limited to 'main.tex') diff --git a/main.tex b/main.tex index 324c2f8..53de028 100644 --- a/main.tex +++ b/main.tex @@ -125,12 +125,11 @@ We can now state the main result of this section: \begin{proof} \emph{Truthfulness.} The algorithm only describes the allocation rule. -However, it suffices to prove that the mechanism is monotone, then -Myerson's theorem (see TODO) ensures us that by paying each allocated -user his threshold payment yields a truthful mechanism. The proof of -the monotonicity has already been done in \cite{singer-influence} and -is given here in lemma~\ref{lemma:monotone} below for the sake of -completeness. +However, it suffices to prove that the mechanism is monotone, then Myerson's +theorem (see theorem~\ref{thm:myerson}) ensures us that by paying each +allocated user his threshold payment yields a truthful mechanism. The proof of +the monotonicity has already been done in \cite{singer-influence} and is given +here in lemma~\ref{lemma:monotone} below for the sake of completeness. \emph{Budget feasibility.} Thanks to the analysis of the threshold payment in \cite{chen}, the budget feasibility follows easily. The -- cgit v1.2.3-70-g09d2