Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142152 | Operations Research Letters | 2016 | 4 Pages |
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
Shivam Gupta,