We study envy-free and truthful mechanisms for domains with additive valuations, like the ones that arise in scheduling on unrelated machines. We investigate the allocation functions that are both weakly monotone (truthful) and locally efficient (envy-free), in the case of only two tasks, but
players. We show that the only allocation functions that satisfy both conditions are affine minimizers, with strong restrictions on the parameters of the affine minimizer. As a further result, we provide a common payment function, i.e., a single mechanism that is both truthful and envy-free.
For additive combinatorial auctions our approach leads us (only) to a non- affine maximizer similar to the counterexample of Lavi et al. . Thus our result demonstrates the inherent difference between the scheduling and the auctions domain, and inspires new questions related to the classic problem of characterizing truthfulness in additive domains.