diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 19 |
1 files changed, 12 insertions, 7 deletions
@@ -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. |