A Primal-Dual Algorithm for Computing Fisher Equilibrium in the Absence of Gross Substitutability Property

We provide the first strongly polynomial time exact combinatorial algorithm to compute Fisher equilibrium for the case when utility functions do not satisfy the Gross substitutability property. The motivation for this comes from the work of Kelly, Maulloo, and Tan [15] and Kelly and Vazirani [16] on rate control in communication networks. We consider a tree like network in which root is the source and all the leaf nodes are the sinks. Each sink has got a fixed amount of money which it can use to buy the capacities of the edges in the network. The edges of the network sell their capacities at certain prices. The objective of each edge is to fix a price which can fetch the maximum money for it and the objective of each sink is to buy capacities on edges in such a way that it can facilitate the sink to pull maximum flow from the source. In this problem, the edges and the sinks play precisely the role of sellers and buyers, respectively, in the Fisher’s market model. The utility of a buyer (or sink) takes the form of Leontief function which is known for not satisfying Gross substitutability property. We develop an O(m3) exact combinatorial algorithm for computing equilibrium prices of the edges. The time taken by our algorithm is independent of the values of sink money and edge capacities. A corollary of our algorithm is that equilibrium prices and flows are rational numbers. Although there are algorithms to solve this problem but they are all based on convex programming techniques. To the best of our knowledge, ours is the first strongly polynomial time exact combinatorial algorithm for computing equilibrium prices of Fisher model under the case when buyers’ utility functions do not satisfy Gross substitutability property.