UM  > Faculty of Science and Technology
Residential Collegefalse
Status已發表Published
Understanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions
Fritsch, Robin1; Lee, Younjoo2; Meier, Adrian1; Wang, Ye3; Wattenhofer, Roger1
2023-08-26
Conference Name17th International Joint Conference on Theoretical Computer Science
Source PublicationFrontiers of Algorithmics (IJTCS-FAW 2023)
Volume13933
Pages1-14
Conference Date14-18 August 2023
Conference PlaceMacao, China
CountryChina
PublisherSpringer 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.

KeywordCombinatorial Auctions Core-selecting Payment Rules Non-decreasing Payment Rules Overbidding Vgc-nearest Payment Rule
DOI10.1007/978-3-031-39344-0_1
URLView the original
Language英語English
Scopus ID2-s2.0-85171430168
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionFaculty of Science and Technology
DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Corresponding AuthorWang, Ye
Affiliation1.ETH Zurich, Zurich, Switzerland
2.Seoul National University, Seoul, South Korea
3.University of Macau, Macao
Corresponding Author AffilicationUniversity 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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Fritsch, Robin]'s Articles
[Lee, Younjoo]'s Articles
[Meier, Adrian]'s Articles
Baidu academic
Similar articles in Baidu academic
[Fritsch, Robin]'s Articles
[Lee, Younjoo]'s Articles
[Meier, Adrian]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Fritsch, Robin]'s Articles
[Lee, Younjoo]'s Articles
[Meier, Adrian]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.