Dynamics and Phenomena in Stateful Multi-Agent Systems
| dc.contributor.author | Gaitonde, Jason | |
| dc.contributor.chair | Tardos, Eva | en_US |
| dc.contributor.committeeMember | Kleinberg, Robert | en_US |
| dc.contributor.committeeMember | Sridharan, Karthik | en_US |
| dc.contributor.committeeMember | Chattopadhyay, Eshan | en_US |
| dc.date.accessioned | 2024-04-05T18:46:34Z | |
| dc.date.available | 2024-04-05T18:46:34Z | |
| dc.date.issued | 2023-08 | |
| dc.description | 321 pages | en_US |
| dc.description.abstract | An important goal at the intersection of theoretical computer science and economics is to understand the long-run outcomes of complex processes in multi-agent systems. In many cases, such social systems are inherently algorithmic and strategic; in others, agents may act in simpler behavioral ways in response to some underlying randomness in their environment. In real-world settings, of course, both of these features will likely arise. But regardless of the precise model of agent behavior, these local interactions give rise to important macroscopic outcomes that are vital to theoretically understand and quantify. A subtle factor in many such real-world systems is that their evolution strongly depends on past outcomes. For instance, strategic agents may use learning algorithms that adapt to the actions taken by the other agents in previous rounds, which in turn evolve based on past outcomes and actions. The underlying environment, strategic or stochastic, may itself also change in response to the sequence of past outcomes, as in ridesharing or information diffusion on networks. The complexities of statefulness induce substantial technical challenges that preclude existing analyses from applying. In this thesis, we develop new techniques towards understanding these important and dynamic social systems in two key settings: price of anarchy bounds in repeated games with state, and polarization and discord in models of opinion formation. In Part I, we consider the interplay between learning algorithms and welfare in repeated games with state (also known as stochastic games). In particular, we prove optimal price of anarchy guarantees for natural learning algorithms in two prototypical settings. First, we consider the long-run stability of queuing systems with strategic agents. Our main result shows that queuing systems with no-regret learners strategically competing will be stable so long as the queuing system has just twice the necessary resources under complete coordination. Nonetheless, we also demonstrate the myopia of no-regret learning in games with state by comparing these guarantees with those that can be obtained at long-run patient equilibrium. We then consider the long-run outcomes of learning dynamics in repeated auctions with budgets, an abstraction of the important setting of Internet ad auctions. We show that when all strategic agents use a form of budget pacing, a popular algorithmic approach to strategic bidding in both theory and practice, the resulting outcome of the auctions achieves at least half the optimal welfare attainable by any allocation. Collectively, these results highlight the surprising effectiveness of learning and welfare in stateful environments, as well as several challenges and subtleties. In Part II, we aim to capture a different class of macroscopic phenomena: namely, the long-run emergence of discord and polarization in models of opinion dynamics in networks. In these models, agents belong to a social network and maintain numerical opinions about one or more issues. They then update their beliefs according to simple behavioral rules in response to stochastic events and the beliefs of their neighbors in the network. While classical opinions of opinion formation, like the well-known DeGroot model, suggest approximate consensus ought be reached asymptotically, these theoretical predictions are contradicted by recent empirical observations. We make progress towards theoretically understanding these important global phenomena. We first demonstrate how polarization and discord can be induced by adversarial perturbations of Friedkin-Johnsen dynamics, focusing on the interplay between the underlying network structure and the algorithmic power of the adversary. We then demonstrate how polarization and issue alignment can arise, endogenously and robustly, in geometric models of opinion formation. A crucial theme of our analyses in all settings will be determining how local, round-by-round properties of social dynamics, which are easier to reason about, can coalesce to produce global, long-run properties. Our results suggest new avenues and techniques towards analyzing these kinds of social processes more broadly. | en_US |
| dc.identifier.doi | https://doi.org/10.7298/710t-xk53 | |
| dc.identifier.other | Gaitonde_cornellgrad_0058F_13741 | |
| dc.identifier.other | http://dissertations.umi.com/cornellgrad:13741 | |
| dc.identifier.uri | https://hdl.handle.net/1813/114627 | |
| dc.language.iso | en | |
| dc.rights | Attribution 4.0 International | * |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | * |
| dc.subject | algorithmic game theory | en_US |
| dc.subject | no-regret learning | en_US |
| dc.subject | opinion dynamics | en_US |
| dc.subject | price of anarchy | en_US |
| dc.title | Dynamics and Phenomena in Stateful Multi-Agent Systems | en_US |
| dc.type | dissertation or thesis | en_US |
| dcterms.license | https://hdl.handle.net/1813/59810.2 | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Cornell University | |
| thesis.degree.level | Doctor of Philosophy | |
| thesis.degree.name | Ph. D., Computer Science |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Gaitonde_cornellgrad_0058F_13741.pdf
- Size:
- 1.1 MB
- Format:
- Adobe Portable Document Format