Lemma 4.17 — the randomly biased min work mechanism is strongly truthful

For every number $k$ of tasks, the randomly biased min work mechanism (the uniform distribution over the biased min work mechanisms with $\beta = 4/3$ and $s \in \{1,2\}^k$) is universally strongly truthful:

1. for every $s \in \{1,2\}^k$, the biased min work mechanism with parameters $4/3$ and $s$ is truthful on positive types; and
2. for every agent $i$, every positive true type $t^i$ and every positive misreport $d^i \ne t^i$, there are $s$ and a positive declaration $d^{-i}$ of the other agent under which declaring $d^i$ gives agent $i$ strictly smaller utility than declaring $t^i$.

Truthfulness is required for every outcome of the coin tosses, not in expectation.

Formalization Note Given part 1, part 2 says exactly that truth-telling is the only universally dominant strategy (Definition 16); the support of the uniform distribution is all of $\{1,2\}^k$.