What Do Agents Think One Another Want? Level-2 Inverse Games for Inferring Agents' Estimates of Others' Objectives

Die Arbeit stellt ein neues Framework für die Level-2-Inferenz vor, das in dezentralen Szenarien wie dem autonomen Fahren die Schätzungen von Agenten über die Ziele anderer erfasst, um die Beschränkungen bestehender Level-1-Methoden zu überwinden, die fälschlicherweise von vollständigem Wissen über die Ziele aller Akteure ausgehen.

Hamzah I. Khan, Jingqi Li, David Fridovich-KeilThu, 12 Ma💻 cs

Sequential Causal Normal Form Games: Theory, Computation, and Strategic Signaling

Die Arbeit zeigt, dass die Erweiterung von kausalen Normalformspielen auf sequenzielle Szenarien trotz theoretischer Eleganz und PSPACE-Vollständigkeit in der Praxis keine Wohlfahrtsverbesserung gegenüber klassischen Stackelberg-Gleichgewichten bietet, da rationale Rückwärtsinduktion kausale Vorteile eliminiert und somit neue theoretische Rahmenwerke jenseits des Nash-Gleichgewichts für KI-Agenten erforderlich macht.

Dennis ThummThu, 12 Ma📊 stat

Instant Runoff Voting on Graphs: Exclusion Zones and Distortion

Die Arbeit untersucht die Komplexität von Ausschlusszonen und der Verzerrung beim Instant-Runoff-Voting auf Graphen und zeigt, dass beide Probleme auf Bäumen in Polynomialzeit lösbar sind, während sie für allgemeine Graphen bzw. für eine Klasse von Abstimmungsregeln mit der Eigenschaft „Strong Forced Elimination" NP-schwer bzw. co-NP-vollständig bleiben.

Georgios Birmpas, Georgios Chionas, Efthyvoulos Drousiotis, Soodeh Habibi, Marios Mavronicolas, Paul SpirakisThu, 12 Ma💻 cs

On the Existence of Fair Allocations for Goods and Chores under Dissimilar Preferences

Diese Arbeit löst eine offene Frage von Gorantla et al., indem sie explizite obere Schranken für die Anzahl der benötigten Kopien von Gütern und Aufgaben herleitet, um eine faire Zuteilung unter beliebigen Gruppen und Präferenzen zu garantieren, und dabei eine vereinfachte, konstruktive Methode einführt, die sich auch auf andere faire Teilungsprobleme erweitern lässt.

Egor Gagushin, Marios Mertzanidis, Alexandros PsomasMon, 09 Ma💻 cs

Test-then-Punish: A Statistical Approach to Repeated Games

Die Arbeit entwickelt einen statistischen „Test-then-Punish"-Ansatz für wiederholte Spiele mit unvollkommener Überwachung, der durch die Einbettung von Hypothesentests in strategisches Verhalten und die Verwendung relaxierter Gleichgewichtsbegriffe zeigt, dass auch unter Unsicherheit über Abweichungen ein Folk-Theorem-Ergebnis erzielt werden kann.

Aymeric Capitaine, Antoine Scheid, Etienne Boursier, Alain Durmus, Michael I. JordanMon, 09 Ma💻 cs

The Coordination Gap: Alternation Metrics for Temporal Dynamics in Multi-Agent Battle of the Exes

Diese Studie zeigt, dass herkömmliche, zeitunabhängige Leistungsmetriken in Multi-Agenten-Szenarien koordinierte Verhaltensmuster wie Turn-taking oft übersehen, und führt daher neue, zeitlich sensitive Alternationsmetriken ein, die offenbaren, dass selbst lernbasierte Strategien trotz hoher aggregierter Belohnungen signifikant schlechter koordinieren als zufällige Baselines.

Nikolaos Al. Papadopoulos, Konstantinos PsannisMon, 09 Ma🤖 cs.LG