Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Faster Algorithms and Better Payment Rules for Core-Selecting Combinatorial Auctions
Organization Unit
Authors
  • Benedikt Bünz
Supervisors
  • Sven Seuken
Language
  • English
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Number of Pages 90
Date 2014
Abstract Text Combinatorial auctions have received increasing attention during the last years. Their allocational power, which allows for highly complex bidder valuations, has been utilized in many multi billion dollar public-sector auctions. Despite their frequent use, many questions about combinatorial auction still remain unanswered. The nature of these questions is often not only economical but also computational. In this thesis we focus on payments in combinatorial auction. Recent literature has suggested that one should select payments that are in the core of the auction. In the first part of the thesis we introduce new theoretical results on core constraints. We then use this insight to improve the state of the art algorithm for computing core payments. Our experiments show that these new algorithmic ideas can compute core payments in hard instances at least 75 faster than the currently fastest known algorithm. In the second part of the thesis we propose an algorithm that can approximate BNEs in core-selecting combinatorial auctions. We then use this algorithm to analyze several known core-payment rules. Additionally we introduce new core payment rules that, in our analysis, have better incentives.
Zusammenfassung Kombinatorische Auktionen haben in den letzten Jahren zunehmende Aufmerksamkeit erlangt. Die Fähigkeit hoch komplexe Präferenzen von Bietern zu handhaben, wurde in vielen Milliarden Dollar Auktionen im öffentlichen Sektor genutzt. Trotz der häufigen Nutzung gibt es noch viele unbeantwortete Fragen zu kombinatorischen Auktionen. Viele dieser Fragen sind nicht nur ökonomischer sondern auch rechnerischer Natur. In dieser Arbeit fokussieren wir uns auf Preise in kombinatorischen Auktionen. In der Fachliteratur wurde in letzter Zeit Payments vorgeschlagen, das die Preise im Kern der Auktion liegen sollten. Im ersten Teil der Arbeit führen wir neue theoretische Resultate zu Kern Constraints ein. Wir benutzen dieses neue Wissen um Verbesserungen zu einem bestehenden Algorithmus vorzuschlagen. Unsere Experimente Zeigen, dass unser Algorithmus, in genügend schweren Problemen, mindestens 75% schneller als der bisherige Standard ist. Der zweite Teil der Arbeit beschäftigt sich mit Zahlungsregeln in Kombinatorischen Auktionen. Wir analysieren verschiedene bekannte und neu entwickelte Zahlungsregeln, indem wir deren BNEs approxi­mieren. Wir zeigen das eine unserer vorgeschlagenen Regeln bessere Anreize hat, als alle bisher bekannten.
PDF File Download
Export BibTeX