eCommons

 

Dynamics and Phenomena in Stateful Multi-Agent Systems

Other Titles

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.

Journal / Series

Volume & Issue

Description

321 pages

Sponsorship

Date Issued

2023-08

Publisher

Keywords

algorithmic game theory; no-regret learning; opinion dynamics; price of anarchy

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Tardos, Eva

Committee Co-Chair

Committee Member

Kleinberg, Robert
Sridharan, Karthik
Chattopadhyay, Eshan

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Attribution 4.0 International

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record