Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the future will have to face is coordination in the use of limited resources, central to which is finding an optimal allocation between agents. To truly allow for scalable solutions, we needs to shift from traditional approaches, to multi-agent solutions, ideally run on-device. We present a novel heuristic (ALMA), which exhibits such properties, for solving the assignment problem. ALMA is decentralized, requires only partial feedback, and has constant in the total problem size running time, under reasonable assumptions on the preference domain of the agents, making it ideal for an on-device implementation. We have evaluated ALMA in a variety of scenarios including synthetic and real data, time constraints, and on-line settings. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm.