Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions
METADATA ONLY
Loading...
Author / Producer
Date
2023-08
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Combinatorial auctions (CAs) allow bidders to express complex preferences for bundles of goods being auctioned. However, the behavior of bidders under different payment rules is often unclear. In this paper, we aim to understand how core constraints interact with different core-selecting payment rules. In particular, we examine the natural and desirable non-decreasing property of payment rules, which states that bidders cannot decrease their payments by increasing their bids. Previous work showed that, in general, the widely used VCG-nearest payment rule violates the non-decreasing property in single-minded CAs. We prove that under a single effective core constraint, the VCG-nearest payment rule is non-decreasing. In order to determine in which auctions single effective core constraints occur, we introduce a conflict graph representation of single-minded CAs and find sufficient conditions for the single effective core constraint in CAs. Finally, we study the consequences on the behavior of the bidders and show that no over-bidding exists in any Nash equilibrium for non-decreasing core-selecting payment rules.
Permanent link
Publication status
published
External links
Book title
Frontiers of Algorithmics. IJTCS-FAW 2023
Journal / series
Volume
13933
Pages / Article No.
1 - 14
Publisher
Springer
Event
International Joint Conference on Theoretical Computer Science – Frontier of Algorithmic Wisdom (IJTCS-FAW 2023)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Computer Science and Game Theory (cs.GT); FOS: Computer and information sciences; Combinatorial auctions; Core-selecting payment rules; VGC-nearest payment rule; Non-decreasing payment rules; Overbidding
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
Notes
Funding
Related publications and datasets
Is new version of: 10.48550/arXiv.2204.11708