VGVasilis Gkatzelis

Vasilis Gkatzelis

*This is an algorithmically generated author record based on publicly available information.

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


Vasilis Gkatzelis has a total of 59 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Optimal metric distortion for matching on the line

    by Aris Filos-Ratsikas, Vasilis Gkatzelis, Mohamad Latifian, Emma Rewinski, Alexandros A. Voudouris

  • Deterministic Budget-Feasible Clock Auctions

    by Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, Xizhi Tan

    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.


  • Learning-augmented mechanism design

    by Xizhi Tan, Vasilis Gkatzelis

    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.

  • Bayesian and Randomized Clock Auctions

    by Michal Feldman, Vasilis Gkatzelis, Nick Gravin, Daniel Schoepflin

    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

    Procurement Auctions with Best and Final Offers

    by Vasilis Gkatzelis, Randolph Preston McAfee, Renato Paes Leme

  • Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

    by Priyank Agrawal, Eric Balkanski, Vasilis Gkatzelis, Tingting Ou, Xizhi Tan

    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

    Online Mechanism Design with Predictions

    by Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan, Cherlin Zhu


  • Open Access

    Learning-Augmented Metric Distortion via (p,q)-Veto Core

    by Ben Berger, Michal Feldman, Vasilis Gkatzelis, Xizhi Tan