Analysis of Algorithms for Mathematical Optimization Problem under UncertaintyCopyright: Mario Irrmischer
Improving local search for distributed resource allocation and equilibrium computation.
The advent of Industrial Revolution saw an increasing demand on road transportation network across the world. Growing population, rapid production of motor vehicles and rising demand for transfer of goods across cities, warranted well planned road networks that were favorable to efficient travel time. However, the efficacy of the road networks were thwarted by the non-cooperative nature of the users, resulting in congestion and non-optimal travel time. Thus, a comprehensive process that is conducive to at least assuage if not preclude the consequences of such user behavior was imperative.
The primary reason for congestion in road networks is due to the non-optimal distribution of traffic flow arising as a result of the selfish nature of the users. A user's rationale while traversing the network in order to reach his destination is to pick routes that have the least travel time from his current location at that point in time. Such a collective conduct by all the users of the road network resulted in a sub-optimal traffic flow along the network. One of the many approaches investigated to alleviate the aforementioned problem in the transportation network is the introduction of tolls or taxes on the roads in the network. The hope is that this persuades users into taking desirable traffic flows with respect to the network.
A transportation network can be succinctly represented using a directed graph. The nodes in the graph constitute the source and destination of the users in the road network and the edges that inter-connect the nodes represent the roads. Such a representation motivates us to investigate the problems arising in a transportation network by considering the game-theoretic aspect of the problem. Congestion games constitute an important class of games to model resource allocation by different users such as in traffic networks. In this joint work with Alexander Skopalik from the University of Twente, 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 a number of different results.
As computing an exact or even approximate pure Nash equilibrium is in general PLS-complete, Caragiannis et al. [FOCS 2011] 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 further improved to 1.6+epsilon by a seemingly simple modification of their algorithm using our technique. Bilo and Vinci [EC 2016] presented an algorithm to compute load depended taxes the improve the price of anarchy (PoA) e.g. for linear game from 2.5 to 2. Their algorithm is a centralized algorithm and is sensitive to changes of the instance such as e.g. the number of players. Our methods yield slightly weaker results, e.g., 2.012 for linear games. However, our approach is rather robust since, our tax functions are universal, locally computable and independent of the actually instance of the game. Computing an optimal allocation in congestion games is NP-hard. The best known centralized approximation algorithm is due to Makarychev and Srividenko [FOCS14]. Again, our technique does not quite match there bounds but offers a modified local search procedure as a much simpler alternative which can easily be implemented in a distributed fashion.
Our work considers optimizing a cost minimization game that represents various resource allocation problems. We define a slightly more general smoothness condition than Roughgarden and show that it is a sufficient condition to guarantee a certain approximation factor. From this condition we derive a linear program that computes a (convex) cost function for the resources to minimize the smoothness parameter. From its dual, we derive a reduction to a PoA lower bound of selfish scheduling on identical machines. This specific family of instances also implies a lower bound on the achievable approximation factor and hence, the optimality of the original LP. In case of the unweighted problem, we show that the PoA of the optimal modified game is equal to the PoA for scheduling on identical machines, implying that there is a simple local search algorithm that achieves this approximation ratio. Moreover, using approximate local search one can come arbitrarily close to that in polynomial time. For weighted, we show that the PoA with modified cost function is the PoA of the unmodified game. However, if we change the functions in a weight specific manner, we get exactly the bounds for the unweighted version of the problem. As for future work, we look at other variants such as utility maximization and shapley cost sharing games. We would also like to consider adapting our ideas to online learning techniques that converge faster to other local optimum concepts such as coarse correlated equilibrium.