AF: SMALL : Algorithmic and Game Theoretic Problems Arising in Modern Matching Markets

University Of Washington, Seattle WA

Investigators

Abstract

Modern matching markets include healthcare markets, energy markets, online marketplaces, markets associated with the sharing/gig economy, markets for matching schools/universities with students, cloud computing markets, online advertising markets, etc. This project will consist of designing and analyzing new pricing mechanisms and matching algorithms with the objective of greatly increasing the effectiveness and efficiency of such marketplaces. Significant online resources will be developed to showcase training advice and insight for a diverse workforce that the Computing Research Association's Committee on the Status of Women in Computing has been providing for several years in its in-person workshops. These resources will address issues such as networking, communication skills, choosing between academia and industry, leadership skills, negotiating, etc. Developing these online resources will ensure that this mentoring will reach more students and especially members of underrepresented groups, thereby increasing their success and participation in computing research and education at all levels. Maximum weight matching is a cornerstone problem in combinatorial optimization. It is a showcase for algorithmic gems and beautiful algorithmic techniques, and, most importantly, is of immense practical importance, with new applications and important variants arising every day. The primary objective of the project is to solve algorithmic and game-theoretic problems motivated by modern matching markets. The matching problems that arise in these settings require handling strategic agents, designing new mechanisms, making pricing decisions, deciding what and how much information to disseminate to the participating agents, solving online problems, and analyzing complex dynamics and queueing. 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.