Psomas earns NSF CAREER award

07-20-2022

The Internet and the vast increase in the availability of data have transformed algorithm design, as well as computer science in general. From computational resources and advertising space, to food donations, loans, kidneys, and vaccines, algorithms are increasingly being used to decide how scarce resources are allocated. What is special about many of these modern applications is that the input to the algorithms must be solicited from strategic agents, with their own, private preferences over the algorithm’s output. 

Computer science assistant professor and theoretical researcher, Alex Psomas, received a CAREER award from the National Science Foundation (NSF) to address mechanism design without money. His project will expand the reach of theory into areas of algorithm design where there is a major gap in current understanding 

Psomas’ work is titled, “Incentives, Fairness, and Efficiency without Monetary Transfers.” His project takes aim at several key theoretical questions in three complementary areas; foundations of mechanism design without money, mechanism design with imperfect rationality, and mechanism design with imperfect expressivity.

From resource allocation in the cloud and spectrum auctions to tournaments in major sporting events, it is well-understood that real people will optimize their own benefit to the extent possible while still “following the rules,” leading to unpredictable final outcomes. And, unlike traditional optimization, in many of these modern applications, system designers must also consider whether their system is equitable among its participants. 

Classic work in economics, as well as extensive work in the intersection of computer science and economics, provides a rich toolkit for designing algorithms that are immune to strategic manipulations as well as algorithms that balance fairness and efficiency. 

Psomas’ project aims to advance and develop this theory with a focus on domains where monetary transfers are not allowed, by taking aim at several fundamental open questions. The project also contains plans to design, develop, and deploy a system that is based on the proposed theoretical research and that serves the local community by enabling local non-profit organizations that fight hunger to allocate their food donations in a more efficient manner.

The project has three complementary thrusts. 

(1) Foundations of mechanism design without money. The project takes aim at fundamental questions in this space, with the goal of developing tools for designing truthful mechanisms for a number of paradigms: divisible and indivisible goods, static and dynamic environments, worst-case and Bayesian objectives. 

(2) Mechanism design with imperfect rationality. There are important domains in which protecting against fully rational, expected utility-maximizing participants is overly cautious. This project puts forward and explores several possibilities for modeling imperfect rationality. 

(3) Mechanism design with imperfect expressivity. Eliciting complex utility functions is often infeasible, e.g., because of agents' cognitive limitations. The project explores the trade-off between expressiveness and ease of elicitation in mechanism design without money.

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.

 

NSF CAREER awards are the organization’s most prestigious awards given to junior faculty who embody the role of teacher-scholars through research, education and the integration of those concepts within the mission of their organizations. CAREER awards support promising and talented researchers in building a foundation for a lifetime of leadership. Receiving this award reflects this project’s merit of the NSF statutory mission and its worthiness of financial support.

 

Alexandros Psomas is a theoretical computer scientist and assistant professor in the Department of Computer Science at Purdue University. His research focuses on the intersection of computer science and economics. Using the application of tools and insights from computer science, he studies problems in a variety of economic environments. His research interest lies in algorithmic economics, artificial intelligence, computational social choice and mechanism design, machine learning, and algorithmic game theory. Psomas earned his PhD in computer science 2017 from the University of California, Berkeley with the Theory of Computation group, advised by Professor Christos Papadimitriou. Previously, he was a visiting researcher with Google Research and Research Fellow at the Simons Institute for the Theory of Computing and a postdoctoral researcher in the Computer Science Department at Carnegie Mellon University, 

 

About the Department of Computer Science at Purdue University

Founded in 1962, the Department of Computer Science was created to be an innovative base of knowledge in the emerging field of computing as the first degree-awarding program in the United States. The department continues to advance the computer science industry through research. US News & Reports ranks Purdue CS #20 and #18 overall in graduate and undergraduate programs respectively, ninth in both software engineering and cybersecurity, 14th in programming languages, 17th in computing systems, and 24th in artificial intelligence. Graduates of the program are able to solve complex and challenging problems in many fields. Our consistent success in an ever-changing landscape is reflected in the record undergraduate enrollment, increased faculty hiring, innovative research projects, and the creation of new academic programs. The increasing centrality of computer science in academic disciplines and society, and new research activities - centered around data science, artificial intelligence, programming languages, theoretical computer science, machine learning, and cybersecurity - are the future focus of the department. cs.purdue.edu