Understanding the relationship between core constraints and core-selecting payment rules in combinatorial auctions (Q6535796)

In this paper, the authors study payment rules for welfare maximizing known single-minded combinatorial auctions (CAs) in which each bidder is interested in a single known bundle. The profile of desired bundles together with the profile of bids define a number of linear constraints (the core constraints) which form a polytope (the core). It has been shown that bidders can sometimes decrease their payments by announcing higher-than-truthful bids under the VN payment rule. The limitations of VN payments are studied. It is shown that the non-decreasing property holds whenever a single effective core constraint exists. More precisely, the authors introduce a graph-based representation of CAs and construct a conflict graph based on the overlap between the desired bundles of the bidders. Sufficient conditions on the conflict graph are obtained to have a single effective core constraint.\N\NFor the entire collection see [Zbl 1535.68009].