Date: May 11, 2026
Time: 3:30-4:30 p.m.
Location: Gates Hall, 122 or Click here to attend via Zoom
Speaker: Vasilis Gkatzelis, Associate Professor in Computer Science at Drexel University
Abstract: We introduce the problem of designing mechanisms that incentivize strategic agents to form self-sufficient marketplaces. In our model, each participating agent $i$ generates revenue $r_i$ and incurs a participation cost $c_i$, unknown to the mechanism; crucially, $c_i$ can be greater or smaller than $r_i$. Each subset of agents $S$ yields a value $v(S)$ and the objective is to choose a set that maximizes the value while ensuring that each $i\in S$ receives a payment $p_i\geq c_i$ and that $S$ is budget-balanced, i.e., $\sum_{i\in S} p_i \leq \sum_{i\in S} r_i$. This problem generalizes the well-studied budget-feasible mechanism design problem,
where the requirement is that $\sum_{i\in S} p_i \leq B$ for some publicly known budget $B$.
We first consider the optimal value as a benchmark and show that there exist instances where every Nash equilibrium of every auction fails to achieve a constant approximation. We complement this result by proposing a
class of auctions whose subgame perfect equilibria achieve the optimal approximation guarantees. We then introduce an alternative value benchmark that better captures the liquidity of the market and we provide an auction whose subgame perfect equilibria achieve a constant approximation of this benchmark.
This is joint work with Yuan Deng, Xizhi Tan, Grigoris Velegkas, and Song Zuo
Bio: Vasilis Gkatzelis is an associate professor in computer science at Drexel University. He is a recipient of the NSF Faculty Early Career Development Program (CAREER) award. He previously held positions as a postdoctoral scholar at the computer science departments of UC Berkeley and Stanford University, and as a research fellow at the Simons Institute for the Theory of Computing. He received his PhD from the Courant Institute of New York University and his Diploma from the Computer Engineering and Informatics department of the University of Patras. His research focuses on problems in algorithm design and analysis, and algorithmic game theory.