ALPS - design and analysis of a robust iterative combinatorial auction format [Elektronische Ressource] / Pavlo Shabalin

Pasha Shabalin

Sujets

• Wissenschaft
• Naturwissenschaften
• Management

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2009
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Institut fur Informatik
der Technischen Universit at Munc hen
Lehrstuhl fur Informatik XVIII
ALPS { Design and Analysis of a Robust
Iterative Combinatorial Auction Format
Pavlo Shabalin
Vollst andiger Abdruck der von der Fakult at fur Informatik der Technischen
Universit at Munc hen zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr. J. Schlichter
Prufer der Dissertation:
1. Univ.-Prof. Dr. M. Bichler
2. M. Beetz, Ph.D.
Die Dissertation wurde am 10.12.2008 bei der Technischen Universit at
Munc hen eingereicht und durch die Fakult at fur Informatik am 19.05.2009
angenommen.Orach Boris GrigorjevichAbstract
In a combinatorial auction (CA) several heterogenous items are traded simulta-
neously, they can be distributed between several winners, and the bidders can
submit indivisible all-or-nothing \bundle" bids on groups of items. The idea of
using CAs for capturing economies of scale and scope and thus achieving better
economic results on complex markets was rst suggested in 1982 in the context
of allocating airport slots. For several years the concept was not considered
practical because of its combinatorial complexity, but it was eventually picked
up by the US Federal Communication Commission (FCC) as a promising tool
for conducting spectrum auctions, where bidders have strong preferences to
win licenses for geographically adjacent regions. However, it took the FCC
over 15 years of research and testing until the rst combinatorial spectrum
auction was conducted in 2008.
In the meantime, combinatorial auctions were discovered by frontier profes-
sionals in industrial purchasing. There are a couple of published cases which
demonstrate the high potential of this new technology for procurement applica-
tions, among them two nalists and one winner of the prestigious practitioner
INFORMS Edelman Award in the past six years.
However, there are no standard solutions with adequate support for combina-
torial auctions available to date. Only the recent advances in computer science
and the optimization theory made their application possible, and they still re-
quire signi cant research and engineering work. In particular, there is little
understanding regarding the applicability of various existing CA formats, and
regarding their robustness in cases where bidders do not follow theoretically
optimal strategies.
In this context, our goal was to suggest a practical and robust combinatorial
auction format which delivers good results for various types of bidder valua-
tions and strategies. Such a design shall be based on a thorough analysis and
icomparison of existing mechanisms. In particular, it was not clear whether
CAs based on linear or non-linear prices present the preferable approach.
We have chosen computational experiments to be our main research tool. The
game-theoretical approach, which has been used extensively to model single-
item auctions, has only limited applicability in the context of combinatorial
auctions due to their high strategic complexity. Furthermore, there are strong
indications that the bidders fail to act rationally in their exponential strate-
gic space. Experimental economics, which is another proven approach to the
studying of market mechanisms, has delivered only very limited results to date,
due to the high complexity and cost of laboratory experiments with CAs.
Computational experiments allowed us to systematically test and compare
many combinatorial auction designs under di erent valuations and di erent
bidder behavioral models. We could also measure their sensitivity with respect
to di erent parameters. To achieve reliable results, our experiments are based
on a broad range of economically motivated value models and bidding agents
with di erent behavior, based both on theoretical assumptions and on our
observations in the laboratory. Overall, this thesis summarizes the results of
over 50’000 auctions.
The main contribution of this work is the ALPS linear-price-based iterative
combinatorial auction (ICA) format. It demonstrates high allocative e ciency
of over 98% in our experiments, as well as very good robustness in cases when
the bidders do not follow the theoretically optimal strategy. It has several
practice-oriented features which further improve its performance. The dynamic
minimum increment can halve the auction duration without sacri cing the
e ciency. The surplus eligibility rule can mitigate the negative e ect of activity
rules in the auction. While our results achieve high e ciency values on average,
we have identi ed and described cases where linear price CAs are not e cient.
There are a few remedies, such as the proxy phase in the Clock-Proxy auction
or after-market negotiation on unsold items.
During development of the new CA design, we run a thorough comparison
of existing formats along various criteria. In particular, this work is the rst
detailed benchmark of two big ICA families: linear-price and non-linear price
designs.
An important result of our work is the MarketDesigner platform for com-
binatorial auctions, which was a signi cant investment, and is a joint e ort
together with several colleagues and many students. It is currently being used
for laboratory experiments and pilot projects with industry partners.
iiZusammenfassung
In einer kombinatorischen Auktion werden mehrere heterogene Guter gleich-
zeitig versteigert; es sind mehrere Gewinner m oglich; und die Bieter k onnen
untrennbare alles-oder-nichts Bun delgebote auf Gruppen von Gutern abgeben.
Auf komplexen M arkten k onnen solche Auktionen Verbund- und Skalen-
e ekte adressieren und dadurch bessere ok onomische Ergebnisse erzielen. Das
Konzept wurde zum ersten Mal im Jahr 1982 im Zusammenhang mit der
Terminalzeitplanung auf Flugh afen vorgeschlagen. Nachdem die kombina-
torischen Auktionen zuerst wegen ihrer exponentiellen Komplexit at als im-
praktikabel galten, wurden sie von der US Federal Communication Commis-
sion (FCC) zum Versteigern von Frequenzlizenzen vorgeschlagen, wo die Bie-
ter starke Pr aferenzen fur benachbarte Regionen haben. Es hat aber ub er 15
Jahren gedauert, bis das FCC die erste kombinatorische Frequenzauktion im
Jahr 2008 durchgefuhrt hat.
Inzwischen wurden die kombinatorischen Auktionen vom Industrieeinkauf ent-
deckt. Das gro e Potenzial der neuen Technologie im Einkauf wurde durch
einige Publikationen bewiesen, unter denen be nden sich zwei Finalisten und
ein Gewinner des angesehenen INFOMRS Edelman Award in den letzten sechs
Jahren.
Dennoch gibt es keine standardm a igen L osungen fur kombinatorische Auktio-
nen. Lediglich die jungsten Entwicklungen der Informatik und Optimierungs-
theorie haben ihre praktischen Anwendungen erm oglicht, und sie erfordern im-
mer noch wesentliche Forschungs- und Entwicklungsarbeit. Insbesondere gibt
es wenig Wissen sowohl bezuglic h der Anwendbarkeit von verschiedenen kombi-
natorischen Auktionsformaten, als auch bezuglic h deren Robustheit gegenub er
suboptimaler Bietstrategien.
In diesem Zusammenhang, das Ziel dieser Arbeit war, ein praktisches und
robustes kombinatorisches Auktionsformat vorzuschlagen, das fur verschiedene
iiiWertigkeiten und Bietstrategien gute Ergebnisse zeigt. Der Vorschlag soll auf
grundlic her Analyse und Vergleich von bekannten Auktionsformaten basieren.
Speziell, es war nicht klar ob kombinatorische Auktionen mit linearen oder
nichtlinearen Preisen vorzuziehen sind.
Zum Hauptwerkzeug unserer Forschung haben wir Simulationen gew ahlt. Die
Spieltheorie, die zur Analyse von ublic hen Auktionen oft benutzt wird, ist we-
gen der hohen Komplexit at von Spielerstrategien in kombinatorischen Auktio-
nen nur begrenzt anwendbar. Au erdem gibt es Anzeichen dafur, dass die Bie-
ter sich in solch komplexen Strategier aumen nicht rationell verhalten. Die an-
dere bekannte Forschungsmethode - die experimentelle konomie hat bis heute
auf dem Gebiet, wegen hoher Komplexit at und Kosten von Experimenten mit
kombinatorischen Auktionen, nur sehr begrenzte Ergebnisse hervorgebracht.
Mittels Simulationen konnten wir viele kombinatorische Auktionsformate unter
verschiedenen Wertigkeits- und Bieterverhaltensmodellen systematisch testen
und vergleichen. Ebenfalls konnten wir ihre Sensitivit at bezug lich unter-
schiedlicher Parameter messen. Um verl assliche Ergebnisse zu bekommen,
verwenden unsere Simulationen viele unterschiedliche Wertigkeitsmodelle mit
ok onomischem Hintergrund und verschiedene Bieteragenten, die beides auf
theoretischen Annahmen und auf Beobachtungen im Labor basieren. Insge-
samt haben wir in Rahmen dieser Arbeit ub er 50’000 Auktionen analysiert.
Der Hauptbeitrag dieser Arbeit ist ALPS: ein iteratives, linear-Preis basiertes
kombinatorisches Auktionsformat. Es zeigt in unseren Simulationen eine hohe
allokative E zienz von ub er 98auch eine gute Robustheit gegenub er subopti-
maler Bieterstrategien. ALPS hat auch einige praxisorientierte Eigenschaften.
Das dynamische Preisinkrement (dynamic minimum increment) kann die Auk-
tionsl ange halbieren, ohne dass die allokative E zienz allt.f Die surplus eli-
gibility Regel kann die negative Wirkung von Aktivit atsregeln in der Auk-
tion reduzieren. Obwohl ALPS im Durchschnitt eine sehr hohe allokative
E zienz z