• A primal-dual algorithm for co...

Result: A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property

Title:
A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property
Authors:
GARG, Dinesh, JAIN, Kamal, TALWAR, Kunal, VAZIRANI, Vijay V
Source:
Internet and Network EconomicsTheoretical computer science. 378(2):143-152
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 26 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Théorie programmation, Programming theory, Divers, Miscellaneous, Arbre, Tree, Arbol, Calcul automatique, Computing, Cálculo automático, Communication, Comunicación, Connaissance, Knowledge, Conocimiento, Equilibre, Equilibrium, Equilibrio, Flot, Flow, Oleada, Informatique théorique, Computer theory, Informática teórica, Maximum, Máximo, Noeud, Node, Nudo, Polynôme, Polynomial, Polinomio, Programmation convexe, Convex programming, Programación convexa, Recherche, Research, Investigación, Réseau communication, Communication network, Red de comunicación, Stabilité numérique, Numerical stability, Estabilidad numérica, Temps polynomial, Polynomial time, Tiempo polinomial, 05C05, 68N19, 68Wxx, Algorithme combinatoire, Combinatorial algorithm, Algorithme polynomial, Equité, Nombre rationnel, Computing market equilibria, Fisher equilibrium, Gross substitutability property, Primal-dual algorithm, Strongly polynomial time exact algorithm
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science and Automation, Indian Institute of Science, Bangalore - 560 012, India
One Microsoft Way, Redmond, WA 98052, United States
United States College of Computing, Georgia Institute of Technology, Atlanta, GA 30332-0280, United States
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18799218
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.18799218
Database:
PASCAL Archive

Further Information

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 [F.P Kelly, A.K. Maulloo, D.K.H. Tan, Rate control for communication networks: Shadow prices, proportional fairness and stability, Journal of Operational Research (1998)] and Kelly and Vazirani [F.P Kelly, Vijay V. Vazirani, Rate control as a market equilibrium (2003) (in preparation)] 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 that 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 Fisher's market model. The utility of a buyer (or sink) takes the form of a Leontief function which is known for not satisfying Gross substitutability property. We develop an 0(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 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's model under the case when buyers' utility functions do not satisfy gross substitutability property.