CAREER: A Game Theory Framework for Decentralized Decisions in Large-Scale Discrete Optimization Problems

About This Grant

This Faculty Early Career Development Program (CAREER) grant supports research that intends to enhance decision making in decentralized systems. Decentralized decision-making naturally arises in many scenarios, notably in supply chains and transportation and logistics, where multiple self-interested agents share a finite collection of common resources and influence each other's behavior. One crucial challenge arising in decentralized systems is the lack of coordination among interdependent decisions, which are made locally but have broader system-wide implications. This research project will approach decentralized decision-making through a game theoretic framework. For systems where the decisions are chosen from a discrete set, this project explores a computational approach that exploits the discrete nature of the individual optimization problems. The models and algorithms developed will be evaluated on a problem involving multiple loosely coordinated agents providing logistic support for post-disaster operations, with the goal to improve resource utilization and coordination among responding organizations. The educational component of the project aims to engage undergraduates and K-12 students in science through a community-building series and a structured portfolio of outreach activities. This project will integrate techniques from integer optimization and algorithmic game theory to establish new theoretical foundations and practical algorithms for resource-sharing games. In these games, multiple decision-makers, each solving their own integer optimization problem, interact while sharing a common set of resources. The methodology will leverage polyhedral characterizations, sparsity structures and decomposition methods beyond optimization, to provide certificates for existence of equilibrium solutions, algorithms for computing exact or approximate equilibria, bounds on equilibria inefficiency, and strategies to reduce such inefficiency. By exploiting polyhedral and combinatorial structures, the project looks to isolate key sources of complexity and identify broad classes of tractable games, both theoretically and computationally. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.