Network Restoration Games With Quotas (Student abstract)

In a game of NETWORK RESTORATION GAMES WITH QUOTAS, there is an underlying graph where a subset of its edges have to be restored by a set of agents. Each agent has a creation cost for each such edge, a traversal cost for every edge of the graph, and in addition they have a quota on the number of edges they have to restore. Then, given a set of edges that fulfill the quota, the cost of an agent is the cost of creating these edges, plus the cost of reaching them, i.e., the traversal cost. We prove that any cost-minimizing allocation is swap-stable, i.e., there is no profitable exchange of edges between any pair of agents, but computing one is hard even on trees. We complement this by designing an algorithm that finds a swap-stable allocation on trees in polynomial time and we quantify its cost against the optimal one.