Ph.D. Dissertation Defense: Jared Soundy
Thursday, July 11, 2024
8:00 AM CST
Zoom Link: https://unl.zoom.us/j/93596771640
"Aggregate Games: Computations and Applications"
Existing computational game theory studies consider compact representations of games that capture agent interaction in real-world environments and examine computation aspects of computing equilibrium concepts to analyze or predict agent behavior. One of the most well-studied representations that capture many commonly studied real-world environments is aggregate games. Aggregate games, first systematically studied by Nobel laureate Reinhard Selten, have various applications in modeling the decision-making interdependence of agents, where each agent’s utility function depends on their own actions and the aggregations or summarizations of the actions of all agents. These applications include Cournot oligopoly competition, public good contribution, and voting, where an agent’s action (e.g., goods to produce, amount to contribute to public good, and vote) depends only on the aggregation of all other agents’ actions (e.g., total goods produced, total public contributions, and total percentage of votes).
For the first part of this thesis, we extend aggregate games to model two complementary non-cooperative game-theoretic scenarios capturing certain aspects of real-world characteristics. These scenarios have been examined by us and are not known to be modeled by aggregate games previously. For the first scenario, we introduce (collaborative) public project contribution games with thresholds, where each agent determines which projects to contribute to and each project's success depends on the total contribution exceeding their threshold. The thresholds model project failure from insufficient contributions, not modeled by prior work. The second scenario examines (competitive) multi-dimensional congestion games, where each agent determines which resources to use with the cost of using each resource depending on its total demands in multiple dimensions. These games are a recent extension of the popular congestion games. For these two games and their variants, we examine the open computational complexity of determining and computing Nash Equilibria (NE), a fundamental solution concept in game theory, and related problems.
For the second part of this thesis, we consider aggregate games and examine open computational questions on NE and strong NE, which extends NE for agent coalitions, by using insights from the first part of this thesis. We also demonstrate how aggregate game algorithms for NE and strong NE can be applied to several popular games (e.g., congestion games, anonymous games, and Schelling games).
Committee:
Hau Chan, Chair
Leen-Kiat Soh
Rahul Purandare
Teck Yong Tan
Mohammad Irfan