Lemma 4.15 — the biased min work mechanism is strongly truthful for all parameters

Consider task scheduling with two agents and $k$ tasks. For every real $\beta \ge 1$ and every bit vector $s \in \{1,2\}^k$, the biased min work mechanism with parameters $\beta$ and $s$ is strongly truthful on positive types:

1. for every positive declaration $d^{-i}$ of the other agent, every positive true type $t^i$ and every positive misreport $d^i$, agent $i$'s utility from declaring $t^i$ is at least that from declaring $d^i$;
2. for every positive $t^i$ and every positive $d^i \ne t^i$, there is a positive declaration $d^{-i}$ of the other agent under which declaring $d^i$ gives agent $i$ strictly smaller utility than declaring $t^i$.

Here agent $i$'s utility is the payment it receives minus $\sum_{j \in x^i} t^i_j$ over the tasks it is allocated. This lemma is the source of the universal truthfulness of the randomized mechanism.

Formalization Note "For all parameter values" is read as all $\beta \ge 1$ (the parameter range of Fig. 1) and all $s$; it is stated for every number $k$ of tasks.