• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Combinatorial and exchange markets: Algorithms, complexity, and applications

    Thumbnail
    View/Open
    YAZDANBOD-DISSERTATION-2018.pdf (1.073Mb)
    Date
    2018-05-23
    Author
    Yazdanbod, Sadra
    Metadata
    Show full item record
    Abstract
    In today's world, globalization and the Internet have resulted in the creation of enormously many different kinds of marketplaces. The marketplaces naturally tend to find an equilibrium in terms of prices and interaction of agents. Therefore, understanding the equilibria results in better understanding and prediction of the marketplaces. In this thesis, we study two broad classes of equilibria. The first one is called market price equilibria, which can explain and predict prices within a market. The second one is Nash equilibria (NE), which is arguably the most important and well-studied solution concept within game theory. NE helps us to explain and predict the interactions between agents within a market. - Market price equilibria. We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling and communicating over a network. We give a proof of the existence of equilibria and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. Next, we show FIXP-hardness of computing equilibria in Arrow-Debreu exchange markets under Leontief utility functions, and Arrow-Debreu markets under linear utility functions and Leontief production sets, thereby settling these open questions of Vazirani and Yannakakis (2011). As a consequence of the results stated above, and the fact that membership in FIXP has been established for PLC utilities, the entire computational difficulty of Arrow-Debreu markets under PLC utility functions lies in the Leontief utility subcase. Finally, we give a polynomial time algorithm for finding an equilibrium in Arrow-Debreu exchange markets under Leontief utility functions provided the number of agents is a constant. - Nash equilibria. The complexity of 2-player Nash equilibrium is by now well understood. Our contribution is on settling the complexity of finding equilibria with special properties on multi-player games. We show that the following decision versions of 3-Nash are EXISTS-R-complete: checking whether 1. there are two or more equilibria, 2. there exists an equilibrium in which each player gets at least h payoff, where $h$ is a rational number, 3. a given set of strategies are played with non-zero probability, and 5. all the played strategies belong to a given set. EXISTS-R is the class of decision problems which can be reduced in polynomial time to Existential Theory of the Reals. Next, we give a reduction from 3-Nash to symmetric 3-Nash.
    URI
    http://hdl.handle.net/1853/60221
    Collections
    • College of Computing Theses and Dissertations [1071]
    • Georgia Tech Theses and Dissertations [22401]
    • School of Computer Science Theses and Dissertations [79]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology