Characterization of Incentive Compatible Single-parameter Mechanisms Revisited

We review the characterization of incentive compatible single-parameter mechanisms introduced by Archer and Tardos in 2001. We argue that the claimed (and often cited) uniqueness result has not been established in the computer science literature and clarify that it was given in a slightly different setting in the 2002 Krishna’s book `Auction Theory’. However, this proof implicitly relies on Lebesgue integral.

We provide an elementary proof of uniqueness that unifies the presentation for two classes of allocation functions considered in the 2016 book of Rougharden `Twenty Lectures on Algorithmic Game Theory’ and show that the general case is a consequence of a little known result from the theory of real functions.

The corresponding general result and its modification to more dimensions yield elementary proofs of characterizations of incentive compatibility for Bayesian mechanisms and dominant mechanisms studied in 2015 Boerger’s book `An Introduction to the Theory of Mechanism Design’, and multiunit auctions and combinatorial auctions considered in Krishna’s book (such results are called Revenue Equivalence in the economics literature).

Joint work with Jan Heering. The talk is based on a paper that appeared in the Journal of Mechanism and Institution Design, see http://www.mechanism-design.org/arch/v007-1/v007-1-4.html.