Characterizing incentive compatible, Pareto optimal and sufficiently anonymous constrained combinatorial mechanisms – Two players case

Article type: Research Article

Authors: Gonen, Rica^a | Lerner, Anat^b

Affiliations: [a] Department of Management and Economics, The Open University of Israel, 1 University Road, Raanana 43537, Israel. ricagonen@gmail.com | [b] Department of Mathematics and Computer Science, The Open University of Israel, 1 University Road, Raanana 43537, Israel. anat@cs.openu.ac.il

Abstract: We characterize the possibility space of deterministic, dominant-strategy incentive compatible, individually rational, and Pareto-optimal combinatorial auctions in a model with two players and two nonidentical items. Our model has multidimensional types, private values, quasilinear preferences for the players with one relaxation – one of the players is subject to a publicly-known budget constraint. We show that the space includes two types of mechanisms: VCG and dictatorial mechanisms. Furthermore when it is publicly known that the budgeted player is not constrained by his budget, VCG uniquely fulfills the basic properties of deterministic, dominant-strategy incentive compatible, individually rational, and Pareto-optimal. When it is publicly known that the budgeted player is constrained on all bundles then only a dictatorial solution will fulfill the above properties. Moreover when it is publicly known that the budgeted player is constrained on the largest bundle there are preferences under which the VCG mechanism uniquely fulfills these properties.

Keywords: Budget constraints, dictatorship, Pareto efficiency, incentive compatibility

DOI: 10.3233/COM-160064

Journal: Computability, vol. 6, no. 2, pp. 183-208, 2017