Improved Price of Anarchy via Predictions

23^rd November 2022, 13:00
Alkmini Sgouritsa

Abstract

In this work we revisit two classic decentralised resource allocation problems, scheduling games and network formation games, aiming to achieve improved price of anarchy bounds by leveraging predictions.

These two classes of games correspond to special cases of a very general model defined using a network with load dependent cost functions. Given a graph and a set of agents, each agent needs to use a path in order to connect some source vertex to a terminal vertex. For each edge, a cost is generated that depends on the total load of agents that choose to use it, which is passed on to the users. The agents strategically choose their paths, aiming to minimise their cost, and the performance of the induced game is evaluated using its price of anarchy. We study and design cost-sharing mechanisms with low price of anarchy.

One crucial question is the information that is available to the mechanism designer, ranging from the most pessimistic scenario that the designer has no information, to the most optimistic scenario that the designer has full information of the graph, the cost functions and the agents’ source and terminal. Our work lies in the middle of those two scenarios by assuming that the designer has full knowledge of the graph and cost functions, but they have incomplete information about agents’ demand. However, even for this situation the results are often very pessimistic. To overcome those obstacles, we design mechanisms that are enhanced with predictions regarding the missing information.

The talk is based on a joint work with Vasilis Gkatzelis, Kostas Kollias and Xizhi Tan