Entscheidungsunterstützungssysteme IWI Frankfurt 2004 Dynamische Bepreisung von Güterbündeln mittels kombinatorischer Auktionen Michael Schwind Institut

Entscheidungsunterstützungssysteme IWI Frankfurt 2004

Dynamische Bepreisung von Güterbündeln mittels

kombinatorischer Auktionen

Michael SchwindInstitut für Wirtschaftsinformatik

Prof. Wolfgang KönigGoethe-University Frankfurt

Sommersemester 2004 – Uni Frankfurt


1. Einführung Kombinatorische Auktionen


Grundlagen der kombinatorischen Auktionen

Was sind Kombinatorische Auktionen (CA)?

Kombinatorische Auktionen sind Auktionen, in denen

ein Bieter nicht nur für einzelne Güter bieten kann,

sondern in einem einzigen Gebot für mehrere Güter

(Güterbündel) gleichzeitig bieten kann.


Warum CA?

• notwendig, da ein Preis, den ein Bieter für ein Gut bereit ist zu zahlen, oftmals auf komplexe Weise von anderen Gütern, die er erhält, abhängt (Synergieeffekte).

• Vorteil, dass ein Bieter solche Synergieeffekte bereits in seinen Geboten ausdrücken kann.

• ebenso geeignet, um mehrere Einheiten eines Gutes simultan zu versteigern.


Synergieeffekte

Es existieren zwei Arten von Synergieeffekten:

Komplementarität

versus

Substitutionalität


Komplementarität

Beispiel Komplementarität:

• es gilt: v(A) + v(B) < v(A+B) Superadditivität

• im Extremfall: v(A)=v(B)=0, aber v(A+B)>0

• z.B. Bieter will von Leipzig nach New York

Gebot für Teilstrecke A (Leipzig-London) 200 €

Gebot für Teilstrecke B (London-New York) 400 €

Gebot für beide Teilstrecken zusammen 800 €


Substitutionalität

Beispiel Substitutionalität

• es gilt: v(A) + v(B) > v(A+B) Subadditivät

• im Extremfall: v(A+B) = max[v(A), v(B)]

• z.B. Bieter möchte ein neues T-Shirt

Gebot für rotes T-Shirt (Gut A) 20 €

Gebot für blaues T-Shirt (Gut B) 20 €

Gebot für beide T-Shirts zusammen (A+B) 30 €


Probleme mit Synergieeffekten

• wenn keine Synergieeffekte Menge von unabhängigen Einzelauktionen denkbar

• bei vorhandenen Synergien Ergebnis nicht mehr effektiv

• noch akuter, wenn Komplementarität und Substitutionalität zwischen den verschiedenen Bietern variieren.


2. Gebote in Kombinatorischen Auktionen


Darstellung von Geboten

• Gebotssprache formale Ausdrucksweise zur Platzierung von Geboten

• zwei Hauptanforderungen: Einfachheit und Ausdrucksstärke

• Trade-Off zwischen der Einfachheit der Sprache und deren Ausdrucksstärke.


Anforderungen an Gebotssprachen

Einfachheit:• Umgang mit den ausgedrückten Geboten muss einfach sein• sowohl in technischer („computationally easy to handle“) als auch • in menschlicher (leicht zu verstehen und zu bearbeiten) Hinsicht

Ausdrucksstärke:• jeder gewünschte Gebotsvektor muss zu formulieren sein• und das möglichst knapp

Eine geeignete Gebotssprache sollte ein gutes Gleichgewicht zwischen diesen beiden Anforderungen finden.


Gebotsformen

Unterschiedliche Gebotsformen (nach Nisan)

• (atomare Gebote)• OR-Gebote• XOR-Gebote• OR-of-XOR-Gebote• XOR-of-OR-Gebote• OR/XOR-Gebote• OR*-Gebote (OR-Gebote mit Dummy-Gütern)


Atomare Gebote

• jeder Bieter kann genau ein Gebot (Si, pi) abgeben

• additiver Wert von zwei oder mehr Gütern (Synergien) kann nicht mit atomaren Geboten ausgedrückt werden

• Beispiel für einen atomaren Gebotsvektor: (A,B,10), d.h. Bieter 1 bietet 10 Geldeinheiten für das Güterbündel A+B.

•sind für Kombinatorische Auktionen von nachrangigem Interesse


OR-Gebote

• Bieter kann beliebige Anzahl von atomaren Geboten abgeben

• d.h. eine Sammlung von Paaren (Si,pi)

• Si ist die gewünschte Teilmenge von Gütern

• pi ist der maximale Preis, den er dafür zahlen will

• Bieter kann dabei für mehrere disjunkte Gebote den Zuschlag erhalten (und/oder-Gebote)

• nur für Gebote, die keine Substitutionalitäten besitzen.

Gegenbeispiel: (A,5) OR (B,10) OR (A,B,13) Widerspruch


XOR-Gebote

• Bieter kann eine beliebige Anzahl an Geboten (Si,pi) abgeben

• implizit enthalten, dass Bieter nur den Zuschlag für ein Gebot erhalten will (entweder/oder-Gebote)

• XOR-Gebote können alle Bewertungen ausdrücken.

• Beispiel Substitutionalität: (A,5) XOR (B,10) XOR (A,B,13)

• Gebot (A,B,13) erhält den Zuschlag, da Erlösmaximierung


Vergleich OR/XOR-Gebote

Es gibt Bewertungen, die mit sehr kurz beschreibbaren OR-Geboten ausgedrückt werden können, aber nun die Darstellung in XOR-Geboten eine exponentielle Größe annimmt.

Die additive Bewertung von m Gütern kann repräsentiert werden mit m OR-Geboten, aber benötigt gleichzeitig XOR-Gebote in der Größenordnung 2m.


OR-of-XOR-GeboteXOR-of-OR-Gebote

• Kombination aus OR- und XOR-Geboten • OR-of-XOR-Gebote: Bieter kann eine beliebige Anzahl von XOR-Geboten abgeben. Implizit gilt, dass er den Zuschlag für mehrere der Gebote erhalten möchte.

• Beispiel: [(A,7) XOR (B,5)] OR [(C,D,8) XOR (E,3)]

• XOR-of-OR-Gebote: Bieter kann eine beliebige Anzahl von OR-Geboten abgeben kann. Implizit gilt, dass er davon allerdings maximal den Zuschlag für ein Gebot bekommen möchte.


3. Design Kombinatorischer Auktionen


Anreizkompatibilität / Wahrheitsgemäßes Bieten

• um eine effektive Allokation der Güter zu ermöglichen, müssen „Spielregeln“ im Vorfeld klar festgelegt werden

• dies ist Aufgabe des Mechanism Design

Effizienz heißt hierbei:• Bieter mit dem höchsten Gebot erhält den Zuschlag • Ziel ist (in der Regel) Erlösmaximierung für den Auktionator

• Bieter könnten durch Absprachen den Gewinn des Auktionators stark einschränken: Beispiel: Verdeckte Information in Geboten der FCC-Auktion


Wahrheitsgemäße Gebote

• Maximierung des Erlöses hängt von den abgegebenen Geboten ab

• keine Garantie, dass diese der tatsächlichen Zahlungsbereitschaft der Bieter entsprechen.Beispiel (drei Bieter 1, 2 und 3 sowie 2 Güter A und B):

v1(A,B) = 100 v2(A,B) = 0 v3(A,B) = 0v1(A) = v1(B) = 0 v2(A) = v2(B) = 75 v3(A) = v3(B) = 40

• bei wahrheitsgemäßem Bieten: A geht an Bieter 2, B an Bieter 3• Bieter 2 hätte den Anreiz, sein Gebot für A bzw. B bis 61 herabzusetzen• Bieter 3 hätte den Anreiz, sein Gebot für A bzw. B bis 26 herabzusetzen• tun dies jedoch beide Gefahr, dass Bieter 1 mit 100 die Auktion gewinnt


Wahrheitsgemäße Gebote

• Im eindimensionalen Fall gilt die Vickrey-Auktion als anreizkompatibel:

• Bieter gibt einzelnes verdecktes Gebot ab (single sealed bid)• Gut wird dem Bieter mit dem höchsten Gebot zum Preis des zweithöchsten Gebots zugeteilt

• Warum ist wahrheitsgemäßes Bieten dominante Strategie?

bi Gebot der Person i , vi wahre Bewertung durch Person iZwei Bieter: erwartete Auszahlung von Bieter 1: prob(b1 > b2)[v1-b2] positives [v1-b2] → max prob(b1 > b2) → v1= b1 negatives [v1-b2] → min prob(b1 > b2) → v1= b1

• Idee ist es nun, diese Auktionsform für den kombinatorischen Fall zu erweitern.

Verallgemeinerte Vickrey-Auktion (GVA)


Die Generalized Vickrey Auction (GVA)

• auch Vickrey-Clarke-Groves (VCG)-Mechanismus genannt

• Ziel ist es, jeden Bieter mit den durch ihn entstandenen sozialen Kosten (Wohlfahrtsverluste) zu belegen.

Voraussetzungen:• i = 1,..,n Konsumenten• j = 1,..,k Güter • Konsumenten bieten für Güterbündel xi = (x1

i … xki)


Formale Darstellung der GVA

• Jeder Bieter i gibt sein Gebot ri(•) ab – dieses kann von seiner wahren Nutzenfunktion ui(•) abweichen.

• Der Auktionator berechnet die Verteilung x*, die die Summe der Nutzenwerte der abgegebenen Gebote unter Berücksichtigung der Restriktionen maximiert.

• Danach berechnet der Auktionator die Verteilung x*~i, die die

Nutzensumme der Gebote ohne die von Bieter i nachgefragten Ressourcen maximiert.

• Bieter i erhält (x*i) und eine Querzahlung von:

• Nutzen von Bieter i aus der Auktion ist:

ij

ijij

j xrxr )()( ~**

ij

ijij

ji xrxrxu )()()( ~***


Formale Darstellung der GVA

Warum ist dieses Auktionsdesign anreizkompatibel?

• Gesamterlös für Bieter i:

• Bieter i beeinflusst lediglich:

• Auktionator maximiert:

Da der Auktionator seinen Nutzen maximiert, sollte Bieter i seine Funktion der Zielfunktion des Auktionators anpassen, also sollte gelten ui(x*) = ri(x*)

j

jij

ji xrxrxr )()()( ***

ij

ji xrxu )()( **

ij

ijij

ji xrxrxu )()()( ~***


Beispiel für die GVA

2 Konsumenten 3 Gütereinheiten

• Optimale Allokation ohne GVA: Konsument 1: 2 Einheiten → 18 GE Konsument 2: 1 Einheit → 9 GE• Allokation mit GVA: ohne Konsument 1 gehen 3 Einheiten an Konsument 2: 9 + 7 + 6 = 22 GE → Konsument 1 erhält Auszahlung von: 18 + [9 - 22] = 18 – 13 = 5 GE

Konsument 1 zahlt 13 GE für zwei Einheiten des Gutes ohne Konsument 2 gehen 3 Einheiten an Konsument 1: 10 + 8 + 5 = 23 GE → Konsument 2 erhält Auszahlung von: 9 + [18 - 23] = 9 – 5 = 4 GE

Konsument 2 zahlt 5 GE für eine Einheit des GutesVerkäufer erhält 13 + 5 = 18 GE

Gut: Einheit 1 Einheit 2 Einheit 3

Konsument 1 10 GE 8 GE 5 GE

Konsument 2 9 GE 7 GE 6 GE


Formale Darstellung des CAP

• zentrale Problem bei CA Auswahl der Gewinner-Bündel, die den Erlös des Auktionators maximieren

• Formulierung als Integer-Programm, aber keine optimale Lösung in polynominalen Zeitaufwand garantiert

• Relaxation in Lineares Programm, aber keine effiziente Lösung garantiert

• Vereinfachung durch Verwendung von Heuristiken


Formale Darstellung desCombinatorial Auction Problems

N Menge der Bieter

M Menge der verschiedenen

Objekte/Güter

m ein Objekt der Menge M

S Bündel von Objekten/Gütern

bj(S) Gebot von Bieter j für Bündel S

b(S) maximales Gebot für Bündel S

i Index Bündel

Annahme: von jedem Gut m ist nur eine Einheit

vorhanden


Formale Darstellung desCombinatorial Auction Problems

als Integer-Programm (CAP1)

MS

sxSb )(max

MSsx 1,0

MixSi

s

1

unter Beachtung der Restriktionen

und

Maximiere die Summe allermaximalen Gebote für dieeinzelnen Bündel SM

kein Objekt aus M kann zumehr als einem Bieter zugeordnet werden

xs = 1, falls Gebot zugeteiltxs = 0, sonst


Formale Darstellung desCombinatorial Auction Problems als

Integer-Programm

MS

sxSb )(max

MSsx 1,0

MixSi

s

1


und

Dilemma:Formulierung nur korrekt für den Fall, dass alle Gebotsfunktionenbj superadditiv

Komplementarität wird hierbei nicht berücksichtigt.

Ausweg: Einführung von Dummy-Gütern


Einführung von Dummy-Gütern

Beispiel:

• Einführung eines Dummy-Gutes g

• Änderung der Gebote des Bieters j (sog. OR*-Gebote)

bj(A) bj(Ag)bj(B) bj(Bg)bj(AB) bj(AB)

• A und B werden nicht mehr getrennt vergeben, da Dummy-Gut g in beiden Geboten vorkommt

• nur eines der drei Gebote kann Zuschlag bekommen


Formale Darstellung des CAP ohne Dummy-Güter (CAP2)

Nj MS

jSySb ),()(max j

MS

NjjSy 1),(

MijSySi Nj

1),(


undkein Bieter erhält mehr als eine Teilmenge S

y(S,j) = 1, falls Bündel S an Bieter j zugeteilt wird, sonsty(S,j)=0

und

NjMSjSy ,1,0),(

stellt sicher, dass keine überlappenden Güterbündelzugeordnet werden

Maximiere die Summe allermaximalen Gebote für dieeinzelnen Bündel SM


Formale Darstellung des CAP ohne Dummy-Güter (CAP2)

Nj MS

jSySb ),()(max j

MS

NjjSy 1),(

MijSySi Nj

1),(


und

und

NjMSjSy ,1,0),(

Erweiterung auf mehrere Einheiteneines Gutes ist leicht möglich.Voraussetzung: jeder Bieter kannnur eine Einheit eines Gutes nach-fragen.

}rechte Seiten derbeiden Gleichungen könnten dann auchWerte > 1 annehmen


Greedy-Allokationals Näherungslösung

Ablauf des Greedy-Schemas

1. Schritt• Gebote werden anhand eines beliebigen Kriteriums sortiert • Sortierung der Liste in auf- oder absteigender Reihenfolge

2. Schritt• Durchführung der Allokation• erstes Gebot der Liste wird angenommen• Im weiteren Verlauf untersucht der Algorithmus der Reihe

nach jedes weitere Gebot und nimmt ein weiteres Gebot an, sofern es nicht mit vorherigen Geboten auf der Liste in Konflikt steht


Beispiel Greedy-Schema

Beispiel für 2 Bieter (1 und 2) und 2 Güter (A und B)

Es liegen folgende Gebote vor:

b1(A)=6 b1(B)=20 b1(A,B)=28 b2(A)=8 b2(B)=18 b2(A,B)=30

Kriterium: durchschnittlicher Gebotspreis je Gut

Sortierung: absteigende Reihenfolge


BeispielGreedy-Schema



b1(A)=6 (6) b1(B)=20 (20) b1(A,B)=28 (14)b2(A)=8 (8) b2(B)=18 (18) b2(A,B)=30 (15)

Kriterium: durchschnittlicher Gebotspreis je Gut

Sortierung: absteigende Reihenfolge


Beispiel Greedy-Schema



b1(A)=6 (6) b1(B)=20 (20) b1(A,B)=28 (14)b2(A)=8 (8) b2(B)=18 (18) b2(A,B)=30 (15)

Kriterium: durchschnittlicher Gebotspreis je Gut Sortierung: absteigende Reihenfolgees ergibt sich folgende Liste

1. b1(B)=20

2. b2(B)=18

3. b2(A,B)=30

4. b1(A,B)=28

5. b2(A)=8

6. b1(A)=6

Bieter 1 erhält BKonflikt

Konflikt

Konflikt

Bieter 2 erhält A


Beurteilung desGreedy-Schemas

• sehr zielgerichtetes Verfahren

• sehr schnelles Verfahren

• Aufwand (n log n)n

• Effizienz hängt sehr stark von gewähltem Kriterium ab

• ungeeignetes Kriterium wäre z.B. „Höhe des Gebotes“


4. Kombinatorische Auktionen in der Praxis


KA-Anwendungen (1)

• Logistik– Netzwerkressourcen (Streckennutzungsrechte für

Güterzüge)– Logistikdienstleistungen (Beschaffung von

Transportkapazitäten: Sears-Logistics, Transport of London)

– Vergabe von Start- und Landezeitslots auf Flughäfen (FAA)

• Lizenzen für Öffentliche Güter– Funk- und Satelliten-TV-Lizenzen– Mobilfunknetze (z. Bsp. UMTS)– Umweltemissionsrechte (RECLAIM)


KA-Anwendungen (2)

• Scheduling– Ressourcen-Scheduling (Nasa-Raumstation)– Kursvergabe in Schulen (University of Chicago) – Verhandlungsprotokolle für die Supply-Chain-

Koordination

• Finanzen– Handel von Finanzprodukten (Combined Value Trading)– NetExchange (Kombinatorische Börse)– Verkauf von Immobilien-Portfolios (Multiattributive

Auction)

• Beschaffungsauktionen– Mars Inc. (Reverse Combinatorial Auction)– Elektrizitätsmarkt (eBay for Electricity Markets)– Chilenische Schulbehörde für Schulspeisung (JUANEB)


Home Depot - Überblick

• Über 964 Geschäfte und 47 Distributionszentren in den USA, Kanada, Puerto Rico und Chile

• Anzahl Produkte ~ 40,000 bis 50,000 • Größe der Geschäfte ~13,000 m2

• Home Depot ($45 Milliarden Umsatz), weltgrößter Verkäufer für Heimwerkerartikel

• Ziel: Einkauf der Transportdienstleistungen

(Quelle: Elmaghraby, W./ Keskinocak, P. (2002) – Combinatorial Auctionsin Procurement, Georgia Institute of Technology)

Fallbeispiel


Home Depot - Problemstellung

• Suche nach potentiellen Spediteuren

• Koordination der Transportrouten• 37 Zentrallager• 1000 Einkaufscenter• 7000 Lieferanten• variable Anzahl von Kunden

• Koordination der Verhandlungen

Fallbeispiel


Klassischer Sourcing-Prozess

Ja/Nein

Ja/Nein

Ja/Nein

.

Ja/Nein

1

2

3

.

500

$ ?

$ ?

$ ?

.

$ ?

NetzwerkHome Depot

Routen wurden einzeln vergeben

Keine Garantie für bestimmte Routenkombinationen möglich

Keine Möglichkeit Effizienzpotentiale einzupreisen

Fallbeispiel


Gebote für Einzelstrecken

Dallas

Phoenix

Long Beach

Omaha

Seattle

Chicago

Atlanta

Charlotte

Camden

Philadelphia

12

3

Fallbeispiel


Home Depot - Kombinatorische Gebote

Route 1

Kombination 1

Kombination 2

1

2

3

.

.

.

$100

$500

$400

Bestehende Routen der Logistiker

Logistikanbieter können für Routen bieten

Eine Route kann in verschiedenen Kombinationen sein

Logistikanbieter können Synergien durch kombinatorische Gebote ausdrücken

Versand-Routen

Versand-Routen

Fallbeispiel


Home Depot - Kombinatorische Gebote

Dallas

Phoenix

Long Beach Ontario

Omaha

Seattle

Chicago

Atlanta

Charlotte

Camden

Philadelphia

Kombination SEA-DFW-NEB-CHI

Fallbeispiel


Home Depot - Bieterinformationen

• Ausgangs- und Zielort (ORT)Punkt: Einzelhändler, Verteilerzentrum, Geschäft

Zone: Gruppe von Geschäften, Gruppe von Händlern

• Routendetails (Ø Entfernungen, Volumina, Ausstattungsdetails…)

• Nachfrageprognosen

Dallas

Phoenix

Long Beach

Ontario

Omaha

Seattle

Chicago

Atlanta

Charlotte

Camden

CouncilBluffs

Philadelphia

Fallbeispiel

ORT ist die Bezeichnungfür eine oder mehrere Ausgangs- oder Zielpunkte.

STRECKE ist ein einzelnes Ausgangs-Zielpunkt-Paar.


Home Depot - Nachfrageprognosen

Detaillierte Bedarfsprognosenfür Produkte und Strecken auf täglicher und wöchentlicherBasis

Produkt Routen Ladungen

Trockencontainer 317 41,847

53’-LKW Trailer 25 5,343

Pritschenwagen 268 5221

Überdachter Lieferwagen 13 41

Summe 623 52,452

Routen Ladungen

Punkt-zu-Punkt 24,574 171

Punkt-zu-Zone 25,153 402

Zone-zu-Punkt 146 3

Zone-zu-Zone 2579 47

Summe 52,452 623

Fallbeispiel


Home Depot - Aufbau der Auktion

• 1. Vorbereitungsprozesse– Bedarfsanalyse– Suche nach potentiellen Lieferanten– Auswahl der Auktionsteilnehmer– Auktionsdesign und Software erstellen– Training für Auktionsteilnehmer

• 2. Auktionsprozess– Informationen für Auktionsteilnehmer– Gebotsabgabe– Auswahl der Gewinner– Vertragserfüllung

• 3. Nachbereitungsprozesse– Auswertung der Auktion– Verbesserung des Designs

Fallbeispiel


Fallbeispiel

Home Depot - Auswahl der Auktionsteilnehmer

• Potentiellen Lieferanten werden Informationen zur Verfügung gestellt– Start und Ziel der Routen– Details über die Routen und Anforderungen– Angabe der benötigten Kapazitäten

• Auswahl der Bewerber anhand bestimmter Kriterien– Finanzlage, technische Ausstattung, Umsatz, u.a.– Von 192 Bewerber wurden 111 ausgewählt


Fallbeispiel

Home Depot - Auktionsdesign (1)

• Reverse Auction• Kombinatorischer Auktionsmechanismus • OR-Gebote und XOR-Gebote• Sowohl Anbieter als auch Nachfrager können

Restriktionen auf ihre Gebote definieren– Gesamtumsatz (max, min)– Kapazität– Geographisches Gebiet

• Gebotsregeln– Einzelstrecken – Streckengruppen


Fallbeispiel

Home Depot - Auktionsdesign (2)

•Fairness•Reduzierter Wettbewerb

•Sicherung der Qualität•Verweigerung der Gebotsabgabe

single-round multi-round

opensealed

Senkung der Frachtrate: single bid iterative bids

Gebot soll minimale Frachtrate des Spediteurs abbilden, keine Gebote unter dem langfristigen Reservationspreis


Fallbeispiel

Home Depot KA-Support

• Jeder Spediteur entsendete einen Repräsentant der mindestens einen halben Tag am KA-Training teilnahm

• Funktion der Repräsentanten variierte zwischen Pricing-, Sales und Logistik Experten

• Einrichtung einer gebührenfreien Hotline


Fallbeispiel

Home Depot – KA-Software

• Shipper Bid Support (SBS)– Analyse des Transportnetzwerkes– Auswahl der Routen für den Auktionsprozess

• Carrier Bid Response (CBR)– GUI zur Visualisierung der Struktur des Versender-

Transportnetzwerkes– Standardisierte Vorlage für Gebotsabgabe

• Bid Selection Optimization (BSO)– Auswahl der optimalen Gebotsstruktur

(Streckenkombinationen)– Lösung des „Winner-Determination-Problems“– Multivariate Kombinatorische Auktion:

Neben dem Preis gehen auch andere Kriterien in den Gebotsprozess ein: Qualität, Zuverlässigkeit usw.


Fallbeispiel

Home Depot: Gebotsauswahl

• Auswahl einer Untermenge aus allen Geboten– Alle Routen müssen abgedeckt sein– Restriktionen müssen erfüllt sein– Definierte Gesamtkosten dürfen nicht überschritten

werden– Weitere nicht preisbezogene Kriterien, wie Reliabilität

und ausgeglichene Verteilung zwischen Spediteuren

• Dominierte Gebote werden vorab gestrichen– Bsp.: Zwei, abgesehen von der Reliabilität des

Spediteurs, identische Gebote• Gebot mit der geringeren Reliabilität wird gestrichen


Fallbeispiel

Auktionsprozess & Resultate

• Es wurden 96 Gebote abgegeben (von 111 Teilnehmer)

• Aufgrund nicht optimaler Resultate erhielten nur 80% der Routen einen Zuschlag

• Start einer zweiten Auktionsrunde zur Versteigerung der verbliebenen 20% an Routen– 62 Teilnehmer– 36 abgegebene Gebote


Fallbeispiel


• Anzahl Gebote pro Route– Durchschnitt: 14– Minimum: 2– Maximum: 33

• Wenigstens 5 (10) Spediteure bieten auf– 94,4% (73,4%) der Routen und decken damit– 97,1% (86,7%) der Frachten ab.


Fallbeispiel


• Der Auktionsprozess wurde von Home Depot als erfolgreich bewertet.– Senkung der Frachtraten– „Viele“ Spediteure zufriedener mit neuem Procurement

Prozess

• Auktionsprozess soll fortgesetzt werden, mit einigen Änderungen, aufgrund der Auswertung der Auktion– Mind. zwei Repräsentanten der Spediteure mit

längeren Trainingszeiten, da einige den Prozess zu komplex fanden

– Multi-round statt single-round– Weiterentwicklung der Software


Zusammenfassung der Erfolgsfaktoren für Kombinatorische Auktionen

• Leistungsfähige Technologie– Winner-Determination– Gebotsannahme– Sicherheit

• Problemspezifisches Auktionsdesign– Spieltheorethische Analyse– Transparenz und Nachvollziehbarkeit der Auktion

• Usability– Einfache Gebotsabgabe– Intensive Schulung und Support bei der Nutzung

Fallbeispiel


Softwareprodukte für Kombinatorische Auktionen

Softwareprodukte für Kombinatorische Auktionen

„SBIDS“ von SAITECH-INC

„OptiBid“ von Logistics.com (u.a. Ford, Wal-Mart)

für transportlogistische Problemstellungen

Fallbeispiel


5. Ermittlung der Gewinner in Kombinatorischen Auktionen


Dynamische Bepreisung von Güterbündeln

Anbieter 1

Anbieter 2

Anbieter 3

Anbieter 4

Anbieter 5

Hotel MietwagenFlug

240 EUR

130 EUR

220 EUR

380 EUR

360 EUR

Kostenminimale Kombination

Kosten=460

Mietwagen HotelFlug

Das Projekt „Dynamische Bepreisung von Güterbündeln“ entwickelt Werkzeuge zur automatischen kostenminimalen Beschaffung von Komponenten auf verschieden Märkten auf Basis kombinatorischer Auktionen. Die Werkzeuge dienen etwa Logistikunternehmen zum web-basierten Sourcing von Transportkapazitäten für von ihnen angebotenen Dienstleistungen. Ähnlich können z. B. Internet Service Provider für Sonderverkäufe zusätzlich zu ihrer Infrastruktur notwendige kostenminimale Rechnerkapazitäten und Bandbreite automatisch beschaffen.


Bereitstellung von Informationsdienstleistungen

und Produkten (IDIP)

• Annahmen:

Produktionsfaktoren für die Bereitstellung von IDIP in B2B und B2C Märkten, z.B. web-basierte Videokonferenzen, Video-on-Demand-Anwendungen, Portfolio Analyse – Rechenleistung– Volatiler Speicher– Nicht-volatiler Speicher– Netzwerkbandbreite


• Allokationsproblem: Gewinnoptimale Zuweisung von bepreisten

Ressourcen

• Mögliche Allokationsmechanismen: – Reinforcement Learning Scheduling Mechanismen

(Schwind & Wendt 2002) – Kombinatorische Auktionen (Rassenti et al. 1982)

Bereitstellung von Informationsdienstleistungen

und Produkten (IDIP)


Eigenschaften kombinatorischer Auktionen• Kombinatorische Auktionen (CAs) sind Auktionen, die es Bietern erlauben für ganze Güterbündel zu bieten.

(Weighted Set Packing Problem)• Dabei ist es notwendig die Wertabhängigkeit eines Gutes für den Bieter in Abhängigkeit von der Verfügbarkeit anderer benötigter Güter auszudrücken.

Synergieeffekte Subadditivität: v(A) + v(B) < v(A+B) Substitutionalität Grenzfall: V(A+B)= max [V(A), V(B)] Superadditivität: v(A) + v(B) > v(A+B) Komplementarität Grenzfall: V(A)=V(B)=0, aber V(A+B)>0

Grundlagen kombinatorischer Auktionen


Schwierigkeiten:

• Formulierung von Geboten die alle Synergieeffekte enthalten ist sehr schwierig

• Optimale Allokation der Gebote ist NP-vollständig

• Offenbarung der wahren Zahlungsbereitschaft

Lösung des kombinatorischen Allokationsproblems


• Produktionsfaktoren: r1 … rS

• Belegungsplan besteht aus gleichlangen Time-Slots: t1…tN

• Tasks werden als Ressourcenanfragen qi,j(rs,tn) ausgestattet mit einer Zahlungsbereitschaft pi,j formuliert.• Annahme eines Gebots bi,j von Agent i wird durch die Variable xi,j angezeigt.

Optimierungskalkül:),(),(max max

1 1,,

1 1,, ns

I

i

J

jjinsji

I

i

J

jjiji trqxtrqtosubjectxp

IiwherexandNnSswhereJ

jji ,,1,1,,1,,,1

1,

Lösung des kombinatorischen Allokationsproblems


• Gebot bi,j wird als Gebotsmatrix BM(N,S) formuliert.• Jeder Eintrag beschreibt den Betrag qi,j(rs,tn) der benötigten Ressourceneinheiten. • Tasks werden als Agenten ai beschrieben und geben (exklusive) Gebote bi,j ab.• Gebote bestehen aus einer Anzahl von Ressourcenanfragen (statische Nachfrage) und einer als Preis bezeichneten Zahlungsbereitschaft.Arten von Ressourcenanfragen: • Unstrukturierte Gebote• Substrukturierte Gebote• Strukturierte Gebote

Preisgesteuertes Ressourcenallokationsszenario


r1

r4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

4

t =Time-Slots

2 3

3 1 2

5

1

1

3 2 2 5

1

3

5

1

5 2

2

1

3

4

5 2

2

2

3

2

1

1

5 2

3

2

1 3

2

2

1

3

1

1 53 1

4

2 1

4 2

s

5

r1

r4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

3 3 3

4 4 4 4

4 1 1 1 155

33

4

5

4

2

5

2 2

4 4

2

1

3

1

1

2

1 1

1

1

2

1 5

3

5

Un

stru

ktu

rier

t

Su

bstr

uktu

rie

rt

r1

r4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

3 3 3

4 4 4

1 1 1

3

155

3 3 2

4

14

5

4

5

4 4

2

1

2

1 1

2

4

5

1

2

1

2

Str

uktu

rie

rt

4 Ressourcen-24 Perioden-Problem


Greedy Algorithmus für Kombinatorische Auktionen

1. i=0 : ZählerBacc : Leere Menge der akzeptierten Geboterg : Geordnete Gebotsliste (z. Bsp. nach pi,j / qovl

i,j Quotient)

2. v : Index des i-ten Gebotes der Permutation rg

av : Bieter von v

3. Wenn Bacc ein Gebot aus av enthält, gehe zu Schritt 4.

4. Wenn das Einfügen von Gebot v in Bacc die Ressourcenbeladungs- Restriktion verletzt, gehe zu Schritt 4.

5. Füge Gebot v in Bacc ein.

6. Stopp, wenn i > l.

7. Erhöhe Zähler i um 1 und Gehe zu Schritt 2.


Simulated Annealing Combinatorial Auction Algorithm

1

Simulated Annealing CA-Algorithmus (SA-CAA) • Problem: Anfangstemperatur und Abkühlungsrate sind entscheidend für die Simulated Annealing (SA) Performance• Anfangstemperatur: 80% der Austauschoperationen akzeptieren eine Verschlechterung der Fitnessfunktion:

• Temperatur wird alle 100 Schritte mit einem Abkühlungsfaktor von 0.99 gesenkt.

8.0exp1

1

kT

E

Ni

N

imeaniEkT )(5


1. Initialisiere mit Random Walk

2. Wahrscheinlichkeit (WS) eines Gebotstausches: 0.5WS, dass ein Gebot hinzugefügt wird: 0,25

3. Wenn die neue Lösung die Ressourcenbeladungs-Restriktion nicht verletzt und [der Gewinn des Auktionators zunimmt ODER random(0,1) ≤ Pacc(Δ E) ] Operation ausführen

4. Wende den Abkühlungsplan an, bis das Stopp-Kriterium erreicht ist.

Simulated Annealing Combinatorial Auction Algorithm

2


SA-CAA Fitness für unstrukturierte Gebote


Genetic Combinatorial Auction Algorithm 1

Random Key (RK) Encoding:

• Verwendung von realwertigen Zufallszahlen zur Kodierung der Lösungen

• Länge der Schlüssel gleicht der an den Auktionator gesendeten Anzahl von Geboten (z.B., 4 Schlüssel für 4 Gebote: [0.73; 0.32; 0.54; 0.07])

• Gebote werde nach ihren Realwerten sortiert (in obigem Beispiel: [1 3 2 4])

• Zu Ermittlung der Fitness eines RK-Individuums, werden die Gebote nach dieser Reihenfolge in Bacc eingeordnet.(Dabei limitiert natürlich die maximale Ressourcenauslastung die Anzahl eingefügten Gebote.)


Genetic Combinatorial Auction Algorithm 2

1. Initialisiere erste Generation mit Zufallsschlüsseln.

2. Tournament-Selektion in nächster Generation.

3. Two-Point-Crossover zwischen zufällig ausgesuchten Paaren.

4. Mutation: Ersetze Wert in Schlüssel mit WS 1%

5. Bewertung der Fitness analog zu Greedy-Schema (aber entsprechend der zufälligen Schlüsselfolge)

6. Weiter mit Schritt 2 bis Stopp-Kriterium erreicht ist.


GA-CAA Fitness für unstrukturierte Gebote


structured unstructured

Performanceüberblick: Erlös des Auktionators vs. Anzahl der

Agenten


Versuchsanordnung:• 50 Simulationsläufe (Auktionen)• AM: qmax = 8, S = 4, N = 24• BM: qbmax = 3, J = 4 (jeder Agent gibt 4 XOR Gebote ab) • bid price range: pmin = 1, pmin = 3, ptso = 0,33Ergebnisse:• SG-CAA: niedrigste Performance, schneller Algorithmus• SA-CAA: übertrifft den SA-CAA um 20% für alle Problem-

instanzen, strukturierte Gebote erhöhen die Gesamtperformance, Rechenzeit erhöht sichum Faktor 10.000 verglichen mit SG-CAA.

• GA-CAA: leichter Anstieg der Lösungsqualität, weiterer Anstieg der Rechenzeit

Versuchsanordnung und Ergebnisse


Ausblick and Referenzen

Ausblick:• Einbringen und Evaluieren von alternativen Lösungs- ansätzen: B&B, exakt

Referenzen:• http://www.combinatorial-auction.de• http://www.dynamic-pricing.org• Schwind, Michael; Stockheim, Tim; Rothlauf, Franz Optimization Heuristics for the Combinatorial Auction Problem In: Proceedings of the Congress on Evolutionary Computation (CEC 2003), pp. 1588-1595; Canberra, Australia


Literatur (u.a.)

Lehman, Daniel et al. „Truth Revelation in Approximately Efficient Combinatorial Auctions“, 1999

MacKie-Mason, Jeffrey K.; Varian, Hal: „Generalized Vickrey Auctions“, 1994

Nisan, Noam: „Bidding and Allocation in Combinatorial Auctions“, 1999

Varian, Hal: „Economic Mechanism Design for Computerized Agents“, 2000

de Vries, Sven; Vohra, Rakesh: „Combinatorial Auctions: A Survey“, 2001http://www.is-frankfurt.de/ldb

Documents

Entscheidungsunterstützungssysteme IWI Frankfurt 2004 Dynamische Bepreisung von Güterbündeln mittels kombinatorischer Auktionen Michael Schwind Institut