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

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.