19 papers
What You Earn from What You Learn: Characterization and Complexity of the Value of Information
Ratip Emin Berker, Ioannis Anagnostides, Emanuel Tewolde +3
We examine the value of information in extensive-form decision problems: the largest multiplicative gain that a decision maker can obtain from an information refinement, taken over…
Efficient Learning of Survival Analysis Models Under Outcome-Dependent Truncation and Censoring
Itai Zilberstein, Ioannis Anagnostides, Arman Kilic +1
Modern machine learning models are typically trained on data assumed to be representative of the predictive tasks the model will face in the future, but practical datasets violate…
Normal-Form Correlation in Markov Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria…
Preference Elicitation for Policy Optimization and Application to Aligning Heart Transplantation with Human Values
Itai Zilberstein, Ioannis Anagnostides, Zachary W Sollie +2
Preference elicitation is essential for aligning AI systems with human values. Prior approaches (e.g., for organ allocation) often ask stakeholders to compare the decisions of an a…
Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling
Itai Zilberstein, Pranav Rajbhandari, Steve Chien +1
Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too…
The Computational Complexity of Team Zero-Sum Games
Ioannis Anagnostides, Ioannis Panageas, Tuomas Sandholm +1
A celebrated consequence of the minimax theorem is that two-player zero-sum games admit a tractable equilibrium characterization. In many central applications, however, each side c…
Aligning Data-Driven Predictors with Allocation: A Decision-Focused Approach to Survival Analysis
Itai Zilberstein, Ioannis Anagnostides, Tuomas Sandholm
Machine learning predictors have become essential tools for guiding automated decision making. However, a major misalignment persists: predictive models are typically optimized in…
Decision Making under Imperfect Recall: Algorithms and Benchmarks
Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides +2
In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' a…
The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games
Brian Hu Zhang, Ioannis Anagnostides, Kiriaki Fragkia +2
The proper equilibrium, introduced by Myerson (1978), is a classic refinement of the Nash equilibrium that has been referred to as the "mother of all refinements." For normal-form…
Learning Potentials for Dynamic Matching and Application to Heart Transplantation
Itai Zilberstein, Ioannis Anagnostides, Zachary W. Sollie +2
Each year, thousands of patients in need of heart transplants face life-threatening wait times due to organ scarcity. While allocation policies aim to maximize population-level out…
Near-Optimal Dynamic Matching via Coarsening with Application to Heart Transplantation
Itai Zilberstein, Ioannis Anagnostides, Zachary W. Sollie +2
Online matching has been a mainstay in domains such as Internet advertising and organ allocation, but practical algorithms often lack strong theoretical guarantees. We take an impo…
Position: Machine Learning for Heart Transplant Allocation Policy Optimization Should Account for Incentives
Ioannis Anagnostides, Itai Zilberstein, Zachary W. Sollie +2
The allocation of scarce donor organs constitutes one of the most consequential algorithmic challenges in healthcare. While the field is rapidly transitioning from rigid, rule-base…
(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris +1
Follow the regularized leader FTRL is the premier algorithm for online optimization. However, despite decades of research on its convergence in constrained optimization -- and pote…
On the Computational Complexity of Performative Prediction
Ioannis Anagnostides, Rohan Chauhan, Ioannis Panageas +2
Performative prediction captures the phenomenon where deploying a predictive model shifts the underlying data distribution. While simple retraining dynamics are known to converge l…
Equilibrium Refinements Improve Subgame Solving in Imperfect-Information Games
Ondrej Kubicek, Viliam Lisy, Tuomas Sandholm
Subgame solving is a technique for scaling algorithms to large games by locally refining a precomputed blueprint strategy during gameplay. While straightforward in perfect-informat…
Policy Optimization for Dynamic Heart Transplant Allocation
Ioannis Anagnostides, Zachary W. Sollie, Arman Kilic +1
Heart transplantation is a viable path for patients suffering from advanced heart failure, but this lifesaving option is severely limited due to donor shortage. Although the curren…
Convergence of Regret Matching in Potential Games and Constrained Optimization
Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang +3
Regret matching (RM) -- and its modern variants -- is a foundational online algorithm that has been at the heart of many AI breakthrough results in solving benchmark zero-sum games…
The Complexity of Equilibrium Refinements in Potential Games
Ioannis Anagnostides, Maria-Florina Balcan, Kiriaki Fragkia +3
The complexity of computing equilibrium refinements has been at the forefront of algorithmic game theory research, but it has remained open in the seminal class of potential games;…
Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games
Brian Hu Zhang, Ioannis Anagnostides, Tuomas Sandholm
A considerable chasm has been looming for decades between theory and practice in zero-sum game solving through first-order methods. Although a convergence rate of has long…