Unit:
Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)Πληροφορική
Author:
Karathanos Christos
Supervisors info:
Βασίλειος Ζησιμόπουλος, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Ισορροπία Αγοράς με Γραμμικές Αντικειμενικές Συναρτήσεις
Translated title:
Market Equilibria with Linear Utility Functions
Summary:
This thesis focuses on the problem of finding Equilibria in Arrow-Debreu and Fisher markets with Linear Utilities. In the first part, we present polynomial time algorithms via convex programming. Such algorithms use the Ellipsoid algorithm as a black box and are notoriously non-practical, therefore, there has recently been a lot of effort towards obtaining algorithms through the use of combinatorial tools, such as flow computation in graphs. In the second part, we focus on algorithms of such nature. First, we present a strongly polynomial algorithm for Fisher Markets and after highlighting the main techniques used by it we analyze its complexity. Finally, we focus on extensions of those techniques that lead to the development of a weakly-polynomial combinatorial algorithms for Arrow-Debreu markets with Linear utilies.
Main subject category:
Science
Keywords:
market equilibrium, Fisher market, Arrow-Debreu market, strongly polynomial algorithm, combinatorial algorithms
