Vasilis Gkatzelis, PhD, an assistant professor in the Department of Computer Science at Drexel University’s College of Computing & Informatics (CCI), was selected by the National Science Foundation (NSF) to receive a Faculty Early Career Development Award (CAREER).
A CAREER award is NSF’s most prestigious award in support of early-career faculty who have the potential to serve as academic role models in research and education and to lead advances in the mission of their department or organization.
The award provides $599,782 in funding over five years for Gkatzelis’ project titled “Optimal Mechanism Design without Monetary Transfers.” The project (full abstract below) focuses on the design of multiagent resource-allocation mechanisms that take into consideration the preferences of the participating agents and seek to maximize fairness and efficiency in the resulting outcomes.
Gkatzelis hopes the research will have applications to benefit Drexel students in their search for the ideal co-op position to meet their academic and professional goals.
“An application of this research project that is particularly relevant to Drexel is the co-op matching market, where students and employers report their preferences and are then matched based on these preferences,” said Gkatzelis. “This research project has the potential to help further improve the co-op matching market by carefully analyzing and adjusting its mechanisms.”
Gkatzelis is the recipient of two other NSF grants: "The Efficiency of Clock Auctions" ($358,000, July 2020 to July 2023) and "Practical Auction Design Using the Deferred-Acceptance Framework" ($183,000, Feb. 2018 to Jan. 2020).
Gkatzelis teaches computer science courses including Approximation Algorithms and Algorithmic Game Theory, and also leads the Drexel Computer Science Theory reading group. His research interests include algorithmic mechanism design, multiagent resource allocation, and approximation algorithms. His work has been published at the ACM Symposium on Theory of Computing (STOC), the IEEE Symposium on Foundations of Computer Science (FOCS), the ACM Conference on Economics and Computation (EC), and the ACM-SIAM Symposium on Discrete Algorithms (SODA), as well as the Conference of the Association for the Advancement of Artificial Intelligence (AAAI), the International Joint Conference on Artificial Intelligence (IJCAI), and the International Conference on Web and Internet Economics (WINE). His work has also appeared in journal such as the SIAM Journal on Computing, INFORMS journals such as Operations Research and Mathematics of Operations Research, and the journal on Games and Economic Behavior.
Prior to joining Drexel's faculty in 2016, Gkatzelis served as a postdoctoral scholar at the University of California and at Stanford University. His professional experience includes working for Microsoft Research, HP Labs, and Google. Gkatzelis earned a PhD in computer science from Courant Institute of New York University.
Full Abstract:
One of the goals that lie at the core of computer science, as well as operations research and economics, is the effective utilization of scarce resources. For example, operating systems are designed to effectively utilize a computer's memory and processing units, and network protocols are designed to effectively utilize a networks' bandwidth. More broadly, a large fraction of the long literature on algorithm design and optimization is motivated by resource-allocation problems that arise in a wide variety of domains, ranging from project management and business administration to government policy and market design. Achieving effective resource-allocation outcomes is particularly challenging in multiagent systems, where a set of self-interested agents compete for shared resources. For example, in large computer networks there are multiple users that compete for the network's shared computational resources, such as its bandwidth, or access to its servers. Each agent's goal is to maximize its own utility, and the goal of the designer is to achieve system-level efficiency despite the agents' competing preferences. Without carefully designed resource-allocation mechanisms, the available resources would be underutilized, and massive amounts of social utility would be wasted; thus, it is imperative that these mechanisms are designed to the highest standard. The focus of this project is on the design of multiagent resource-allocation mechanisms that take into consideration the preferences of the participating agents and seek to maximize fairness and efficiency in the resulting outcomes.
To address the competing incentives of the participating agents, the field of mechanism design in economics has provided very useful tools. By far the most effective among them is the use of monetary payments: charging for the use of the resources can ensure that only the agents who need them the most would be interested in paying the price. However, the use of monetary payments is often undesired or even infeasible, e.g., due ethical, legal, or practical considerations, so the mechanism needs to eschew monetary transfers. Nevertheless, the vast majority of the literature on mechanism design has focused on the use of monetary payments, so money-free mechanisms are not well-understood. This project considers canonical domains of mechanism design without money from the perspective of the designer, with the goal of developing a coherent theory regarding what can and cannot be achieved in the absence of money. As a substitute for monetary payments, money-free mechanisms can instead penalize the agents by intentionally keeping some of the resources unallocated (a tool known as "money-burning"). This way, the improved incentives come at a cost in social utility, introducing novel trade-offs for the designer who needs to strike a balance between incentives and effectiveness. The main questions that this project focuses on are: 1) What incentives can the mechanism provide to the participants in the absence of money, and what cost in social utility do these improved incentives require? 2) From an algorithmic perspective what are the best worst-case approximation guarantees that can be achieved given the computational and informational constraints that these mechanisms may face?
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.