Algorithmische Spieltheorie

Untersuchung strategischen Verhaltens im Kontext von Ressourcenallokation und Nutzerbewertungen

Die Algorithmische Spieltheorie untersucht Szenarien, in denen rationale Akteure miteinander interagieren. Sie beschäftigt sich mit Aussagen über Ergebnisse strategischen Handelns und entwickelt Algorithmen, die auf diesen Ergebnissen basieren. Network Function Virtualization ist hier ein Beispiel für ein Szenario, welches auch im Kontext des Sonderforschungsbereichs 901 „On-The-Fly Computing“ auftritt.

Die Algorithmische Spieltheorie untersucht die Auswirkungen
strategischen Handelns seitens autonomer Akteure. Eine Fragestellung
ist hierbei etwa die Berechnungskomplexität von
Ergebnisprognosen bei verteilter Allokation von Ressourcen,
wie beispielsweise Kapazitäten in Netzwerken oder Rechenleistung
von Servern. Weiterhin untersuchen wir, wie sich dynamische
Anpassungsprozesse verhalten, wenn Agenten wiederholt
auf die Aktionen anderer Agenten reagieren: Welche Dauer
haben solche Prozesse? Konvergieren sie zu stabilen Zuständen?
Wie ineffizient sind diese Systeme?

Allokation von Ressourcen

Wir haben uns in mehreren Arbeiten mit der Allokation von Ressourcen
unter strategischen Teilnehmern aus spieltheoretischer
Sicht beschäftigt. Wir haben hierzu das bekannte Modell der
Auslastungsspiele genutzt. Eine Menge von Spielern, die z. B.
unsere OTF-Dienstleister im Kontext des Sonderforschungsbereichs
901 darstellen, können eine Menge von Ressourcen (wie
z. B. Services von Dienstanbietern) nutzen, die jedoch mit Kosten
abhängig von der Nutzerzahl verbunden sind. Jeder Spieler hat
verschiedene Ressourcenmengen zur Verfügung, je nachdem
was er anbieten muss. Wir haben uns mit zwei spezifischen
Ausprägungen dieses Modells beschäftigt. Auf der einen Seiten
haben wir heterogene Teilnehmer betrachtet, die verschiedene
Zielfunktionen verfolgen, und untersucht, welche Garantien über
Gleichgewichtszustände erhalten bleiben. Auf der anderen Seite
haben wir uns mit der Aufteilung der Kosten beschäftigt und hier
ein anderes Modell als die proportionale Aufteilung betrachtet.
Der Fokus lag dann auf der Berechnung von approximativen
Gleichgewichten in diesem Modell.

Disaggregation von Nutzerbewertungen

Des Weiteren haben wir uns dem Problem der konsistenten
Verarbeitung von Nutzerbewertungen über komponierte
Services gewidmet. Ziel war es, aus Daten über komponierte
Services Bewertungen der Einzelservices zuzurechnen. Da
es sich um Bewertungen vieler Einzelnutzer handelt, diskutieren
wir Kombinationen aus Aggregation (über Nutzer) und
Disaggregation (in Einzelbewertungen). Unter der Annahme,
dass das Ergebnis nicht von der Reihenfolge der Anwendung
dieser Operationen abhängen soll, stellt sich heraus, dass das
(gewichtete) arithmetische Mittel als Aggregator zusammen mit
dem Shapley-Wert als Disaggregator eine sinnvolle Kombination
darstellt. Hierbei bedeutet sinnvoll, dass es nicht auf o.g.
Reihenfolge ankommt und die Manipulationsmöglichkeiten
eines einzelnen Nutzers stark eingeschränkt sind. Offen ist
noch die Charakterisierung dieser Lösung durch eine erweiterte
Liste von Axiomen.

Gefördert durch:

  • DFG Sonderforschungsbereich 901 „On-TheFly Computing“, Teilprojekt A3