Date: 17 November 2017
Time: 12:45 - 13:30 (Lunch available from 12:35)
Room: RA 2334 (Ravelijn)
Title: Simple, distributed, and powerful - utilizing local search for resource allocation and equilibrium computation
Abstract:
We study variant of simple local search algorithms for general resource allocation problems with a diseconomy of scale or congestion games.
Here, we are given a finite set of commodities or players that request certain resources. The cost of each resource grows super-linearly with the demand for it and our goal is to minimize the total costs of the resources.
We show that for mildly growing cost functions a small modification of a simple, distributed local search algorithm guarantees a approximation factor that is close to the best known centralized algorithm [Makarychev, Srividenko FOCS14].
Moreover, our technique has interesting game theoretic implications: On the one hand, the algorithmic technique can be used for a significant improvement in the computation of approximate pure Nash equilibria. For example for linear cost functions it improves the factor from 2 [Caragiannis et al. FOCS11] to 1.6. On the other hand, it exhibits a method to influence the strategic behavior of selfish agents to increase efficiency by pricing or taxing.