ENTSCHEIDUNGSFINDUNG IN AGENTENSYSTEMEN: ABTIMMUNGEN, AUKTIONEN, VERHANDLUNGEN Dongdong Jiao, Bastian Treger Überblick Einleitung Grundlagen / Kriterien Beispiel: Abstimmung Beispiel: Auktion Weitere Beispiele Zusammenfassung Einleitung Computergestützte Verhandlungen spielen eine immer wichtigere Rolle Technologie vorhanden, die die Kommunikation zwischen Agenten ermöglich (Internet) Multiagenten Systeme: o o Sparen Zeit Sind effektiver Soziale Gerechtigkeit Betrachtet die Summe aller Einnahmen/Nützlichkeiten aller Agenten Ist ein globales Kriterium Pareto Effizienz / Optimum Vilfredo Pareto (1848 - 1923): Ökonom und Soziologe Ein Situation, bei der es keine Möglichkeit gibt, zumindest eine Person / Agenten besser zu stellen ohne jemand anderes zu benachteiligen. Beispiel 1: Tausch A und B mögen Äpfel, Birnen gleich gerne Ausgangssituation: A(4,0) B(0,4) Schritt 1: A(3,1) B(1,3) Schritt 2: A(2,2) B(2,2) Pareto Optimum Pareto Effizienz / Optimum Beispiel 2: Pareto-Optimum und Gerechtigkeit 6 Äpfel auf die Personen A, B & C verteilen, alle Personen mögen Äpfel gerne Möglichkeit 1: A(2) B(2) C(2) Möglichkeit 2: A(4) B(1) C(1) Möglichkeit 3: A(6) B(0) C(0) Frage: Welche Möglichkeit ist pareto-optimal? Pareto Effizienz / Optimum Beispiel 2: Pareto-Optimum und Gerechtigkeit 6 Äpfel auf die Personen A, B & C verteilen, alle Personen mögen Äpfel gerne Möglichkeit 1: A(2) B(2) C(2) Möglichkeit 2: A(4) B(1) C(1) Möglichkeit 3: A(6) B(0) C(0) Frage: Welche Möglichkeit ist pareto-optimal? Lösung: Alle Möglichkeiten sind pareto-optimal Soziale Gerechtigkeit ist ein Sonderfall des Pareto-Optimums Individuelle Rationalität Teilnahme eines Agenten in einer Verhandlung ist individuell rational, wenn nicht weniger oder gleichviel wie bei einer Nichtteilnahme verdient Ein Vorgang ist individuell rational, wenn er für alle teilnehmenden Agenten individuelle Rational ist Stabilität - Nash-Gleichgewicht Besonders bei eigennützigen Agenten ist eine stabile (nicht manipulierbar) Verhandlung nötig Nash-Gleichgewicht: Spielstrategie bei der jeder Agent eine Strategie wählt, welche die beste Antwort auf die Strategie des anderen Agenten ist. Probleme: Es existiert nicht immer ein Nash-Gleichgewicht Teilweise existieren mehrere Nash-Gleichgewichte Nash-Gleichgewicht Beispiel: Strategisches Spiel Spieler 2 Spieler 1 links mitte rechts oben 4,2 1,1 2,0 mitte 2,3 1,1 1,4 unten 3,0 0,2 1,3 Ein Nash-Gleichgewicht existiert bei: (oben,links) (4,2) Nash-Gleichgewicht Beispiel: Gefangenen Dilemma Einer schweigt, einer gesteht: 5 bzw. 0 Jahre Beide gestehen: je 4 Jahre Beide schweigen: je 2 Jahre Gefangener 2 Gefangener 1 gestehen schweigen gestehen 4,4 0,5 schweigen 5,0 2,2 Nash-Gleichgewicht: beide gestehen und bekommen je 4 Jahre Rechen & Kommunikations-Effizienz Rechen-Effizienz: Erwünscht ist geringer Rechenaufwand Ideal: Kompromiss zwischen Qualität und Rechenzeit Kommunikations-Effizienz Ausfall- und Fehlertoleranz Geringe Menge an Kommunikation Teilweise widersprüchliche Ziele Abstimmungen, Wahl Alle Agenten geben eine Stimme ab und müssen das Ergebnis akzeptieren Menge der Agenten A, Agent i A Menge der Ergebnisse O, Ergebnis o O Präferenzrelation i (transitiv & unsymmetrisch) Ergebnis der Abstimmung * * * ظ 1 ظ1 ظ Wahlurne ظ2 *ظ 2 ظ3 3 Abstimmung: Bedingungen * muss für alle möglichen Eingaben existieren * muss für jedes Paar o,o‘ O definiert sein * sollte unsymmetrisch und transitiv über O sein * sollte pareto-optimal sein Unabhängig von unbedeutend Alternativen (o i o‘ und o i‘ o‘) Kein Agent i sollte ein Diktator sein (o i o‘ impliziert o * o‘) Abstimmungsverfahren Bei ehrlichen Wählern 1. Mehrheiten – Protokoll Verbreitetste Form der Wahl Alternativen werden gleichzeitig verglichen Alternative mit den meisten Stimmen gewinnt 2. Binär – Protokoll Die Alternativen werden paarweise verglichen Der Gewinner bleibt im Rennen (KO-System) Reihenfolge ist entscheidend für das Ergebnis Möglichkeiten der Alternativen wird schnell groß langsam Binär – Protokoll Abstimmungen Borda-Protokoll: Den Alternativen werden Punkte geben: 1. Platz = |O| 2. Platz = |O| - 1 … Punkte werden addiert, Alternative mit den meisten Punkten gewinnt Borda-Protokoll Agent 1 2 3 4 5 6 7 Summe Alternative a 4 1 2 4 1 2 4 18 Alternative b 3 4 1 3 4 1 3 19 Alternative c 2 3 4 2 3 4 2 20 Alternative d 1 2 3 1 2 3 1 13 Agent 1 2 3 4 5 6 7 Summe Alternative a 3 1 2 3 1 2 3 15 Alternative b 2 3 1 2 3 1 2 14 Alternative b 1 2 3 1 2 3 1 13 Beim Wegfall der Alternative d wird der Gewinner c zum Verlierer Auktionen Englische Auktion: Gebote sind öffentlich Jeder Bieter kann beliebig viele Gebote abgeben Bieter mit dem Höchstpreis gewinnt Strategie für Bieter: Immer etwas mehr als das aktuelle Gebot bieten Maximal den eigenen Höchstpreis Probleme: Preistreiberei durch den Auktionator Auktionen Ausschreibung: Gebote sind geheim Nur ein Gebot pro Bieter möglich Bieter mit dem Höchstpreis gewinnt Strategie für Bieter: Den kleinsten Betrag bieten der gerade noch gewinnt Gebote der Anderen sind jedoch unbekannt Auktionen Holländische Auktion: Auktionator beginnt mit hohen Preis Preis wird gesenkt bis das erste Gebot erfolgt Zuschlag an Höchstbieter Strategie der Bieter: Analog zu Ausschreibung, da Gebote der Anderen unbekannt Auktionen Vickrey-Auktion: Gebote sind geheim Nur ein Gebot pro Bieter möglich Höchstbieter erhält den Zuschlag zum 2. höchsten Gebot Werden oft bei Agenten eingesetzt Strategie für Bieter: Den eigenen maximalen Wert bieten Probleme: Auktionator gibt falsches 2. höchstes Gebot an Aktionen Alle 4 Auktionstypen sind anfällig für Absprachen unter den Bietern Alle 4 Auktionstypen sind pareto-optimal Verhandlungen Komplexer als Auktionen Verhandlungen sind Vereinbarungen über gemeinsame Ziele 4 Komponenten von Verhandlungen: Verhandlungsmasse Protokoll Strategie für jeden Agenten (nicht öffentlich) Regeln Wann ist eine Vereinbarung abgeschlossen Was ist der Inhalt der Vereinbarung Weitere Beispiele Marktsysteme (Angebot, Nachfrage, Produktivität) Agenten-Gruppen Verträge abschließen Zusammenfassung Oft sind Agenten eigennützig Ziel ist es diesen mit der entsprechenden Strategie entgegen zu wirken Es ist sowohl Wissen über die Informatik (Spielstrategie, Effizienz) als auch die Wirtschaft (Pareto) notwendig
© Copyright 2024 ExpyDoc
