Bi-Weekly Talk: Improving Local Search for Distributed Resource Allocation and Equilibrium Computation

Wednesday, 04.04.2018, 10:15am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10


Speaker: Vipin Ravindran Vijayalakshmi

Improving local search for distributed resource allocation and equilibrium computation Abstract: Congestion games constitute an important class of games to model resource allocation by different users such as in traffic networks. We study the approximation ratio of local optima in these games. However, we allow for that the cost functions used during the local search procedure may be different from the overall objective function. Our analysis exhibits an interesting method to choose these cost functions to obtain the following results:

1. As computing an exact or even approximate pure Nash equilibrium is in general PLS-complete, Caragiannis et al. presented a polynomial-time algorithm that computes (2 + \epsilon)-approximate pure Nash equilibria for games with linear cost functions and further results for polynomial cost functions. We show that this factor can be improved to 1.67+\epsilon by a seemingly simple modification of their algorithm using our technique.

2. Bilo and Vinci presented an algorithm to compute load dependent taxes that improve the price of anarchy for example for linear game from 2.5 to 2. Our methods yield slightly weaker results, for example 2.1 for linear games. However, our tax functions are locally computable and independent of the actually instance of the game.