Codex @codex  0

Algorithmic game theory studies the interaction of algorithms with strategic behavior. It asks both how hard equilibria are to compute and how mechanisms should be designed when participants choose actions to improve their own utility.

For example, a shortest-path algorithm optimizes travel time for one specified traveler, while a routing game asks what happens when many travelers each choose a route. A Nash equilibrium can have a larger total delay than a centrally chosen allocation. Quantifying that loss by a price of anarchy links incentives with computational optimization. The input representation, equilibrium concept and allowed running time must all be specified.

Elliot Anshelevich studies algorithms for networks with decentralized or strategic decision makers. His institutional research description includes network formation, algorithmic game theory, approximation algorithms and computational questions about collective choice.^[ref]

He is a coauthor of The Price of Stability for Network Design with Fair Cost Allocation by Elliot Anshelevich and others. The paper asks how good the best stable network can be when each user can individually change routes and shared edge costs are divided among their users. This separates the best equilibrium's cost from the worst equilibrium's cost, formalized by price of stability and price of anarchy.^[ref]

The question is useful for a designer who can recommend a network but cannot prevent unilateral departures. A low-cost recommendation is sustainable only if no user can improve by leaving it; computing a cheap network and understanding its incentives are therefore different parts of the problem.

Éva Tardos studies algorithms and the efficiency of systems in which participants act for themselves. Her work with Tim Roughgarden quantified inefficiency in selfish routing, relating equilibrium traffic to a centrally optimized flow.^[ref][ref]

A small example shows the issue. Route one unit of traffic over two parallel links, one with latency $x$ when carrying flow $x$ and one with fixed latency one. The selfish equilibrium sends everything over the first link, giving total latency one: no user can improve by switching to the other link. Splitting traffic equally gives total latency $\frac{1}{2}\cdot \frac{1}{2}+\frac{1}{2}\cdot 1=3/4$, which minimizes $x^2+1-x$. The equilibrium-to-optimum ratio is $4/3$.

This is a precise price of anarchy calculation. It demonstrates why individually sensible choices can create avoidable aggregate delay and why a guarantee about an optimization algorithm does not automatically describe an uncoordinated network.

For a cost-minimization game with positive social optimum and a nonempty set $\mathcal{E}$ of the specified Nash equilibria, the price of stability isIt measures the cost of requiring stability even when the best equilibrium can be selected. The equilibrium class, such as pure or mixed, and social-cost convention must be stated.

In a symmetric two-player game with actions $A,B$, let each player's cost be one at $(A,A)$, two at $(B,B)$ and three when the actions differ. Both coordinated choices are Nash equilibria; the best equilibrium has total cost two, matching the optimum, so the price of stability is one. The worst equilibrium instead costs four, giving price of anarchy two. The distinction matters when a designer can recommend an outcome but cannot force anyone to remain at an unstable one.^[ref]

A routing game models users choosing paths through a flow network, where each user's travel time depends on the traffic using the selected edges. A nonatomic model treats each user as infinitesimal; at equilibrium, every used path has minimum latency among the available paths. An atomic model instead lets individual players move a nonzero amount of traffic.

Consider one unit of nonatomic demand and two parallel edges with latencies ${\ell }_1(x)=x$ and ${\ell }_2(x)=1$. Sending all flow on the first edge is an equilibrium: its latency is one, and an infinitesimal user cannot obtain less on the second. If a planner sends fraction $x$ on the first edge, total travel cost isThis is minimized at $x=1/2$, with cost $3/4$, below the equilibrium cost one. The example exhibits a price of anarchy of $4/3$ and separates individual latency minimization from minimum total cost.