國立虎尾科技大學 |

Dynamics and Phenomena in Stateful Multi-Agent Systems.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Dynamics and Phenomena in Stateful Multi-Agent Systems./
Author:	Gaitonde, Jason.
Description:	1 online resource (322 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-03, Section: A.
Contained By:	Dissertations Abstracts International85-03A.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9798380317450

Dynamics and Phenomena in Stateful Multi-Agent Systems.
Gaitonde, Jason.

Dynamics and Phenomena in Stateful Multi-Agent Systems. - 1 online resource (322 pages)

Source: Dissertations Abstracts International, Volume: 85-03, Section: A.

Thesis (Ph.D.)--Cornell University, 2023.

Includes bibliographical references

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.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798380317450Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

Algorithmic game theoryIndex Terms--Genre/Form:

554714
Electronic books.

Dynamics and Phenomena in Stateful Multi-Agent Systems.
LDR:05575ntm a22003977 4500 001 1143808
005 20240517104958.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798380317450
035 $a (MiAaPQ)AAI30531197
035 $a AAI30531197
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Gaitonde, Jason. $3 1468601
245 1 0 $a Dynamics and Phenomena in Stateful Multi-Agent Systems.
264 0 $c 2023
300 $a 1 online resource (322 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-03, Section: A.
500 $a Advisor: Tardos, Eva.
502 $a Thesis (Ph.D.)--Cornell University, 2023.
504 $a Includes bibliographical references
520 $a 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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Computer engineering. $3 569006
653 $a Algorithmic game theory
653 $a Opinion dynamics
653 $a Macroscopic outcomes
653 $a Natural learning algorithms
653 $a Queuing systems
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0464
690 $a 0501
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Cornell University. $b Computer Science. $3 1179602
773 0 $t Dissertations Abstracts International $g 85-03A.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30531197 $z click for full text (PQDT)