Courtesy as a Means to Coordinate

2018/01/22 by Danassis, Panayiotis, Faltings, Boi
#FOS: Computer and information sciences #Multiagent Systems (cs.MA)

paper · doi:10.48550/arxiv.1801.07140

Abstract

We investigate the problem of multi-agent coordination under rationality constraints. Specifically, role allocation, task assignment, resource allocation, etc. Inspired by human behavior, we propose a framework (CA³NONY) that enables fast convergence to efficient and fair allocations based on a simple convention of courtesy. We prove that following such convention induces a strategy which constitutes an ε-subgame-perfect equilibrium of the repeated allocation game with discounting. Simulation results highlight the effectiveness of CA³NONY as compared to state-of-the-art bandit algorithms, since it achieves more than two orders of magnitude faster convergence, higher efficiency, fairness, and average payoff.

Related

• Today Me, Tomorrow Thee: Efficient Resource Allocation in Competitive\n Settings using Karma Games
• Approximate Equilibrium and Incentivizing Social Coordination
• When Smoothness is Not Enough: Toward Exact Quantification and Optimization of the Price-of-Anarchy
• Payoff Mechanism Design for Coordination in Multi-Agent Task Allocation Games
• A Mechanism for Mutual Fairness in Cooperative Games with Replicable Resources -- Extended Version