Efficiency Loss in a Network Resource Allocation Game

TLDR

The study contributes to the price‑of‑anarchy literature, examining how selfish actions impact system efficiency. The paper investigates how users in a congestion game anticipate price impacts of their actions. The authors analyze a congestion game where users anticipate price effects, and extend the model to a network setting with link‑specific payments. The authors prove that selfish behavior yields at least 75 % of optimal aggregate utility in single‑resource, network, and multi‑resource allocation settings.

Abstract

We explore the properties of a congestion game in which users of a congested resource anticipate the effect of their actions on the price of the resource. When users are sharing a single resource, we establish that the aggregate utility received by the users is at least 3/4 of the maximum possible aggregate utility. We also consider extensions to a network context, where users submit individual payments for each link in the network they may wish to use. In this network model, we again show that the selfish behavior of the users leads to an aggregate utility that is no worse than 3/4 of the maximum possible aggregate utility. We also show that the same analysis extends to a wide class of resource allocation systems where end users simultaneously require multiple scarce resources. These results form part of a growing literature on the “price of anarchy,” i.e., the extent to which selfish behavior affects system efficiency.