2025 : 6 : 7
Mehdi Ghiyasvand

Mehdi Ghiyasvand

Academic rank: Associate Professor
ORCID:
Education: PhD.
ScopusId: 13104152900
HIndex:
Faculty: Faculty of Science
Address:
Phone:

Research

Title
COMPUTING ARROW-DEBREU PRICES FOR THE CASE OF LINEAR UTILITIES
Type
Presentation
Keywords
ثبت نشده‌است!
Year
2013
Researchers Mehdi Ghiyasvand

Abstract

In this paper, we consider a market consisting of n divisible goods and n' buyers. Garg and Kapoor 's algorithm[3] is the current fastest algorithm with combinatorial method to solve Arrow-Debreu model. Their algorithm computes an approximate answer for each parameter ε > 0 and runs in O(((n'n2 + nn'2 ) /ε )(log n /ε )) time. In this paper, we use the scaling algorithm in [8] and Devanour and Vazirani's algorithm[2] as black boxes to find O((( n + n' )(m + (n + n' ) log( n + n' )) log n) /ε ) time to solve this problem, where m is the number of eligible arcs between buyers and goods. This running time is faster than the Garg and Kapoor 's algorithm for ε < n (2^(log( n+ n ')^2).