Article ID Journal Published Year Pages File Type
1142152 Operations Research Letters 2016 4 Pages PDF
Abstract

It is well-known that the VCG mechanism is optimal for a buyer procuring one unit from a set of symmetric suppliers. For procuring a unit from asymmetric suppliers, Myerson’s optimal mechanism can be interpreted as a transformation of the VCG mechanism–both in terms of its allocation and payment–using the virtual cost function. For a more general setting in which multiple units need to be procured from asymmetric suppliers under an arbitrary set of feasibility constraints, we analyze the same transformation of the VCG mechanism. We show that this mechanism is optimal if the feasible region is a polymatroid. We also present an example of a non-polymatroidal feasible region for which this mechanism is sub-optimal.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,