Header

UZH-Logo

Maintenance Infos

The Cost of Simple Bidding in Combinatorial Auctions


Bosshard, Vitor; Seuken, Sven (2020). The Cost of Simple Bidding in Combinatorial Auctions. arXiv.org 12237, University of Zurich.

Abstract

We study the complexity of bidding optimally in one-shot combinatorial auction mechanisms. Specifically, we consider the two most-commonly used payment rules: first-price and VCG-nearest. Prior work has largely assumed that bidders only submit bids on their bundles of interest. However, we show the surprising result that a single-minded bidder may lose an exponential amount of utility by playing his optimal simple strategy (only bidding on his bundle of interest) compared to playing his optimal complex strategy (which involves bidding on an exponential number of bundles). Our work suggests that it is important for future research on combinatorial auctions to fully take these effects into account.

Abstract

We study the complexity of bidding optimally in one-shot combinatorial auction mechanisms. Specifically, we consider the two most-commonly used payment rules: first-price and VCG-nearest. Prior work has largely assumed that bidders only submit bids on their bundles of interest. However, we show the surprising result that a single-minded bidder may lose an exponential amount of utility by playing his optimal simple strategy (only bidding on his bundle of interest) compared to playing his optimal complex strategy (which involves bidding on an exponential number of bundles). Our work suggests that it is important for future research on combinatorial auctions to fully take these effects into account.

Statistics

Downloads

3 downloads since deposited on 26 Jan 2021
3 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Working Paper
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Date:2020
Deposited On:26 Jan 2021 13:14
Last Modified:26 Jan 2021 13:15
Series Name:arXiv.org
ISSN:2331-8422
OA Status:Green
Free access at:Official URL. An embargo period may apply.
Official URL:https://arxiv.org/abs/2011.12237
Other Identification Number:merlin-id:20200

Download

Green Open Access

Download PDF  'The Cost of Simple Bidding in Combinatorial Auctions'.
Preview
Content: Published Version
Filetype: PDF
Size: 713kB
Licence: Creative Commons: Attribution 4.0 International (CC BY 4.0)