Two-player incentive compatible outcome functions are affine maximizers
arXiv:1710.05218 · doi:10.1016/j.laa.2019.04.027
Abstract
In mechanism design, for a given type space, there may be incentive compatible outcome functions which are not affine maximizers. Using tools from linear algebra and tropical geometry, we prove that for two-player games on a discrete type space, any given outcome function can be turned into an affine maximizer through a nontrivial perturbation of the type space. Furthermore, our theorems are the strongest possible in this setup.
16 pages, 2 figures; to appear in Linear Algebra and its Applications