Today Me, Tomorrow Thee: Efficient Resource Allocation in Competitive Settings using Karma Games

We present a new type of coordination mechanism among multiple agents for the\nallocation of a finite resource, such as the allocation of time slots for\npassing an intersection. We consider the setting where we associate one counter\nto each agent, which we call karma value, and where there is an established\nmechanism to decide resource allocation based on agents exchanging karma. The\nidea is that agents might be inclined to pass on using resources today, in\nexchange for karma, which will make it easier for them to claim the resource\nuse in the future. To understand whether such a system might work robustly, we\nonly design the protocol and not the agents' policies. We take a game-theoretic\nperspective and compute policies corresponding to Nash equilibria for the game.\nWe find, surprisingly, that the Nash equilibria for a society of\nself-interested agents are very close in social welfare to a centralized\ncooperative solution. These results suggest that many resource allocation\nproblems can have a simple, elegant, and robust solution, assuming the\navailability of a karma accounting mechanism.\n