Residential College | false |
Status | 已發表Published |
Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions | |
Fritsch, Robin1; Lee, Younjoo2; Meier, Adrian1; Wang, Ye3![]() ![]() | |
2023-08-26 | |
Conference Name | 17th International Joint Conference on Theoretical Computer Science |
Source Publication | Frontiers of Algorithmics (IJTCS-FAW 2023)
![]() |
Volume | 13933 |
Pages | 1-14 |
Conference Date | 14-18 August 2023 |
Conference Place | Macao, China |
Country | China |
Publisher | Springer Science and Business Media Deutschland GmbH |
Abstract | Combinatorial auctions (CAs) allow bidders to express complex preferences for bundles of goods being auctioned, which are widely applied in the web-based business. 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. We further show that the VCG-nearest payment rule is non-decreasing with no more than five bidders. |
Keyword | Combinatorial Auctions Core-selecting Payment Rules Non-decreasing Payment Rules Overbidding Vgc-nearest Payment Rule |
DOI | 10.1007/978-3-031-39344-0_1 |
URL | View the original |
Language | 英語English |
Scopus ID | 2-s2.0-85171430168 |
Fulltext Access | |
Citation statistics | |
Document Type | Conference paper |
Collection | Faculty of Science and Technology DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE |
Corresponding Author | Wang, Ye |
Affiliation | 1.ETH Zurich, Zurich, Switzerland 2.Seoul National University, Seoul, South Korea 3.University of Macau, Macao |
Corresponding Author Affilication | University of Macau |
Recommended Citation GB/T 7714 | Fritsch, Robin,Lee, Younjoo,Meier, Adrian,et al. Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions[C]:Springer Science and Business Media Deutschland GmbH, 2023, 1-14. |
APA | Fritsch, Robin., Lee, Younjoo., Meier, Adrian., Wang, Ye., & Wattenhofer, Roger (2023). Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions. Frontiers of Algorithmics (IJTCS-FAW 2023), 13933, 1-14. |
Files in This Item: | There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment