38 papers
On the LLM Verification for Argument Graph Generation
Jakub Bąba, Jarosław A. Chudziak
Multi-agent LLM systems can formalize natural-language argumentation end-to-end, turning plain text into structured graphs by classifying components, connecting them with relations…
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…
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
Ioannis Anagnostides, Weiqiang Zheng
A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing to a fixed action. Motivated by…
From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +3
Budget-feasible mechanism design is a classic framework introduced by Singer, but there is still a wide gap between existing upper and lower bounds. In this paper, we significantly…
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…
Compensation Design
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +5
We introduce compensation design, the problem of designing payment rules that incentivize high-quality contributions in decentralized environments. Here, a budget-constrained princ…
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…
On the Complexity of Correlated Equilibria Beyond Normal-Form Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
Correlated equilibria are a fundamental solution concept in game theory. However, despite decades of research, the complexity beyond games of polynomial type -- such as extensive-f…
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…
Swap Regret Minimization Through Response-Based Approachability
Ioannis Anagnostides, Gabriele Farina, Maxwell Fishelson +2
We consider the problem of minimizing different notions of swap regret in online optimization. These forms of regret are tightly connected to correlated equilibrium concepts in gam…
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…
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…
A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm +1
Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization. However, this expressivity comes at the cost of computational hardness…