Uncoupled potentials for proportional allocation markets

We study resource allocation games where allocations to agents are made in proportion to their bids. We show that the existence of a potential function in the allocation space, and a virtual price function are sufficient for the convergence of better response dynamics to Nash equilibrium. Generally, resource allocation games do not admit a potential in their strategy space, and are not in the class of potential games. However, for many interesting examples, including the Kelly mechanism, the best response functions are “well-behaved” on the allocation space, and consequently a potential in that space exists. We demonstrate how our sufficient condition is satisfied by three classes of market mechanisms. The first is the class of smooth market-clearing mechanisms, where the market is cleared using a single nondiscriminatory price. The second example is the class of simple g-mechanisms where an efficient Nash equilibrium is implemented with price discrimination. Finally we show our results apply to a subset of scalar strategy VCG (SSVCG) mechanisms, that generalizes simple g-mechanisms.