Characterization of Incentive Compatible Single-parameter Mechanisms Revisited

6^th June 2023, 16:00 Electrical Engineering, Lecture Theatre
Prof. Krzysztof Apt
Centrum Wiskunde & Informatica

Abstract

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
recently appeared in
the Journal of Mechanism and Institution Design, see
http://www.mechanism-design.org/arch/v007-1/v007-1-4.html.