TY - GEN
T1 - Application of M-Convex submodular flow problem to mathematical economics
AU - Murota, Kazuo
AU - Tamura, Akihisa
PY - 2001/12/1
Y1 - 2001/12/1
N2 - This paper shows an application of the M-convexs ubmodular flow problem to an economic model in which producers and consumers trade various indivisible commodities through a perfectly divisible commodity, money. We give an efficient algorithm to decide whether a competitive equilibrium exists or not, when cost functions of the producers are M« convex and utility functions of the consumers are M« concave and quasilinear in money. The algorithm consists of two phases: the first phase computes productions and consumptions in an equilibrium by solving an M-convexs ubmodular flow problem and the second finds an equilibrium price vector by solving a shortest path problem.
AB - This paper shows an application of the M-convexs ubmodular flow problem to an economic model in which producers and consumers trade various indivisible commodities through a perfectly divisible commodity, money. We give an efficient algorithm to decide whether a competitive equilibrium exists or not, when cost functions of the producers are M« convex and utility functions of the consumers are M« concave and quasilinear in money. The algorithm consists of two phases: the first phase computes productions and consumptions in an equilibrium by solving an M-convexs ubmodular flow problem and the second finds an equilibrium price vector by solving a shortest path problem.
UR - http://www.scopus.com/inward/record.url?scp=0038768365&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0038768365&partnerID=8YFLogxK
U2 - 10.1007/3-540-45678-3_2
DO - 10.1007/3-540-45678-3_2
M3 - Conference contribution
AN - SCOPUS:0038768365
SN - 3540429859
SN - 9783540429852
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 14
EP - 25
BT - Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
T2 - 12th International Symposium on Algorithms and Computation, ISAAC 2001
Y2 - 19 December 2001 through 21 December 2001
ER -