Kombinatorische Auktion - Combinatorial auction
.jpg)
Eine kombinatorische Auktion ist eine Art intelligenter Markt, in dem Teilnehmer Gebote auf Kombinationen von diskreten heterogenen Artikeln oder „Paketen“ abgeben können, anstatt auf einzelne Artikel oder kontinuierliche Mengen. Diese Pakete können auch als Lose bezeichnet werden und die gesamte Auktion als Multi-Lot-Auktion . Kombinatorische Auktionen sind anwendbar, wenn Bieter nicht-additive Bewertungen von Artikelbündeln haben, dh Kombinationen von Artikeln mehr oder weniger bewerten als die Summe ihrer Bewertungen einzelner Elemente der Kombination.
Einfache kombinatorische Auktionen werden seit vielen Jahren bei Nachlassauktionen verwendet , bei denen ein übliches Verfahren darin besteht, Gebote für Paketpakete anzunehmen. Sie wurden in letzter Zeit für den LKW-Transport, Buslinien, die industrielle Beschaffung und bei der Zuweisung von Funkfrequenzen für die drahtlose Kommunikation verwendet. In den letzten Jahren haben Beschaffungsteams umgekehrte kombinatorische Auktionen bei der Beschaffung von Waren und Dienstleistungen angewendet. Diese Anwendung wird oft als Sourcing-Optimierung bezeichnet. Da der Aufbau Beschaffung oft Verhandlungen über mehrere Komponenten umfasst, die kombinatorischen Reverse - Auktionen werden vorgeschlagen , die Kosten in dieser Branche zu reduzieren.
Obwohl sie es Bietern ermöglichen, ausdrucksvoller zu sein, stellen kombinatorische Auktionen im Vergleich zu herkömmlichen Auktionen sowohl rechnerische als auch spieltheoretische Herausforderungen. Ein Beispiel für ein Rechenproblem ist die effiziente Bestimmung der Zuteilung, nachdem die Gebote an den Auktionator abgegeben wurden. Dies wird als Gewinnerbestimmungsproblem bezeichnet.
Das Problem der Gewinnerbestimmung kann wie folgt formuliert werden: Finden Sie bei einer Reihe von Geboten in einer kombinatorischen Auktion eine Zuteilung von Artikeln an Bieter – einschließlich der Möglichkeit, dass der Auktionator einige Artikel behält –, die den Erlös des Auktionators maximiert. Dieses Problem ist für große Instanzen schwierig. Insbesondere ist es NP-hart , was bedeutet, dass vermutet wird, dass es keinen Polynomialzeitalgorithmus gibt, der die optimale Zuordnung findet. Die kombinatorische Auktion Problem kann als modelliert werden Set Verpackung Problem. Daher wurden viele Algorithmen vorgeschlagen, um angenäherte Lösungen für das kombinatorische Auktionsproblem zu finden. Hsieh (2010) schlug beispielsweise einen Lagrange-Relaxationsansatz für kombinatorische umgekehrte Auktionsprobleme vor.
Viele dieser Aspekte kombinatorischer Auktionen, einschließlich einiger Beispiele aus der Praxis, werden auch in dem umfassenden Buch von Cramton, Shoham und Steinberg (2006) erörtert.
Geschichte
Kombinatorische Auktionen wurden zuerst von Rassenti, Smith und Bulfin (1982) für die Zuteilung von Landeplätzen auf Flughäfen vorgeschlagen . Ihr Papier stellte viele Schlüsselideen zu kombinatorischen Auktionen vor, darunter die mathematische Programmierung des Auktionatorproblems, die Verbindung zwischen dem Gewinnerbestimmungsproblem und dem Set-Packing- Problem, das Problem der rechnerischen Komplexität, die Verwendung von Techniken aus der experimentellen Ökonomie zum Testen kombinatorischer Auktionen und Berücksichtigung von Fragen der Anreizkompatibilität und Nachfrageoffenbarung in kombinatorischen Auktionen.
Kombinatorische Uhren-Auktion
Ein Sonderfall einer kombinatorischen Auktion ist die Combinatorial Clock Auction (CCA), die eine Clock-Auktion, bei der Bieter aufgrund steigender Preise ihre Bestätigungen abgeben können, mit einer anschließenden Sealed-Bid-Auktion kombiniert, bei der Bieter versiegelte Paketgebote abgeben . Der Auktionator verwendet die endgültigen Gebote, um die beste Wertzuordnung und die Vickrey-Zahlungen zu berechnen .
Siehe auch
Verweise
Weiterlesen
- Peter Cramton, Yoav Shoham und Richard Steinberg (2006). Kombinatorische Auktionen . MIT-Presse . ISBN 0-262-03342-9 . Ein beigesteuertes Buch mit breiter Abdeckung des Themas.
- de Vries, S.; Vohra, R. (2003). "Kombinatorische Auktionen: Eine Umfrage" (PDF) . INFORMS Zeitschrift für Informatik . 15 (3): 284–309. CiteSeerX 10.1.1.23.8046 . doi : 10.1287/ijoc.15.3.284.16077 . ISSN 1526-5528 . Etwas veraltet, aber eine klassische Umfrage.
- Vazirani, Vijay V .; Nisan, Noam ; Rauer Garten, Tim ; Tardos, Eva (2007). Algorithmische Spieltheorie (PDF) . Cambridge, Großbritannien: Cambridge University Press. ISBN 0-521-87282-0.. Ein beigesteuertes Buch mit einem guten Einführungskapitel zu kombinatorischen Auktionen aus der Perspektive der Informatiktheorie; siehe Kapitel 11.
- Rassenti, Stephen J. ; Smith, Vernon L.; Bulfin, Robert L. (1982). "Ein kombinatorischer Auktionsmechanismus für die Zuteilung von Zeitfenstern am Flughafen" (PDF) . Bell Journal of Economics . 13 (2): 402–417. doi : 10.2307/3003463 . JSTOR 3003463 . Frühes Werk, das die Idee einer kombinatorischen Auktion populär machte.
- Rothkopf, M.; Pekec, A.; Harstad, R. (1998). "Rechnerisch überschaubare kombinatorische Auktionen". Management-Wissenschaft . 44 (8): 1131-1147. CiteSeerX 10.1.1.723.9753 . doi : 10.1287/mnsc.44.8.1131 . Ein einflussreiches frühes Papier zu rechnerischen Überlegungen.
- Hammami, Faruk; Rekik, Monia; Coelho, Leandro C. (2019). "Exakte und heuristische Lösungsansätze für das Angebotsbildungsproblem bei Verkehrsbeschaffungsauktionen mit heterogener Flotte". Transportforschung Teil E: Logistik und Transportbericht . 127 : 150–177. doi : 10.1016/j.tre.2019.05.009 . Eine Anwendung kombinatorischer Auktionen für die Beschaffung von Transportdienstleistungen.
- Hsieh, Fu-Shung (2010). "Kombinatorische umgekehrte Auktion basierend auf der Enthüllung von Lagrange-Multiplikatoren" (PDF) . Entscheidungsunterstützungssysteme . 48 (2): 323–330. doi : 10.1016/j.dss.2009.08.009 .
- Schoham, Yoav; Leyton-Brown, Kevin (2009). Multiagentensysteme: Algorithmische, spieltheoretische und logische Grundlagen . New York: Cambridge University Press . ISBN 978-0-521-89943-7.Eine Übersicht in Lehrbuchform; siehe Abschnitt 11.3. Kostenlos online herunterladbar .