From 07d48e21fb6fc62b1a85b9d80c25560529a9a0b5 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 28 Jun 2013 00:16:44 +0200
Subject: Moving the proofs to the appendix, improving the flow

---
 main.tex | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 0e8457c..ff26c5d 100644
--- a/main.tex
+++ b/main.tex
@@ -53,9 +53,9 @@ Instead, \citeN{singer-mechanisms} and \citeN{chen}
 suggest to approximate $OPT_{-i^*}$ by a quantity $OPT'_{-i^*}$ satisfying the
 following properties:
 \begin{itemize}
-    \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported
-    cost and must be monotone: it can only increase when agents decrease
-    their costs. This is to ensure the monotonicity of the allocation function.
+    \item $OPT'_{-i^*}$ must not depend on agent $i^*$'s reported cost and must
+    be decreasing with respect to the costs. This is to ensure the monotonicity
+    of the allocation function.
     \item $OPT'_{-i^*}$ must be close to $OPT_{-i^*}$ to maintain a bounded
     approximation ratio.
     \item $OPT'_{-i^*}$ must be computable in polynomial time.
@@ -74,18 +74,23 @@ $\delta$-decreasing, the resulting mechanism will be $\delta$-truthful as
 defined below.
 
 \begin{definition}
-Let $\mathcal{M}= (S, p)$ a mechanism, and let $s$ denote the indicator
-function of $S$ ($s_i(c) = \id_{i\in S(c)}$). We say that $\mathcal{M}$ is
+Let $\mathcal{M}= (S, p)$ a mechanism, and let $s_i$ denote the indicator
+function of $i\in S(c)$, $s_i(c) \defeq \id_{i\in S(c)}$. We say that $\mathcal{M}$ is
 $\delta$-truthful iff:
 \begin{displaymath}
 \forall c\in\reals_+^n,\;
-\forall\mu\geq\delta,\;
+\forall\mu\;\text{with}\; |\mu|\geq\delta,\;
 \forall i\in\{1,\ldots,n\},\;
 p(c)-s_i(c)\cdot c_i \geq p(c+\mu e_i) - s_i(c+\mu e_i)\cdot c_i
 \end{displaymath}
-where $e_i$ is the $i$-th basis vector of $\reals^n$.
+where $e_i$ is the $i$-th canonical basis vector of $\reals^n$.
 \end{definition}
 
+Intuitively, $\delta$-truthfulness implies that agents have no incentive to lie
+by more than $\delta$ about their reported costs. In practical applications,
+the bids being discretized, if $\delta$ is smaller than the discretization
+step, the mechanism will be truthful in effect.
+
 $\delta$-truthfulness will follow from $\delta$-monotonicity by the following
 variant of Myerson's theorem.
 
-- 
cgit v1.2.3-70-g09d2

