diff options
| -rw-r--r-- | final/main.tex | 6 |
1 files changed, 3 insertions, 3 deletions
diff --git a/final/main.tex b/final/main.tex index 8f7ffff..3816d4a 100644 --- a/final/main.tex +++ b/final/main.tex @@ -165,7 +165,7 @@ $\gamma$ is a constant which is at least $\frac{1}{2}$. Given the simplicity of posted-price mechanisms and the fact that they are optimal in the single-agent single-item setting (for a regular distribution -$F$), we would like a mechanism as close as possible to posted-price. +$F$), it would be desirable to obtain a mechanism as close as possible to posted-price. Unfortunately, Hart and Nisan \cite{hart-nisan} showed that even in the unconstrained, regular case, no posted-price mechanism for the single-agent problem has an approximation ratio better than $\Omega(\log n)$. @@ -178,11 +178,11 @@ This is essentially the concept of a two-part tariff, as discussed in Note that as written above, the candidate mechanism is not individually rational because the agent gets charged $p_0$ regardless of her type. To -restore individual rationality, we need to have the agent pay only when: +restore individual rationality, we need to have the agent pay only when \begin{displaymath} \sum_{i=1}^m (t_i - p_i)^+ \geq p_0 \end{displaymath} -where we used the notation $(x)^+\eqdef\max\{x, 0\}$, so that the +where we used the notation $(x)^+\eqdef\max(x, 0)$, so that the above inequality could also be written as $$\sum_{i: t_i\geq p_i} (t_i- p_i)\geq p_0.$$ We can now formally describe the candidate mechanism. |