Mayesha Tasnim

One-sided matching algorithms decide who gets access to scarce public resources, from secondary school seats to social housing to refugee placements. The standard design problem is framed as a trade-off between two desirable properties: matching efficiency, which is whether people are assigned to items they actually prefer, and strategyproofness, which is whether they have any reason to misrepresent their preferences. The classical result is that no mechanism can have both. Policymakers must therefore choose, and either choice comes with a cost: strategyproof mechanisms produce inefficient matches with long tails of unfavorable assignments, while more efficient mechanisms create opportunities for strategic manipulation that may be distributed unequally across participants. This thesis investigates how one-sided matching systems should be evaluated and designed when attempts to improve allocations create new incentives for strategic misreporting of preferences. In Chapter 2, we investigate strategic reporting in the rank minimization mechanism, a welfare-oriented alternative to Random Serial Dictatorship that achieves better rank distributions but is not strategyproof. We derive a best-response strategy for participants seeking to be matched to their top preferred items and extend it to a first-order heuristic strategy that requires only knowledge of which items are popular as first choices. Using both synthetic markets and real preference data from secondary school choice in Amsterdam, we show that the strategy is easy to apply and creates a clear individual incentive to misreport, exposing a distributional gap between those who can act on it and those who cannot. In Chapter 3, we expand the analysis from manipulable mechanisms to strategyproof mechanisms embedded in broader institutional settings. We study the Amsterdam placement guarantee, a policy modification layered on top of Random Serial Dictatorship that promises placement to students who submit a sufficiently long preference list. We characterize a simple reporting strategy for students with fewer sincere preferences than the required list length, and show through simulation that as this behavior spreads, the number of guarantee-eligible students can exceed the additional capacity the policy creates, rendering the guarantee infeasible. We use this case to articulate a promise gap in public algorithmic systems: a mismatch between what an implemented system publicly assures and what it can sustain once participants adapt to it. With Chapter 4, the focus shifts from formal incentives to behavioral response. We conduct a behavioral experiment embedded in a survey of 140 parents participating in Amsterdam’s 2025 school choice process, and model their decisions using Security-Potential/Aspiration theory. We find that transparency about strategic risk acts as a deterrent rather than an enabler of manipulation, and that parents in the more competitive academic tracks are more risk-averse rather than more strategic. These findings reverse common assumptions in the school choice literature and suggest that the trade-off between efficiency and manipulability may be less sharp in practice than formal analyses imply. While the previous chapters take the design space of matching mechanisms as given, Chapter 5 asks whether learning-based methods can reach intermediate positions that classical mechanisms cannot. We formulate one-sided matching as a sequential decision problem on a bipartite graph and train two learned policies, one based on Generative Flow Networks and one on Deep Q-Networks. Because learned policies admit no analytical strategyproofness guarantees, we develop a framework for empirical robustness evaluation built around four misreporting strategies and a population-level adoption experiment. We find that truthful efficiency is not a reliable indicator of robustness, that individual incentive to misreport does not predict population-level outcomes, and that learned policies remain stable under population-level strategic adoption where classical methods deteriorate. Finally, Chapter 6 reflects on what this body of work implies for AI research in civic contexts. We propose a framework for civic AI research organized around three dimensions: between science and society, between fundamental and applied work, and between quantitative and qualitative methods, with the human at the intersection of all three. Drawing on the Amsterdam school choice case, we argue that civic engagement is what makes interdisciplinarity practically possible, rather than the other way around. This thesis brings formal, behavioral, and computational perspectives to one-sided matching. Our contributions show that algorithmic allocation systems shape outcomes, incentives, administrative burdens, and institutional trust at the same time, and that responsible evaluation of such systems cannot stop at the formal properties of the underlying algorithm but must also examine how participants respond to it and how the design space itself can be widened.