Decentralized Auctioneerless Combinatorial Auctions for Multi-Unit Resource Allocation

Li-Hsing Yen*, Guang Hong Sun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Auction has been used to allocate resources or tasks to processes, machines, or other autonomous agents in distributed systems. Among various types of auctions, combinatorial auction (CA) allocates a bundle of items to each agent at once. Finding an optimal auction result for CA that maximizes total winning bid is NP-hard. Many time-efficient approximations to this problem work with a bid ranking function (BRF). However, the existing approximations are mostly for single-unit resource and demand an auctioneer. This paper proposes the first auctioneerless open-bid multi-unit CA (MUCA) scheme. It includes a BRF-based winner determination scheme that enables every agent to locally compute a critical bid value for it to win the MUCA and accordingly take its best response to other agent's bid and win declarations. It also allows each winner to locally compute its payment for a critical-value-based pricing scheme. We analyze stabilization, correctness, and consistency properties of the proposed approach. The simulation results confirm that the proposed approach identifies exactly the same set of winners as the centralized counterpart regardless of initial bid setting, but at the cost of the lower total winning bid and payment.

Original languageEnglish
Article number8736283
Pages (from-to)78625-78639
Number of pages15
JournalIEEE Access
Volume7
DOIs
StatePublished - 13 Jun 2019

Keywords

  • combinatorial auctions
  • Distributed algorithms
  • game theory
  • resource allocation
  • resource management

Fingerprint Dive into the research topics of 'Decentralized Auctioneerless Combinatorial Auctions for Multi-Unit Resource Allocation'. Together they form a unique fingerprint.

Cite this