Vasilis Gkatzelis
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Vasilis Gkatzelis has a total of 59 co-authors. Here are the top co-authors by number of shared publications:
- Xizhi Tan
Drexel University, Philadelphia, PA, USA
5 shared publications Richard Cole
New York University, New York, NY, USA
4 shared publicationsTim Roughgarden
Department of Computer Science, Stanford University, Stanford, California 94305
4 shared publications- Daniel Schoepflin
Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, Piscataway, New Jersey 08854
3 shared publications - Eric Balkanski
Department of Industrial Engineering and Operations Research, Columbia University, New York, USA
3 shared publications - Dimitris Fotakis
National Technical University of Athens Greece
2 shared publications
Latest Publications
- Open Access
- 7 October 2026
- Published by Elsevier in Artificial Intelligence
- Vol. 361
Optimal metric distortion for matching on the line
- 7 October 2026
- Published by Elsevier in Artificial Intelligence
- Vol. 361
Open AccessOptimal metric distortion for matching on the line
- 1 November 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (6) , 2972-2985
Deterministic Budget-Feasible Clock Auctions
In the budget-feasible mechanism design problem, an auctioneer with a strict budget constraint is looking to acquire services from a set of self-interested providers. The auctioneer aims to design a polynomial-time strategy-proof mechanism that maximizes the value of the services she acquires, subject to the sum of payments to providers falling within her budget. This problem has attracted a great deal of attention due to its combination of practical relevance and theoretical depth. In “Deterministic Budget-Feasible Clock Auctions,” Balkanski, Garimidi, Gkatzelis, Schoepflin, and Tan provide the first such deterministic mechanism that achieves a constant-factor approximation for instances where the auctioneer’s valuation function is submodular. Moreover, this mechanism achieves an improved approximation even compared with previously known randomized mechanisms, and it takes the form of a clock auction, implying a suite of important properties that make this auction much more practical.
- 1 November 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (6) , 2972-2985
Deterministic Budget-Feasible Clock Auctions
In the budget-feasible mechanism design problem, an auctioneer with a strict budget constraint is looking to acquire services from a set of self-interested providers. The auctioneer aims to design a polynomial-time strategy-proof mechanism that maximizes the value of the services she acquires, subject to the sum of payments to providers falling within her budget. This problem has attracted a great deal of attention due to its combination of practical relevance and theoretical depth. In “Deterministic Budget-Feasible Clock Auctions,” Balkanski, Garimidi, Gkatzelis, Schoepflin, and Tan provide the first such deterministic mechanism that achieves a constant-factor approximation for instances where the auctioneer’s valuation function is submodular. Moreover, this mechanism achieves an improved approximation even compared with previously known randomized mechanisms, and it takes the form of a clock auction, implying a suite of important properties that make this auction much more practical.
- Open Access
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 689-718
Simultaneously Satisfying MXS and EFL
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 689-718
Open AccessSimultaneously Satisfying MXS and EFL
- 2 July 2025
- Published by Drexel University Libraries
Learning-augmented mechanism design
The central theme of this thesis is the design of multi-agent systems that interact with self-interested agents, aiming to overcome strategic manipulation and information asymmetries. The design of such systems is typically guided by traditional analytical frameworks. While worst-case analysis offers robust guarantees, it can be overly pessimistic; Bayesian methods, in contrast, depend on precise distributional knowledge, limiting their real-world applicability. With the increasing availability of data and predictive tools, there is now an opportunity to improve outcomes by leveraging predictions, even though they are unreliable. This thesis systematically develops the framework of learning-augmented mechanism design, which integrates potentially unreliable predictions to achieve strong guarantees when predictions are accurate, while maintaining robust worst-case performance when they are not. By combining theoretical rigor with practical relevance, this approach significantly enhances mechanism performance in data-driven environments. Through detailed studies of canonical problems including auctions, decentralized network protocols, job scheduling, and social choice, this work demonstrates how integrating predictions can fundamentally improve outcomes. For instance, we develop combinatorial clock auctions that achieve near-optimal social welfare when predictions are accurate, while still preserving best-known worst-case guarantees. We also introduce prediction-augmented strategies for scheduling and procurement settings, achieving constant approximation ratios under accurate predictions, and robust linear guarantees otherwise. In the domain of social choice, this thesis derives new general upper bounds for metric distortion problems, offering improved performance unattainable through traditional deterministic methods alone. Moreover, this thesis contributes novel analytical techniques of broader interest, including general lower-bound constructions and smooth, error-dependent analyses applicable to related theoretical domains, such as sample complexity and learning theory. Collectively, these results highlight the power and versatility of predictions in mechanism design, providing both foundational insights and practical guidelines for future research in robust, data-driven economic systems.
- 2 July 2025
- Published by Drexel University Libraries
Learning-augmented mechanism design
The central theme of this thesis is the design of multi-agent systems that interact with self-interested agents, aiming to overcome strategic manipulation and information asymmetries. The design of such systems is typically guided by traditional analytical frameworks. While worst-case analysis offers robust guarantees, it can be overly pessimistic; Bayesian methods, in contrast, depend on precise distributional knowledge, limiting their real-world applicability. With the increasing availability of data and predictive tools, there is now an opportunity to improve outcomes by leveraging predictions, even though they are unreliable. This thesis systematically develops the framework of learning-augmented mechanism design, which integrates potentially unreliable predictions to achieve strong guarantees when predictions are accurate, while maintaining robust worst-case performance when they are not. By combining theoretical rigor with practical relevance, this approach significantly enhances mechanism performance in data-driven environments. Through detailed studies of canonical problems including auctions, decentralized network protocols, job scheduling, and social choice, this work demonstrates how integrating predictions can fundamentally improve outcomes. For instance, we develop combinatorial clock auctions that achieve near-optimal social welfare when predictions are accurate, while still preserving best-known worst-case guarantees. We also introduce prediction-augmented strategies for scheduling and procurement settings, achieving constant approximation ratios under accurate predictions, and robust linear guarantees otherwise. In the domain of social choice, this thesis derives new general upper bounds for metric distortion problems, offering improved performance unattainable through traditional deterministic methods alone. Moreover, this thesis contributes novel analytical techniques of broader interest, including general lower-bound constructions and smooth, error-dependent analyses applicable to related theoretical domains, such as sample complexity and learning theory. Collectively, these results highlight the power and versatility of predictions in mechanism design, providing both foundational insights and practical guidelines for future research in robust, data-driven economic systems.
- 1 July 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (4) , 1965-1982
Bayesian and Randomized Clock Auctions
The recently introduced and highly practical class of deferred acceptance clock auctions offers a unique combination of desirable properties, including obvious strategy-proofness, unconditional winner privacy, and transparency. Early excitement around these auctions was dampened due to a result demonstrating that no deterministic and prior-free clock auction can guarantee better than a logarithmic approximation of the optimal social welfare, even in simple settings. In “Bayesian and Randomized Clock Auctions,” Feldman, Gkatzelis, Gravin, and Schoepflin reignite this excitement by demonstrating that one can achieve improved results for a wide class of instances if a clock auction can either use randomization or has access to prior information. The authors provide three different clock auctions that achieve these improved guarantees given access to different amounts of prior information, exhibiting how additional information can further simplify the auction design.
- 1 July 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 73 (4) , 1965-1982
Bayesian and Randomized Clock Auctions
The recently introduced and highly practical class of deferred acceptance clock auctions offers a unique combination of desirable properties, including obvious strategy-proofness, unconditional winner privacy, and transparency. Early excitement around these auctions was dampened due to a result demonstrating that no deterministic and prior-free clock auction can guarantee better than a logarithmic approximation of the optimal social welfare, even in simple settings. In “Bayesian and Randomized Clock Auctions,” Feldman, Gkatzelis, Gravin, and Schoepflin reignite this excitement by demonstrating that one can achieve improved results for a wide class of instances if a clock auction can either use randomization or has access to prior information. The authors provide three different clock auctions that achieve these improved guarantees given access to different amounts of prior information, exhibiting how additional information can further simplify the auction design.
- Open Access
- 22 April 2025
- Published by Association for Computing Machinery (ACM)
- p. 3335-3343
Procurement Auctions with Best and Final Offers
- 22 April 2025
- Published by Association for Computing Machinery (ACM)
- p. 3335-3343
Open AccessProcurement Auctions with Best and Final Offers
- 1 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (4) , 2626-2651
Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in “learning-augmented algorithms.” Aiming to complement the traditional worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are inaccurate (robustness). We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well, even when the predictions are not fully accurate. Funding: The work of E. Balkanski was supported in part by the National Science Foundation [Grants CCF-2210501 and IIS-2147361]. The work of V. Gkatzelis and X. Tan was supported in part by the National Science Foundation [Grant CCF-2210502] and [CAREER Award CCF-2047907].
- 1 November 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (4) , 2626-2651
Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in “learning-augmented algorithms.” Aiming to complement the traditional worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are inaccurate (robustness). We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well, even when the predictions are not fully accurate. Funding: The work of E. Balkanski was supported in part by the National Science Foundation [Grants CCF-2210501 and IIS-2147361]. The work of V. Gkatzelis and X. Tan was supported in part by the National Science Foundation [Grant CCF-2210502] and [CAREER Award CCF-2047907].
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1184
Online Mechanism Design with Predictions
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1184
Open AccessOnline Mechanism Design with Predictions
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 984
Learning-Augmented Metric Distortion via (p,q)-Veto Core
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 984
Open AccessLearning-Augmented Metric Distortion via (p,q)-Veto Core
- 1 January 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 72 (1) , 167-184
Resource-Aware Cost-Sharing Methods for Scheduling Games
- 1 January 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 72 (1) , 167-184
Resource-Aware Cost-Sharing Methods for Scheduling Games