NDLI: A Simple and Efficient Algorithm for Computing Market Equilibria

Please wait, while we are loading the content...

ACM Transactions on Algorithms (TALG) : Volume 13

ACM Transactions on Algorithms (TALG) : Volume 12

Issue 4, September 2016

Issue 3, June 2016

Scale-Free Compact Routing Schemes in Networks of Low Doubling Dimension

Distributed Algorithms for End-to-End Packet Scheduling in Wireless Ad Hoc Networks

Fast Constructions of Lightweight Spanners for General Graphs

The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs

LIMITS and Applications of Group Algebras for Parameterized Problems

Approximating Semi-matchings in Streaming and in Two-Party Communication

Optimal Orthogonal Graph Drawing with Convex Bend Costs

A Simple and Efficient Algorithm for Computing Market Equilibria

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median

On the Expected Complexity of Voronoi Diagrams on Terrains

All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns

Sparse Text Indexing in Small Space

Point Line Cover: The Easy Kernel is Essentially Tight

On Problems as Hard as CNF-SAT

Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack

The Traveling Salesman Problem for Lines, Balls, and Planes

A Faster Algorithm for Computing Straight Skeletons

Issue 1(Special Issue on SODA'12 and Regular Papers), February 2016

Issue 2, February 2016

ACM Transactions on Algorithms (TALG) : Volume 11

ACM Transactions on Algorithms (TALG) : Volume 10

ACM Transactions on Algorithms (TALG) : Volume 9

ACM Transactions on Algorithms (TALG) : Volume 8

ACM Transactions on Algorithms (TALG) : Volume 7

ACM Transactions on Algorithms (TALG) : Volume 6

ACM Transactions on Algorithms (TALG) : Volume 5

ACM Transactions on Algorithms (TALG) : Volume 4

ACM Transactions on Algorithms (TALG) : Volume 3

ACM Transactions on Algorithms (TALG) : Volume 2

ACM Transactions on Algorithms (TALG) : Volume 1

A Simple and Efficient Algorithm for Computing Market Equilibria

Content Provider	ACM Digital Library
Author	Fleischer, Lisa Saberi, Amin Kapoor, Sanjiv Khandekar, Rohit Garg, Rahul
Copyright Year	2016
Abstract	We give a new mathematical formulation of market equilibria in exchange economies using an indirect utility function: the function of prices and income that gives the maximum utility achievable. The formulation is a $\textit{convex}$ program and can be solved when the indirect utility function is convex in prices. We illustrate that many economies, including: —Homogeneous utilities of degree α ∈ [0, 1] in Fisher economies—this includes Linear, Leontief, Cobb-Douglas —Resource allocation utilities like multi-commodity flows satisfy this condition and can be efficiently solved. Further, we give a natural tâtonnement type price-adjusting algorithm in these economies. Our algorithm, which is applicable to a larger class of utility functions than previously known weak gross substitutes, mimics the natural dynamics for the markets as suggested by Walras: it iteratively adjusts a good’s price upward when the demand for that good under current prices exceeds its supply; and downward when its supply exceeds its demand. The algorithm computes an approximate equilibrium in a number of iterations that is independent of the number of traders and is almost $\textit{linear}$ in the number of goods.
Starting Page	1
Ending Page	15
Page Count	15
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/2905372
Volume Number	12
Issue Number	3
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-05-13
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Market equilibrium Approximation algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Market equilibrium via a primal--dual algorithm for a convex program

A fast and simple algorithm for computing market equilibria.

A simple approximation algorithm for computing arrow-debreu prices (2012).

Computing equilibria for a service provider game with (Im)perfect information

A Primal-Dual Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions

Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

A new optimal algorithm for weighted approximation and integration over ℝ

An efficient algorithm for accelerating the convergence of oscillatory series, useful for computing the polylogarithm and Hurwitz zeta functions

An efficient algorithm for the generalized centro-symmetric solution of matrix equation A X B = C

A Simple and Efficient Algorithm for Computing Market Equilibria

Similar Documents

Market equilibrium via a primal--dual algorithm for a convex program

A fast and simple algorithm for computing market equilibria.

A simple approximation algorithm for computing arrow-debreu prices (2012).

Computing equilibria for a service provider game with (Im)perfect information

A Primal-Dual Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions

Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

A new optimal algorithm for weighted approximation and integration over ℝ

An efficient algorithm for accelerating the convergence of oscillatory series, useful for computing the polylogarithm and Hurwitz zeta functions

An efficient algorithm for the generalized centro-symmetric solution of matrix equation A X B = C

A Simple and Efficient Algorithm for Computing Market Equilibria