All types (
22 )
agt (
3 )
approximation (
5 )
Conference (
15 )
Journal (
10 )
network (
10 )
Preprint (
3 )
probability (
6 )

Sort by year:

Game Theory and Mechanism Design are by now standard tools for studying and designing massive decentralized systems. Unfortunately, designing mechanisms that induce socially efficient outcomes often requires full information and prohibitively large computational resources. In this work we study simple mechanisms that require only *local* information. Specifically, in the setting of a classic scheduling problem, we demonstrate local mechanisms that induce outcomes with social cost close to that of the socially optimal solution. Somewhat counter-intuitively, we find that mechanisms yielding Pareto dominated outcomes may in fact enhance the overall performance of the system, and we provide a justification of these results by interpreting these inefficiencies as externalities being internalized. We also show how to employ randomization to obtain yet further improvements. Lastly, we use the game-theoretic insights gained to obtain a new combinatorial approximation algorithm for the underlying optimization problem.

We consider a priority-based selﬁsh routing model, where agents may have diﬀerent priorities on a link. An agent with a higher priority on a link can traverse it with a smaller delay or cost than an agent with lower priority. This general framework can be used to model a number of diﬀerent problems. The structural properties that lead to ineﬃciencies in routing choices appear diﬀerent in this priority-based model compared to the classical model. In particular, in parallel link networks with nonatomic agents, the price of anarchy is exactly one in the priority-based model; that is, selﬁsh behaviour leads to optimal routings. In contrast, in the standard model the worst possible price of anarchy can be achieved in a simple two-link network. For multi-commodity networks, selﬁsh routing does lead to ineﬃciencies in the priority-based model. We present tight bounds on the price of anarchy for such networks. Speciﬁcally, in the nonatomic case the worst-case price of anarchy is exactly $(d + 1)^{d+1}$ for polynomial latency functions of degree $d$ (hence 4 for linear cost functions). For atomic games, the worst-case price of anarchy is exactly $3+2\sqrt{2}$ in the weighted case, and exactly 17/3 in the unweighted case. An upper bound of $O(2^dd^d)$ is also shown for polynomial cost functions in the atomic case, although this is not tight. Our framework (and results) also generalise to include models similar to congestion games.