Synergie und Koordination in dezentral planenden Organisationen

+
Synergie und Koordination in dezentral planenden Organisationen
∗
Peter Gomber, Claudia Schmidt, Christof Weinhardt
Stichworte: Auktionen, Anreizstrukturen, dezentrale betriebliche Planung, Kooperationen, marktliche Koordinationsmechanismen, Multi-Agenten-Systeme, Synergie.
Zusammenfassung: Dynamische Märkte, hoher Innovationsdruck und ein ausgeprägter Zeitwettbewerb - vor diesem Hintergrund suchen Unternehmen nach neuen Organisationsformen, die sich in
dezentralen innerbetrieblichen Strukturen und dem Versuch, Kernkompetenzen über Unternehmensgrenzen hinweg zu bündeln, konkretisieren. Unabhängig davon, auf welcher dieser Ebenen autonome Organisationseinheiten kooperieren, geht es vor allem darum, daß Synergiepotentiale ausgeschöpft werden, und jeder Kooperationspartner dabei einen individuellen Vorteil erzielen kann - eine
Aufgabe, die marktliche Koordination nahelegt. Multi-Agenten-Systeme (MAS) sind in der Lage,
solche Organisationsstrukturen abzubilden, die lokalen Interessen der autonomen Einheiten zu wahren und für ein globales Ziel zu koordinieren. Anhand eines detaillierten Anforderungskatalogs an
marktliche Mechanismen wird in dieser Arbeit, aufbauend auf einer Analyse einfacher Auktionen, ein
Koordinationsmechanismus für MAS entwickelt. Diese mehrstufige erweiterte Vickrey Auktion
(MEVA) fördert die Bildung von Kooperationen über geeignete Anreizstrukturen für die Nutzung
von Synergien.
Synergy and Coordination in Decentralized Planning Organizations
Keywords: auctions, incentive structures, decentralized operational planning, cooperation, marketlike coordination mechanisms, Multi-Agent-Systems, synergy.
Abstract: Due to increasing dynamics of markets and decreasing innovation cycles most companies
are looking for new organizational forms. They enforce a trend towards decentralized internal structures and towards interorganizational cooperations (e.g., Virtual Corporations). Irrespective of the
level on which autonomous organizational units cooperate, the main objective is to get use of the
attainable synergetic effects and to guarantee individual advantages for each participant in cooperations. This suggests the use of market-like coordination mechanisms. Multi-Agent-Systems (MAS)
are able to model such organizational structures and to maintain and coordinate the local intentions of
the autonomous units with respect to a global goal. Using a detailed requirements specification concerning market-like coordination mechanisms, in this paper a mechanism for MAS is developed based on an analysis of simple auctions. This multi-staged extended Vickrey auction (MEVA) encourages the formation of cooperations by suitable incentive structures.
∗
Dipl.-Kfm. Peter Gomber, Dipl.-Wirt.-Math. Claudia Schmidt, Prof. Dr. Christof Weinhardt, Lehrstuhl für BWL-Wirtschaftsinformatik, Universität Gießen, Licher Str. 70, D-35394 Gießen, email{peter.gomber|claudia.schmidt|christof.weinhardt}@wirtschaft.uni-giessen.de.
+
Diese Arbeit entstand im Rahmen des im Schwerpunktprogramm „Verteilte DV-Systeme in der
Betriebswirtschaft“ von der Deutschen Forschungsgemeinschaft geförderten Projekts „Integration
von Koordinations- und Kooperationsmechanismen zur verteilten Lösung betrieblicher Planungsprobleme“.
1
Einleitung
Während Fragestellungen der technischen Realisierbarkeit von Kommunikationsinfrastrukturen zur
Vernetzung flacher, dezentraler Organisationsstrukturen weitgehend geklärt zu sein scheinen, rückt
das organisatorische Gestaltungspotential der IKS [PiMa93] in den Vordergrund der aktuellen Forschungsbemühungen in der Wirtschaftsinformatik. Dabei ist für die Gestaltung dieser Strukturen von
großer Bedeutung, daß die individuellen Planungen der Organisationseinheiten einem übergeordneten Ziel gerecht werden. Im Kontext dieser Arbeit kann sich die Zusammenarbeit dieser Einheiten
sowohl auf eigenständige Unternehmen beziehen, die beispielsweise im Sinne eines Virtuellen Unternehmens [MeFa95; FiHe96] kooperieren, als auch auf (inner-)betriebliche Profit-/Cost-Center,
Abteilungen [Kirn96] und/oder einzelne Ressourcen (z.B. Maschinen) [MöWe96; ScWe95], die
jeweils ‘eigenverantwortlich’ innerhalb eines Unternehmens agieren.
Auf überbetrieblicher Ebene ist eine marktliche Koordination bereits häufig Realität. Mit dem Trend
zu flachen Hierarchien und dezentralen Strukturen in den Unternehmen werden verstärkt auch
marktliche Ansätze zur Koordination der Planungen unternehmensinterner Organisationsstrukturen
eingesetzt, um das Gestaltungs- und Problemlösungspotential von Märkten auch für (inner)betriebliche Planungsaufgaben nutzbar zu machen.
Gegenstand dieser Arbeit sind inner- und überbetriebliche Planungsprobleme dezentraler Organisationen, die losgelöst von einem speziellen betrieblichen Anwendungsproblem, wie etwa der Auftragsvergabe in einer Konzernspedition oder der Belegung von Maschinen, betrachtet werden. Abstrahiert man von jeder Fachdomäne, so lassen sich für die hier betrachteten Planungsaufgaben folgende
Grundcharakteristika festmachen:
• Planungssubjekte sind beliebige Organisationseinheiten, die in einem Verbund mit anderen
Organisationseinheiten eine Aufgabe lösen und dabei - unter Wahrung ihrer Autonomie und ihrer
lokalen Interessen - einem globalen Ziel, hier einer effizienten Allokation der insgesamt verfügbaren Ressourcen, gerecht werden. Sie verhalten sich ökonomisch rational, indem sie ihren individuellen Gewinn maximieren.
• Die Planungsobjekte können als Aufträge betrachtet werden, die durch ihren Erlös, die Beschreibung der zu ihrer Erfüllung notwendigen Aktivitäten und gegebenenfalls weitere Restriktionen gekennzeichnet sind.
1
• Alle Planungssubjekte sind in der Lage, eine individuelle Bewertung des Auftrags vorzunehmen.
Den folgenden Überlegungen wird das Kalkül des dispositionsspezifischen Deckungsbeitrags
(dDB) [Rieb85] als Bewertungsgröße zugrunde gelegt.1
• Jedes Planungssubjekt verfügt ausschließlich über lokales Wissen, z.B. in Form von Fakten, Planungsmethoden etc., und ist mit weiteren Planungssubjekten über eine Kommunikationsinfrastruktur verbunden.
Es handelt sich hierbei um Planungsprobleme, die typischerweise aufgrund ihrer Komplexität mit den
Methoden des Operations Research nicht exakt lösbar sind. Die aus diesem Grund häufig verwendeten heuristischen Verfahren lassen in der Regel keine Aussage über die Qualität der erzeugten
Lösung zu. Auch die Beschaffung und Bereitstellung der lokalen Informationen für eine zentrale Planungsinstanz bringen enorme Probleme mit sich und sprechen für einen dezentralen Planungsansatz.
Dies zeigen zahlreiche aktuelle Forschungsprojekte und -berichte [Kirn94; FiKu93; FaSp93; ZeBo93; MaWe95]. Dort steht jeweils eine konkrete betriebliche Problemstellung im Mittelpunkt, deren Lösung von einem Verbund intelligenter bzw. teilintelligenter Informationssysteme generiert wird.
Diese Multi-Agenten-Systeme (MAS) stellen das notwendige Instrumentarium zur Verfügung, um
eine Abbildung verteilter, autonomer Einheiten und insbesondere deren Interaktion auf der Basis
kommunizierender Informationssysteme - man spricht dann von Agenten - zu ermöglichen. Die einzelnen Agenten repräsentieren sowohl das lokale Wissen als auch die individuellen Intentionen [BoGa88, 3]. Wesentlich für die Qualität der gemeinschaftlichen Problemlösung in MAS ist die Implementierung geeigneter Koordinationsmechanismen in diesen Verbund.
Dieser Arbeit liegt die Fragestellung zugrunde, ob es möglich ist, auf der Grundlage obiger domänenbzw. anwendungsunabhängiger Charakteristika Koordinationsmechanismen zu identifizieren, die zur
Lösung spezieller Klassen betrieblicher Planungsprobleme besonders geeignet sind.
Daraus ergibt sich zunächst die Frage:
(A)
Welche Anforderungen müssen Koordinationsmechanismen in MAS erfüllen, damit
(A1) sie den Planungsprozeß autonomer Agenten zur Erreichung eines globalen Ziels
ökonomisch sinnvoll unterstützen und
2
(A2) der Planungsprozeß einer informationstechnischen Systemumgebung überlassen
werden kann?
Um aus globaler Sicht ein Optimum zu erreichen, genügt jedoch die einfache Zuordnung von Aufträgen auf einzelne Aufgabenträger oftmals nicht. Erst wenn über die Koordination (im Sinne der Zuordnung des Auftrags) hinaus Kooperationen bei der Durchführung von Teilaufträgen entstehen, kann
das wesentliche ökonomische Potential einer gemeinschaftlichen Aufgabenerfüllung ausgeschöpft
werden: die Entstehung von Synergieeffekten bei der Kooperation dezentraler Organisationseinheiten. Deshalb schließt sich unmittelbar die zweite und zentrale Fragestellung dieser Arbeit an:
(B)
Welchen Anforderungen muß ein Koordinationsmechanismus genügen und wie muß er
beschaffen sein, damit er die Kooperation unter den Akteuren nicht nur angemessen
berücksichtigt, sondern sogar fördert, um so Synergiepotentiale nutzbar zu machen?
In Abschnitt 2 wird zur Vertiefung der Fragestellung (A) zunächst diskutiert, wie Aufträge einzelnen
Organisationseinheiten zugeordnet werden können. Es werden allgemeingültige Anforderungen an
marktliche Koordinationsmechanismen aufgestellt und alternative Auktionsformen hinsichtlich ihrer
Eignung für die Koordinationsaufgabe analysiert.
Diese Anforderungen an Koordinationsmechanismen werden in Abschnitt 3 vor dem Hintergrund der
Fragestellung (B) erweitert. Anschließend wird in Abschnitt 4 ein Koordinationsmechanismus dargestellt, der im Rahmen des DFG-Forschungsprojekts „Dezentrale betriebliche Planung“2 speziell für
die Koordination kooperativer Aufgabenerfüllung entwickelt wurde und den Anforderungen genügt.
Abschnitt 5 faßt die wichtigsten Ergebnisse zusammen und gibt einen kurzen Ausblick bezüglich der
künftigen Forschungsbemühungen im Rahmen des Projekts.
2
Auktionen als marktliche Koordinationsmechanismen
In diesem Abschnitt werden als marktliche Koordinationsmechanismen Auktionen hinsichtlich ihrer
Eignung für den Einsatz in der dezentralen betrieblichen Planung und für die Umsetzung in MAS untersucht. Dafür wird zunächst ein Katalog wichtiger Anforderungen an Koordinationsmechanismen
aufgestellt, um anschließend alternative Auktionsformen anhand dieser Kriterien beurteilen zu können. Dabei soll in diesem ersten Schritt die Möglichkeit kooperativer Aufgabenerfüllung (Fragestellung (B)) außer acht gelassen werden.
3
2.1
Anforderungen an marktliche Koordinationsmechanismen
Das Ziel aus übergeordneter Sicht in der jeweiligen Planungssituation ist es, bei lokaler Optimierung
eine effiziente Zuordnung von Aufträgen auf die einzelnen betrieblichen Organisationseinheiten zu
erreichen. Der Mechanismus soll daher sicherstellen, daß der Agent mit der höchsten Wertschätzung
den Auftrag erhält, also derjenige Agent mit dem - nach der für das Planungsproblem ausgewählten
Bewertungsmethode - höchsten dDB. Das erste Kriterium, das für einen Koordinationsmechanismus
zu prüfen ist, bezieht sich auf Fragestellung (A1) und damit auf eine
(i) effiziente Allokation
der lokalen Ressourcen.
Wenn der Planungsprozeß einem Verbund intelligenter Informationssysteme überlassen werden soll
(Fragestellung (A2)), muß sichergestellt werden, daß die Informationssysteme in der Lage sind, die
Interessen der von ihnen jeweils repräsentierten Organisationseinheit zu vertreten. Dies ist sicher
dann nicht der Fall, wenn der gewählte Koordinationsmechanismus taktisches Verhalten bzw. die
Beschaffung von Informationen über die Wertschätzung anderer Agenten belohnt.
Ein Koordinationsmechanismus muß folglich gewährleisten, daß diese Informationsbeschaffung nicht
auf Kosten anderer Teilnehmer des Verbunds ausgenutzt werden kann. Nur unter diesen Voraussetzungen werden die menschlichen Repräsentanten der Organisationseinheiten bereit sein, sich in einem
solchen Verbund durch IT-Agenten vertreten zu lassen. Mit anderen Worten: Wenn menschliche
Agenten in einem marktlichen Koordinationsmechanismus keinen Vorteil aus einer wie oben beschriebenen Informationsbeschaffung erzielen können, läßt sich das Agieren im Koordinationsmechanismus auf ein quasi-mechanisches Verfahren reduzieren, das einem informationstechnischen Prozeß,
hier einem MAS, überlassen werden kann. Die zweite Anforderung an den Mechanismus lautet daher:
(ii) Informationsbeschaffung/Taktieren nicht rational.
Während die globale Akzeptanz durch eine effiziente Ressourcenallokation sichergestellt ist, kann die
individuelle, lokale Akzeptanz durch die einzelnen Agenten nur dann erreicht werden, wenn die Teilnehmer ihren Konkurrenten keine bzw. möglichst wenige Informationen preisgeben müssen. Die
Aufrechterhaltung bestehender Informationsasymmetrien verhindert, daß Agenten aus dem Verhalten
anderer Agenten lernen, um diese Informationen und das so erworbene Wissen bei wiederholter
4
Anwendung des Koordinationsmechanismus ausnutzen zu können. Der Mechanismus darf also nicht
so gestaltet sein, daß Informationen der einzelnen Teilnehmer an die übrigen weitergegeben werden.
Dies führt zum dritten Kriterium:
(iii) Informationsoffenbarung nicht erforderlich.
Um im Koordinationsmechanismus die Kommunikationskosten weitgehend zu reduzieren, sollte die
Anzahl auszutauschender Nachrichten möglichst klein sein. Es ist also für einen
(iv) geringen Kommunikationsbedarf
zu sorgen. Tabelle 1 listet die identifizierten Kriterien zusammenfassend auf:
Kriterium
Zur Sicherung ...
(i) effiziente Allokation
... der globalen Akzeptanz
(ii) kein Informationsbedarf/Taktieren
... der konzeptionellen Umsetzbarkeit in MAS
(iii) keine Informationsoffenbarung
... der lokalen Akzeptanz
(iv) geringer Kommunikationsbedarf
... niedriger Kommunikationskosten
Tabelle 1: Anforderungen an Koordinationsmechanismen
2.2
Marktliche Koordinationsmechanismen im Vergleich
In diesem Abschnitt werden vier alternative Auktionsformen [AfMi87, 701-703] vorgestellt und
anhand der oben identifizierten Kriterien beurteilt. Dazu werden Annahmen eingeführt, die der folgenden Analyse dieser einfachen Auktionsformen zugrunde liegen:
• Versteigert wird jeweils genau ein Auftrag als Ganzes.
• Der Auftraggeber hat keine Präferenzen, welche der Organisationseinheiten letztlich den Auftrag
ausführt.
5
• Die Organisationseinheiten/Agenten verhalten sich ökonomisch rational, d.h. sie bieten innerhalb
der Auktion so, daß sie die Wahrscheinlichkeit, den Auftrag zu erhalten, maximieren.
• Die Organisationseinheiten/Agenten verhalten sich symmetrisch, d.h. im Falle einer gleichen Wertschätzung des Auftrags geben sie bei der Auktion Gebote in gleicher Höhe ab.
Die ENGLISH AUCTION ist eine Auktionsform, in der die Bieter ihre Gebote so lange sukzessiv erhöhen, bis nur noch ein Bieter übrig bleibt. Dieser erhält den Zuschlag zu dem von ihm zuletzt genannten
Gebot.
Bei der DUTCH AUCTION gibt der Auktionator einen Startpreis bekannt, den er so lange senkt, bis
der erste Bieter ein Gebot abgibt. Dieser erhält den Zuschlag zu dem von ihm genannten Gebot.
In der FIRST PRICE SEALED BID AUCTION gibt jeder Bieter genau ein verdecktes Gebot ab. Den Zuschlag erhält der Bieter mit dem höchsten Gebot zu dem von ihm genannten Gebot.
Die SECOND PRICE SEALED BID AUCTION oder auch VICKREY AUCTION [Vick61] unterscheidet sich
von der FIRST PRICE SEALED BID AUCTION lediglich dadurch, daß der Bieter mit dem höchsten Gebot den Zuschlag zu dem Preis des zweithöchsten Gebots erhält.
[AfMi87, 711; Kräk92, 13] zeigen, daß unter den oben genannten Annahmen für alle vier Auktionsformen die (i) effiziente Allokation gegeben ist, denn in jedem Fall erhält der Bieter mit dem
höchsten Gebot den Zuschlag. Dabei ergibt sich bei allen Auktionsformen der gleiche Erwartungswert für den Preis: jeweils das zweithöchste Gebot.
Die Anforderung, daß (ii) Informationsbeschaffung/Taktieren nicht rational ist, wird nur von der
ENGLISH AUCTION und der VICKREY AUCTION erfüllt. Durch die offenen Gebote in der ENGLISH
AUCTION,
kennen die Bieter das Verhalten ihrer Mitbieter, so daß keine weiteren Informationen
eingeholt werden müssen und nicht taktiert wird. Man kann zeigen, daß rationale Bieter in der
VICKREY AUCTION nicht taktieren, d.h. ihre eigene Wertschätzung als Gebot abgeben und keine
Informationen beschaffen [WeGo96, 12f.]. Sowohl bei der DUTCH AUCTION als auch bei der FIRST
PRICE SEALED BID AUCTION
werden die Bieter Annahmen über das Verhalten ihrer Konkurrenten
treffen und folglich taktieren, indem sie strategische Gebote abgeben [Kräk92, 22ff.].
Für die DUTCH AUCTION, die FIRST PRICE SEALED BID AUCTION und die VICKREY AUCTION ist (iii)
Informationsoffenbarung nicht erforderlich; in den beiden letztgenannten, weil verdeckte Gebote
abgegeben werden, und in der DUTCH AUCTION, weil das erste abgegebene Gebot schon den Zu6
schlag erhält. Demgegenüber werden in der ENGLISH AUCTION bereits durch die offene Gebotsabgabe Informationen preisgegeben.
Ein (iv) geringer Kommunikationsbedarf besteht bei den verdeckten Auktionen. Hier gibt jeder
Bieter genau ein Gebot ab, das nur dem Auktionator bekannt gemacht wird. In der DUTCH AUCTION
wird insgesamt sogar nur ein Gebot abgegeben. Wenn man zudem davon ausgeht, daß die sukzessiven Preissenkungen getaktet vorgenommen werden, müssen die Bieter nur über Startpreis und Taktung informiert werden. Folglich ist auch hier der Kommunikationsbedarf gering. Bei der ENGLISH
AUCTION
entsteht durch die offenen Gebote, die über die bestehende Kommunikationsinfrastruktur
allen Agenten bekanntgegeben werden müssen, im Mittel ein hoher Kommunikationsbedarf.
Folgende Tabelle 2 gibt einen Überblick über die Eignung der einfachen Auktionsformen als Koordinationsmechanismen für den Einsatz in MAS:
Kriterien
english
auction
dutch
auction
first price sealed
bid auction
Vickrey
auction
(i)
effiziente Allokation
√
√
√
√
(ii)
Informationsbeschaffung/
Taktieren nicht rational
√
-
-
√
(iii) Informationsoffenbarung
nicht erforderlich
-
√
√
√
(iv) geringer Kommunikationsbedarf
-
√
√
√
(Taktung)
Tabelle 2: Vergleich alternativer Auktionsformen
Von den betrachteten Auktionsformen erfüllt als einzige die VICKREY AUCTION alle Anforderungen
und bietet sich daher als marktlicher Koordinationsmechanismus für die hier betrachtete Planungsaufgabe an.
3
Kooperationen in Koordinationsmechanismen
Die in Abschnitt 2 aufgezeigten Anforderungen an Koordinationsmechanismen für die dezentrale
betriebliche Planung und die VICKREY AUCTION, die diesen Kriterien genügt, werden nun im Hinblick
auf die Möglichkeit der Nutzung von Synergiepotentialen durch Kooperationen untersucht (Fragestellung (B) aus Abschnitt 1). Kooperierende Organisationseinheiten/Agenten werden im folgenden
7
als Koalitionen bezeichnet. Dabei liegt der Fokus der Betrachtung nicht auf der Frage, wie sich Koalitionen bilden, sondern ob Koalitionen entstehen und wie diese untereinander um den Zuschlag konkurrieren.
3.1
Anforderungen an Koordinationsmechanismen bei Kooperation
Bei dieser erweiterten Fragestellung ist ebenso die Erreichung des globalen Ziels von zentraler Bedeutung. Als erstes Kriterium ist daher auch hier die
(i) effiziente Allokation für Koalitionen
zu prüfen. Dabei muß der Mechanismus sicherstellen, daß der einzelne Agent oder die Koalition mit
der höchsten Wertschätzung (hier dem höchsten dDB) den Zuschlag erhält. Ziel ist jetzt also nicht
mehr eine effiziente Allokation auf einzelne Agenten, sondern auf alle möglichen Koalitionen des
Verbunds und damit auf alle Elemente der Potenzmenge der beteiligten Agenten. Dies kann allerdings
nur erreicht werden, wenn über Gewinnsteigerungen ein Anreiz für den einzelnen Agenten besteht, an
Koalitionen zu partizipieren. Dies wird in den folgenden Abschnitten 3.2 und 4 ausführlich diskutiert.
Um die Anforderung zu erfüllen, daß
(ii) Informationsbeschaffung/Taktieren für Koalitionen nicht rational
ist, muß - analog zum Fall einzelner Bieter - erreicht werden, daß auch Koalitionen keinen Vorteil
aus der Beschaffung von Informationen über die Wertschätzung aller denkbaren Koalitionen erzielen
können. Dementsprechend muß der Mechanismus zum einen sicherstellen, daß es auch für Koalitionen rational ist, ihre gemeinsame Wertschätzung unabhängig von Wertschätzungen anderer Agenten/Koalitionen anzugeben. Zum anderen muß er gewährleisten, daß die Entscheidung über die Teilnahme an einer Koalition unabhängig vom Informationsstand der Agenten getroffen werden kann.
Die dritte Anforderung
(iii) Informationsoffenbarung für Koalitionen nicht erforderlich
zielt darauf ab, daß - wie zuvor bei einzelnen Agenten - für Koalitionen eine lokale Akzeptanz nur
dann erreicht werden kann, wenn sie den mitbietenden Agenten/Koalitionen keine Informationen
bekanntgeben müssen.
Schließlich ist analog zu Abschnitt 2 für einen
(iv) geringen Kommunikationsbedarf
8
zu sorgen.
3.2
Kooperationen in der VICKREY AUCTION
In diesem Abschnitt wird die Frage untersucht, inwieweit die einfache VICKREY AUCTION die oben
aufgeführten Anforderungen an Koordinationsmechanismen für Kooperationen erfüllt.
Dafür werden zunächst anhand eines Zahlenbeispiels (vgl. Bild 1) Probleme aufgezeigt, die sich aus
der Sicht des rational handelnden Auktionsteilnehmers Agent B ergeben, der ex-ante eine für ihn
optimale Kooperationsstrategie ermitteln will:
7.000
B
D
5.000
C
3.000
?
4.000
A
8.000
E
?
500
G
F
Auftrag
2.500
Beschreibung
Erlös
Restriktionen
...
2.000
Bild 1: Ex-ante-Betrachtung aus Sicht des Agenten B
Die Abbildung zeigt die Agenten A bis G mit ihren individuellen dDB (weiße Schrift). Bieter B hat
durch Koalitionsverhandlungen ermittelt, daß er in A den Koalitionspartner findet, mit dem er den
höchsten gemeinsamen dDB von 8.000 (schwarze Schrift) erzielen kann. Darüber hinaus ist B nur
sein eigener dDB bekannt. Bezüglich der übrigen Größen kann er beispielsweise folgende Überlegungen anstellen: Er nimmt an, daß es neben der Koalition (AB) nur für die Bieter C und D bzw. E
und F möglich ist, Synergien durch Kooperationen zu nutzen. Dies ist in der Abbildung durch die
9
gestrichelten Linien angedeutet. Weiterhin geht B davon aus, daß der dDB der Koalition (EF) relativ
niedrig liegt, die Koalition (CD) aber in der Lage ist, ein eventuell erfolgreiches Gebot abzugeben.
Bieter B hat dann die beiden folgenden Fälle zu betrachten:
(1) Geht B davon aus, daß sein eigener dDB niedriger als das höchste abgegebene Gebot ist, wird er
versuchen, in einer Koalition den Zuschlag zu erhalten.
Rechnet er also beispielsweise damit, daß das höchste Gebot mit 7.500 von der Koalition (CD)
abgegeben wird, liegt sein dDB als Einzelbieter mit 7.000 darunter. (CD) erhält somit den Zuschlag zum Preis von 7.000. Der Gewinn errechnet sich aus der Differenz zwischen der eigenen
Wertschätzung und dem Preis. Damit ergibt sich für (CD) ein Gewinn von 500. Da B in diesem
Fall nicht den Zuschlag erhält beträgt sein Gewinn null. Er wird demnach die Koalition mit A eingehen, die dann mit einem dDB von 8.000 das höchste Gebot abgibt. Bei einem Zuschlag zum
zweithöchsten Gebot von 7.500 erhält B einen Anteil aus dem Koalitionsgewinn von x⋅500, wobei x∈(0,1) das Ergebnis bilateraler Verhandlungen mit A ist. A erhält einen Anteil von (1x)⋅500. Somit ist für Bieter B in diesem Fall ein Koalitionsanreiz gegeben.
Da sich B für die Teilnahme an einer Koalition entscheidet, ist es für in aus ökonomischer Sicht
nicht rational, zusätzlich als Einzelbieter an der Auktion teilzunehmen: Er wird alleine nicht den
Zuschlag erhalten, da sein Gebot unter dem der Koalition liegt. Es besteht vielmehr die Gefahr,
daß er durch Abgabe seines Gebots den Preis für die Koalition erhöht.
(2) Geht B jedoch davon aus, daß er als Einzelbieter den Zuschlag erhält, muß er abwägen, ob der
Gewinn, den er alleine erzielen kann, größer ist als sein Anteil aus dem Koalitionsgewinn.
Gibt Koalition (CD) mit 5.500 das zweithöchste Gebot ab, so stellt sich für B die Frage, ob er
sich als Einzelbieter mit einem Gewinn von 1.500 oder in der Koalition mit A und seinem Anteil
x⋅2.500 aus dem Koalitionsgewinn besserstellt. Es ist für ihn also nicht zwingend ein Anreiz zur
Koalitionsbildung gegeben.
Aufgrund der Unsicherheit wird es mithin von der Risikobereitschaft des Agenten bzw. der durch
ihn repräsentierten Organisationseinheit abhängen, ob eine Koalition eingegangen wird oder nicht.
Insbesondere besteht hier offensichtlich ein Anreiz, Informationen über die Wertschätzung der
übrigen Beteiligten einzuholen, da unabhängig davon, ob B ex-ante den Teilungsfaktor x kennt oder nicht, ihm der aufzuteilende Gewinn der Koalition ex-ante niemals bekannt ist.
10
Das Beispiel macht deutlich, daß in der einfachen VICKREY AUCTION - erweitert um die Möglichkeit
der Koalitionsbildung - Informationen über das Verhalten der anderen Bieter eingeholt werden und
somit das Kriterium (ii) Informationsbeschaffung/Taktieren für Koalitionen nicht rational verletzt wird. Zudem kann die Informationsbeschaffung in einigen Fällen zu einer Entscheidung gegen
eine Koalitionsbildung führen und eine (i) effiziente Allokation für Koalitionen verhindern.
Da Koalitionen ihre dDB weiterhin ausschließlich dem Auktionator und nicht den mitbietenden Agenten/Koalitionen bekanntgeben, ist das Kriterium (iii) Informationsoffenbarung nicht erforderlich weiterhin erfüllt. Schließlich besteht ein (iv) geringer Kommunikationsbedarf, da jede Koalition nur ein verdecktes Gebot an den Auktionator gibt. Folglich kann die Nutzung der Synergiepotentiale zur Erreichung des globalen Ziels nur dann sichergestellt werden, wenn eine Alternative zur einfachen VICKREY AUCTION gefunden wird, die alle Kriterien, insbesondere (i) und (ii), auch für Kooperationen erfüllt.
4 Die MEHRSTUFIGE ERWEITERTE VICKREY AUCTION - MEVA
Basierend auf den zuvor diskutierten Überlegungen wurde im Rahmen des oben erwähnten Forschungsprojekts ein auf dem Grundkonzept der einfachen VICKREY AUCTION aufbauender Mechanismus, die M EHRSTUFIGE ERWEITERTE VICKREY AUCTION (MEVA), entwickelt, in dem ein für den
einzelnen Bieter zwingender Anreiz zur Koalitionsbildung gegeben ist. Das Prinzip dieses Mechanismus wird zunächst für Zweierkoalitionen beschrieben und auf das in Abschnitt 3.2 eingeführte Beispiel angewendet. Anschließend wird die Funktionsweise für beliebig große Koalitionen dargestellt
und der Mechanismus im Hinblick auf die Kriterien (i)-(iv) untersucht.
4.1
Der Mechanismus der MEVA
In Abschnitt 3.2 wurde herausgearbeitet, daß es für einzelne Agenten in der einfachen VICKREY
AUCTION
nicht in jedem Fall rational ist, Koalitionen einzugehen, obwohl die Koalitionsbildung für
eine effiziente Allokation aus globaler Sicht notwendig ist. Daher muß der Mechanismus sicherstellen,
daß der erwartete Gewinn des einzelnen in einer Koalition mindestens so groß ist wie der erwartete
Gewinn bei alleiniger Gebotsabgabe,3 der Referenzgewinn r. Dieser bezeichnet den Gewinn, den ein
einzelner Agent erzielt, wenn er alleine an der Auktion teilnimmt, und hilft, den Koalitionsanreiz in der
MEVA sicherzustellen:
11
In einer ersten Runde gibt jeder Auktionsteilnehmer, nach Bekanntgabe des Auftrags durch den
Auktionator, sein eigenes Gebot verdeckt ab. Der Auktionator merkt sich das höchste Gebot dieser
ersten Runde g1*, den höchstbietenden Agenten K1* sowie das zweithöchste Gebot g1**, gibt
diese Größen jedoch nicht bekannt. Die erste Runde entspricht also der einfachen VICKREY
AUCTION
(siehe Abschnitt 2.2), mit dem Unterschied, daß den Agenten keinerlei Informationen mit-
geteilt werden. Bild 2 skizziert den Ablauf der ersten Runde für das Beispiel aus Abschnitt 3.1:
7.000
B
5.000
C
D
K*1 = B
g* = 7.000
1
g** = 5.000
1
3.000
E
.
4.000
A
500
G
F
Auftrag
2.500
Beschreibung
Erlös
Restriktionen
...
2.000
Bild 2: Mechanismus der MEVA - 1. Runde
Anschließend werden in einer zweiten Runde ausschließlich Zweierkoalitionen zur Gebotsabgabe
aufgefordert. Wenn sich ein Agent in dieser zweiten Runde an einer Koalition beteiligt, ist es für ihn
nicht sinnvoll, das eigene Gebot der ersten Runde aufrecht zu erhalten (siehe Argumentation in Abschnitt 3.2). Dieses ökonomisch rationale Verhalten wird in der MEVA dadurch abgebildet, daß die
Einzelgebote derjenigen Agenten, die an Koalitionen teilnehmen, aus der Betrachtung für die Ermittlung des Zuschlags und des Preises herausgenommen werden. Diese Gebote werden lediglich zur
Bestimmung eines eventuellen Referenzgewinns herangezogen. So wird garantiert, daß der Gewinn
der Koalition mindestens so groß ist wie der Referenzgewinn.
12
Nach Eingang der Gebote in dieser Runde ergeben sich zwei grundsätzliche Alternativen. Für beide
Alternativen stellt der Mechanismus sicher, daß der Bieter mit dem höchsten Gebot beider Runden
den Zuschlag erhält und der Preis dem zweithöchsten Gebot aus der Menge aller Gebote in den beiden Runden entspricht, wobei die Einzelgebote von Koalitionsteilnehmern aus den oben genannten
Gründen vernachlässigt werden:
(a)
Das höchste Gebot der zweiten Runde g2* ist kleiner als das der ersten g1*, (g2*<g1*). Der
Bieter K1* mit g1* erhält den Zuschlag zum Preis p des zweithöchsten Gebots beider Runden, p = max (g1**, g2*).
(b)
Ist jedoch g2* ≥ g1*, so sind weitere Fallunterscheidungen zu treffen:
(b1) Der Bieter K1* mit g1* ist nicht Mitglied der Zweierkoalition K2* mit g2*. K2* erhält den Zuschlag zu p = max (g1*, g2**).
(b2) Der Bieter K1* mit g1* ist Mitglied der Koalition K2* mit g2*, wobei g1* kleiner als
das zweithöchste Gebot der zweiten Runde g2** ist (g1* < g2**). K2* erhält den Zuschlag zu p = g2**. Da in diesem Fall Bieter K1* alleine nicht den Zuschlag erhalten
hätte, besteht hier kein Anspruch auf einen Referenzgewinn.
(b3) Der Bieter K1* mit g1* ist Mitglied der Koalition K2* mit g2*, wobei g1* ≥ g2** ist.
Hier erhält die Koalition K2* den Zuschlag zu p = max (g1**, g2**). Da in diesem
Fall K1* den Zuschlag auch ohne die Teilnahme an der Koalition erhalten hätte, teilt
der Auktionator beiden Koalitionspartnern neben dem Zuschlag und dem Preis zusätzlich auch den Referenzgewinn r und den Bieter K1* mit dem Anspruch auf r mit.
Wendet man den Mechanismus der MEVA auf das Beispiel in Abschnitt 3.2 an, so wird deutlich,
daß ein rational handelnder Bieter in jedem Fall bestrebt ist, Koalitionen einzugehen, um so seinen
individuellen Gewinn zu maximieren.
Aus Sicht des Agenten B stellt sich die Situation nun ex-ante folgendermaßen dar:
13
Ist das Gebot der Koalition (CD) in Höhe von 5.500 kleiner als sein eigenes Gebot mit 7.000, so
erhält nach (b3) die Koalition (AB) den Zuschlag zum Preis von 5.500. Von dem Koalitionsgewinn
in Höhe von 2.500 erhält B den Referenzgewinn r = 1.500. Von dem verbleibenden Gewinn erhält B
einen auszuhandelnden Anteil x⋅1.000, wie Bild 3 zeigt. Verzichtet B jedoch auf die Teilnahme an der
Koalition (AB), erhält er nach (a) den Zuschlag zu 5.500 und damit einen Gewinn von 1.500. B wird
als rational handelnder Agent an der Koalition teilnehmen.
7.000
B
5.000
D
C
3.000
+x. 1.000
+ 1.500
+(1-x). 1.000
4.000
A
g**
5.500
3.000
E
Zuschlag; Preis: 5.500
r = 1.500; K* = B
8.000
500
g*
G
F
Auftrag
2.500
Beschreibung
Erlös
Restriktionen
...
2.000
Bild 3: Mechanismus der MEVA - 2. Runde
Bietet (CD) jedoch 7.500, erhält (AB) gemäß (b2) den Zuschlag zu 7.500 und B einen Anteil x⋅500.
Verzichtet B in diesem Fall auf die Teilnahme an der Koalition (AB), so büßt er diesen Anteil ein und
erzielt einen Gewinn von 0, da nach (b1) die Koalition (CD) den Zuschlag erhält. Auch hier wird B
an der Koalition teilnehmen.
Das dargestellte Prinzip zur Ermittlung des Agenten/der Koalition, der/die den Zuschlag erhält, sowie
des Preises und eines eventuellen Referenzgewinns läßt sich auf weitere Runden übertragen. In jeder
Folgerunde wird die Koalitionsgröße um eins erhöht. Es gibt Folgerunden, bis die Koalitionsgröße
der Anzahl teilnehmender Agenten entspricht. Dies gewährleistet die vollständige Einbeziehung aller
Elemente der Potenzmenge der Agenten.
14
Abschließend wird der Mechanismus der MEVA allgemein dargestellt:
I.
Die Auktion besteht aus mehreren Runden, wobei in der i-ten Runde ausschließlich Koalitionen der Größe i Gebote abgeben.
II.
Der Auktionator speichert in jeder Runde das höchste und das zweithöchste Gebot aller
bisherigen Runden und den Agent/die Koalition mit dem höchsten Gebot. Eine Rückmeldung
erfolgt nicht in den einzelnen Runden, sondern nur am Ende der letzten Runde.
III.
In jeder Runde ermittelt der Auktionator einen Referenzgewinn, wenn eine Teilmenge der
Koalition mit dem höchsten Gebot in dieser Runde auch in der jeweils vorhergehenden Runde alleine bzw. als Koalition das höchste Gebot abgegeben hat und dieses Gebot höher ist
als das zweithöchste Gebot der aktuellen Runde.
IV.
Den Zuschlag erhält der Agent/die Koalition mit dem höchsten Gebot aller Runden zum Preis
des zweithöchsten Gebots aller Runden. Dabei bleiben alle Gebote aus vorhergehenden
Runden unberücksichtigt, die von Koalitionsteilnehmern der letzten Runde, in der Gebote
erfolgen, abgegeben wurden.
V.
Zur Sicherung eines zwingenden Koalitionsanreizes werden den Agenten/Koalitionen, die
den Zuschlag erhalten, eventuell entstandene Referenzgewinne (vgl. III) mitgeteilt.
4.2
Bewertung der MEVA
Der Mechanismus der MEVA wird in diesem Abschnitt anhand der in 3.1 aufgeführten Kriterien (i)
bis (iv) bewertet.
(i) effiziente Allokation
Die MEVA stellt aus individueller Sicht der Agenten sicher, daß deren Gewinn sich für den Fall
des Zuschlags durch die Bildung von Koalitionen stets erhöht. Somit besteht der Suchraum sowohl aus allen einzelnen Agenten als auch aus allen Koalitionen. Dabei werden sich nur solche
Koalitionen bilden, deren gemeinsamer dDB größer ist, als der größte individuelle dDB der jeweils beteiligten Agenten. Dadurch werden alle relevanten Elemente der Potenzmenge der Agenten untersucht und dem Agenten bzw. der Koalition mit der höchsten Wertschätzung der
Zuschlag erteilt. Dies impliziert eine effiziente Allokation.
(ii) Informationsbeschaffung/Taktieren nicht rational
15
In der MEVA werden Koalitionsanreize derart gesetzt, daß Koalitionen in jedem Fall - unabhängig von Informationen über andere Bieter - eingegangen werden. Sowohl für einzelne Agenten als auch für Koalitionen ist es rational, die eigene Wertschätzung als Gebot abzugeben. Die
Argumentation entspricht exakt der für die einfache VICKREY AUCTION.
Diese Überlegungen zeigen, daß im Gegensatz zu der in Abschnitt 3.2 dargestellten einfachen
VICKREY AUCTION für Koalitionen, die Kriterien (i) und (ii) durch die MEVA erfüllt werden.
(iii) Informationsoffenbarung nicht erforderlich
Auch bei der MEVA handelt es sich um eine Auktionsform mit verdeckten Geboten. Eine Informationsoffenbarung findet deshalb für Koalitionen wie auch in der einfachen VICKREY
AUCTION
lediglich gegenüber dem Auktionator statt. Unabhängig davon wird es bei jedem Ko-
ordinationsmechanismus, der eine Koalitionsbildung ermöglicht, zu einem intensiven Informationsaustausch bei den Koalitionsverhandlungen kommen. Relevant für die Beurteilung des Mechanismus ist allerdings nur die Betrachtung der Informationsoffenbarung zwischen den Koalitionen, diese ist in der MEVA nicht erforderlich.
(iv) geringer Kommunikationsbedarf
Analog zu obiger Argumentation kann auch hier vom Kommunikationsbedarf in den Koalitionsverhandlungen abstrahiert werden. Da es sich bei der MEVA um eine Auktion mit verdeckten
Geboten handelt, ist auch hier der Kommunikationsbedarf im Verhältnis zu offenen Auktionsformen gering. Durch die Einführung der Mehrstufigkeit läßt sich ein Ansteigen des Kommunikationsbedarfs nicht verhindern. Ein erster Ansatz zu dessen Senkung besteht in der Vorgabe
von Mindestgeboten durch den Auktionator.
Damit ist ein Mechanismus gefunden, der bei Erfüllung der Kriterien (i) bis (iv) auch für den Fall von
Kooperationen in dezentralen Organisationsstrukturen zur Lösung globaler Planunsgsprobleme sicherstellt, daß
∗ innerhalb dieser Koordination eine aus globaler Sicht optimale Lösung generiert wird,
∗ das Planungsproblem aus konzeptioneller Sicht einem MAS übertragen werden kann,
∗ die einzelnen Organisationseinheiten den ‘Spielregeln’ des Mechanismus vertrauen sowie
∗ die Kommunikationskosten gering sind.
16
5 Fazit
Ausgangspunkt dieser Arbeit sind betriebliche Planungsprobleme, die in dezentralen Organisationsstrukturen zu lösen sind. Dabei stehen - unabhängig von einer konkreten Fachdomäne - Klassen von
Planungsproblemen im Mittelpunkt. Ziel des oben erwähnten DFG-Forschungsprojekts und damit
auch dieser Arbeit ist es, marktliche Mechanismen für die Koordination verteilter Aktivitäten zu identifizieren, auf deren Basis betriebliche Planungsprozesse in einem MAS sinnvoll abgebildet und dort
effizient gelöst werden können.
Vergleicht man einfache Auktionsformen im Hinblick auf die in dieser Arbeit definierten Kriterien,
geht die VICKREY AUCTION als einziger Koordinationsmechanismus hervor, der allen Anforderungen
gerecht wird - solange keine Kooperation zwischen den beteiligten Organisationseinheiten stattfindet.
Für den Kooperationsfall müssen diese Kriterien ebenso erfüllt werden. Dies bedeutet vor allem, daß
über den gesuchten Mechanismus ex-ante eine anreizkompatible Teilungsregel des Kooperationsgewinns festgelegt werden muß, mit der eine Steuerungsfunktion einhergeht: ein zwingender ökonomischer Anreiz zur Bildung von Koalitionen - unabhängig vom Informationsstand aller Beteiligten.
Mit der MEHRSTUFIGEN ERWEITERTEN VICKREY AUCTION (MEVA) konnte auf analytischem Wege
ein Koordinationsmechanismus entwickelt werden, der unter Ausnutzung von Synergieeffekten durch
Kooperationen eine effiziente Lösung der betrachteten Planungsaufgaben in MAS liefert und dabei
dem Anforderungskatalog genügt.
Die im Rahmen dieser Arbeit durchgeführte Analyse beleuchtet dabei den reinen Koordinationsaspekt. Mit der Frage nach der Ausgestaltung von Verhandlungen zwischen potentiellen Kooperationspartnern ist ein gesonderter Problembereich angesprochen. Die Konkretisierung der Koalitionsverhandlungen hinsichtlich der Gewinnverteilung einerseits und der Ermittlung einer gemeinsamen
Wertschätzung andererseits ist deshalb ein wichtiges Thema für weitere Forschungsbemühungen im
Rahmen des DFG-Forschungsprojekts „Dezentrale betriebliche Planung“.
17
Literatur
[AfMi87] McAffee, R.-P.; McMillan, J.: Auctions and Bidding. In: Journal of Economic Literature
25 (1987) S. 699-738.
[BoGa88] Bond, Alan H.; Gasser, Les: An Analysis of Problems and Research in DAI. In: Bond,
Alan H.; Gasser, Les (Hrsg.): Readings in Distributed Artificial Intelligence, San Mateo 1988,
S. 3-35.
[FaSp93] Falk, Jürgen; Spieck, Stefan et al.: Unterstützung der Lager- und Transportlogistik
durch Teilintelligente Agenten. In: IM Information Management (1993) 2, S. 26-31.
[FiHe96] Fischer, Klaus; Heimig, Ingo et al.: Intelligente Agenten für das Management Virtueller
Unternehmen. In: IM Information Management (1996) 1, S. 38-45.
[FiKu93] Fischer, Klaus; Kuhn, N. et al.: Verteiltes Problemlösen im Transportwesen. In: IM
Information Management (1993) 2, S. 32-40.
[Kirn94] Kirn, Stefan: FRESCO: Kooperative wissensbasierte Systeme an der „Kundenschnittstelle“ von Finanzdienstleistern. In: Kirn, Stefan; Weinhardt, Christof (Hrsg.): Künstliche Intelligenz in der Finanzberatung. Wiesbaden 1994, S. 191-210.
[Kirn96] Kirn, Stefan: Kooperativ-Intelligente Softwareagenten. In: IM Information Management
(1996) 1, S. 18-28.
[Kräk92] Kräkel, Michael: Auktionstheorie und interne Organisation. Wiesbaden 1992.
[MaWe95] Mack, Bernd; Weinhardt, Christof: Verteiltes Problemlösen in der Finanzberatung ein portfoliotheoretischer Ansatz. In: KI Künstliche Intelligenz (1995) 3, S. 46-55.
[MeFa95] Mertens, Peter; Faisst, Wolfgang: Virtuelle Unternehmen - eine Organisationsstruktur
für die Zukunft? In: technologie & management 44 (1995) 2, S. 61-68.
[MöWe96] Möhle, Sybille; Weigelt, Mark et al.: Dezentrale Produktionsplanungs- und
-steuerungs-Experten: Kombination Wissensbasierter Ansätze mit ComponentWare. In: IM Information Management (1996) 1, S. 30-37.
[PiMa93] Picot, Arnold; Maier, Matthias: Interdependenzen zwischen betriebswirtschaftlichen
Organisationsmodellen und Informationsmodellen. In: IM Information Management (1993) 3, S.
6-15.
[Rieb85] Riebel, Paul: Überlegungen und Fallstudien zur Bedeutung der Entscheidungssequenz für
die Unternehmensrechnung. In: Stöppler, Siegmar (Hrsg.): Information und Produktion - Beiträge zur Unternehmenstheorie und Unternehmensplanung. Stuttgart 1985, S. 243-276.
[ScWe95] Schultz, Jens; Weigelt, Mark et al.: Verfahren für die rechnergestützte Produktionsfeinplanung - ein Überblick. In: Wirtschaftsinformatik 37 (1995) 6, S. 594-609.
[Vick61] Vickrey, William: Counterspeculation, Auctions, and Competitive Sealed Tender. In:
Journal of Finance 16 (1961), S. 8-37.
[WeGo96] Weinhardt, Christof; Gomber, Peter: Domänenunabhängige Koordinationsmechanismen für die dezentrale betriebliche Planung. In: IM Information Management (1996) 1, S. 6-16.
[ZeBo93] Zelewski, Stephan; Bode, Jürgen: Koordination von Produktionsprozessen - Ein Ansatz
auf der Basis von Multi-Agenten-Systemen. In: IM Information Management (1993) 2, S. 14-24.
18
1
Nach dem Konzept des dispositionsspezifischen Deckungsbeitrags (dDB) plant jedes Subjekt in seine eigene, zuvor auf der Grundlage seines lokalen Wissens bereits optimierte Situation den neuen (Teil-) Auftrag ein
und optimiert unter Berücksichtigung dieses Auftrags neu. Anschließend wird die Kostendifferenz zwischen
der Planungssituation ohne und derjenigen mit dem neuen Auftrag ermittelt. Die Differenz (Erlös des Auftrages - Kostendifferenz) ergibt den dDB des Auftrags.
2
Dies ist der Kurztitel des in Fußnote ‘+’ erwähnten Projekts.
3
Aus ökonomischer Sicht wird sichergestellt, daß das Pareto-Kriterium erfüllt ist.
19

Download Report