• 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.

    Algorithmic Game Theory

    Thumbnail
    View/Open
    mehta_aranyak_s_200508_phd.pdf (434.3Kb)
    Date
    2005-07-19
    Author
    Mehta, Aranyak
    Metadata
    Show full item record
    Abstract
    The interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for algorithm design, which is to optimize in the presence of strategic behavior. Second, it has prompted us to consider the computational aspects of various solution concepts from game theory, economics and auction design which have traditionally been considered mainly in a non-constructive manner. In this thesis we present progress along both these directions. We first consider optimization problems that arise in the design of combinatorial auctions. We provide an online algorithm in the important case of budget-bounded utilities. This model is motivated by the recent development of the business of online auctions of search engine advertisements. Our algorithm achieves a factor of $1-1/e$, via a new linear programming based technique to determine optimal tradeoffs between bids and budgets. We also provide lower bounds in terms of hardness of approximation in more general submodular settings, via a PCP-based reduction. Second, we consider truth-revelation in auctions, and provide an equivalence theorem between two notions of strategy-proofness in randomized auctions of digital goods. Last, we consider the problem of computing an approximate Nash equilibrium in multi-player general-sum games, for which we provide the first subexponential time algorithm.
    URI
    http://hdl.handle.net/1853/7220
    Collections
    • College of Computing Theses and Dissertations [1156]
    • Georgia Tech Theses and Dissertations [23403]

    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