Modern systems consist of self-interested agents with potentially conflicting objectives. These agents interact in a dynamic manner, modifying their strategies over time to improve their payoffs. The presence of self-interested agents in such systems necessitates the analysis of the impact of various strategic considerations on the overall system, and the design of new systems with improved performance guarantees.
Motivated by this observation, in the first part of this thesis, we focus on fundamental structural properties of games, and exploit them to provide a new framework for analyzing the limiting behavior of strategy update rules in various game-theoretic settings. More specifically, we focus on potential games, a special class of games with desirable equilibrium and dynamic properties, and analyze their preference structure. Exploiting this structure, we obtain a decomposition of arbitrary games into three components, which we refer to as the potential, harmonic, and nonstrategic components. We show that the potential component has desirable equilibrium and dynamic properties (e.g., convergence of various strategy update rules to a Nash equilibrium), whereas the harmonic component has quite different and remarkable characteristics. We then establish that the decomposition can be used to characterize the limiting behavior of adaptive dynamics in arbitrary finite strategic form games: the limiting behavior of dynamics in a given game can be characterized by first identifying its potential component, and then analyzing the dynamics in this component.
In the second part of the thesis, we change our focus to designing novel multi-item iterative auctions. Multi-item iterative auctions are a class of mechanisms that are commonly employed in practice, for instance, in the context of spectrum and procurement auctions. However, the existing iterative auction formats that are provably efficient, have certain limitations. Specifically, they are either restricted to environments that do not allow for value complementarity between different items, or they require complex pricing structures. In this part of the thesis, we develop new, practical, and efficient iterative auctions for multi-item settings that exhibit both value complementarity and substitutability. We obtain such auctions by focusing on a natural class of valuation functions that admit a compact representation, which we refer to as graphical valuations.
For special classes of graphical valuations, such as tree valuations, our auctions implement the efficient outcome using item pricing, i.e., offering an anonymous price for each item. However, we establish that this simple pricing structure is not sufficient when the underlying value graph has cycles. On the other hand, we show that for general graphical valuations, auction formats, which rely on offering a bidder-specific price for each item and discounts/markups for pairs of items, can guarantee efficiency. These results suggest that when valuation functions of bidders exhibit some special structure, it is possible to systematically exploit it, in order to develop simple efficient iterative auction formats.
This talk will provide a brief overview of the first part of the thesis, and focus mainly on the results of the second part.
Thesis advisers. Asuman Ozdaglar, Pablo Parrilo
Thesis Committee. Daron Acemoglu, Georgia Perakis