Jabari Hastings (Computer Science) | Optimization in Bipartite Assignment Problems (University of Bonn)

My name is Jabari Hastings, and I am a fifth-year PhD student in the Computer Science department at Stanford. One of the primary goals of my research is to design provably efficient, equitable algorithms for assignment problems. Matching is one of the most fundamental assignment problems and underpins a wide array of resource allocation scenarios. Just within education, centralized systems match students to schools, dorms, and courses; faculty and TAs to teaching assignments; and courses to classrooms. This past summer, I had the incredible opportunity to collaborate with Prof. Thomas Kesselheim and researchers at the University of Bonn, as part of the Graduate Research and Internship Program (GRIP) in Germany. Our work focused on optimizing objectives that prioritize the outcomes of the worst-off participants in matching settings.

There are two natural ways to model the matching problem. In the first, participants express their values in terms of utilities, where higher values are better. Here, our goal is typically to maximize some function of these utilities, such as the total welfare (the sum) or, in the spirit of fairness, the smallest utility assigned to any participant (the max-min solution). In the second setting, participants express costs, such as the distance one has to travel to a school. In this case, the objective is to minimize some function of these costs, like the maximum cost incurred by any individual. I believe that we can, and should, look beyond the traditional objectives in both optimization paradigms. In particular, we can consider a significantly larger class of functions that can convey more nuanced concerns about the participants in a mechanism (e.g., the bottom 10% of individuals, the average utility of the middle 50%, or even a sliding scale of concern for the worst-off).

I was drawn to collaborate with Prof. Thomas Kesselheim because his research focuses on optimizing precisely the kinds of general objectives I find appealing. As objectives become increasingly general, finding perfect solutions often becomes computationally intractable. Prof. Kesselheim's work designs approximation algorithms to sidestep this intractability. Our collaboration focused on mapping out the realm of possibility in the matching setting—determining which objectives can be solved exactly and which require efficient, provable approximations. We discovered that it is indeed possible to attain a modest approximation in the minimization setting of our problem by applying a powerful framework. Our approach appears to hold for a simple yet foundational function in our target class, and our ongoing work is focused on determining whether we can generalize this result to the entire class and apply our insights to the maximization setting.

Beyond this main project, I also started a new collaboration with a PhD student at the university, based on a talk I gave at one of their research seminars. My talk focused on my previous work on designing algorithms in the presence of incomplete information. In many real-world settings, individuals cannot provide precise utilities or costs; instead, they may only provide simple rankings (e.g., "I prefer item A to item B"). This leads to a central challenge: how do we make good assignments based on this limited information? We measure our success using the concept of metric distortion, which, at a high level, describes how much more costly a proposed assignment is when compared to the optimal assignment we could have made if we had access to perfect information.

My talk, which highlighted that distortion is often high (polynomial) in general settings, sparked a new project to explore a promising new direction. Our goal is to consider whether a vastly better—that is, a constant—distortion can be achieved when we assume preferences have a simpler and more natural structure. One way to obtain such structure is by imagining that individuals and items are points in a simple metric space, such as on a line (akin to a political spectrum, where nearby points are assumed to have similar tastes). We have some promising preliminary work suggesting this could be possible, and we are actively working on extending this result.

My productive research experience was just one highlight of my time in Germany. Having only visited once before—a brief, week-long stay in Berlin three years prior—I never expected to return so soon or to truly experience the country. I am so glad I took the time to explore. I traveled from the bustling port city of Hamburg to the enchanting old town of Rothenburg ob der Tauber, and even experienced the sheer beauty of the Black Forest region while visiting another GRIP participant (Ariel Hannum) in Freiburg im Breisgsau. But as memorable as all those scenic adventures were, the place that resonated with me most, perhaps surprisingly, was Cologne. While it may not have the fairy-tale charm of other towns, it was in Cologne that I met incredibly warm, kind, and open people in the local swing dance community. I will always cherish the many evenings we spent dancing, eating, and sharing profound conversations about our lived experiences.

This combination of research and cultural immersion made my GRIP experience in Germany invaluable. It has not only pushed my research forward but also given me a deep, personal appreciation for the country and its people.