Vijay Vazirani
University of California-Irvine, CA·Computer Science
Many markets do not set prices. Instead, they match people and resources: medical interns to hospitals, students to schools, kidney patients to compatible donors.
- Fields
Computer Science
Mathematics & Statistics
Social Science
- Topics
market design
online algorithms
online bipartite matching
- Grants
- 1 known grant, last ended Sep 2026
What they work on
- Design algorithms for online hypergraph matching, where each match can involve more than two parties, and its generalizations, building on the simple proof of the RANKING algorithm, with applications to ride-sharing and network revenue management.
- Extend RANKING to the adwords problem, which assigns search queries to advertisers with budgets, under small bids, to obtain a budget-oblivious algorithm suited to autobidding platforms.
- Prove high-probability performance guarantees for online matching algorithms that have so far been analyzed only in expectation, that is, on average.
- Develop efficient implementations of Nash-bargaining-based mechanisms for matching markets with cardinal utilities, as a tractable replacement for the Hylland–Zeckhauser mechanism.
More about the research
This field of market design began with the Gale–Shapley stable matching algorithm in 1962. The internet and mobile computing then created a second wave of online matching problems, in which decisions must be made as requests arrive. Examples include search engines matching user queries to advertisers, ride-sharing apps matching drivers to riders, and platforms matching employers to workers. The guiding algorithm of this second wave is RANKING, an optimal method for online bipartite matching (pairing two groups as items arrive one at a time) that the investigator co-introduced in 1990. A recent simple proof of RANKING opens new problems, and this project studies four of them.
Why it matters
Matching algorithms already run real systems: residency matching, school choice, kidney exchange, search advertising and ride-sharing. Better online matching algorithms and workable mechanisms for markets with cardinal preferences could improve how platforms allocate rides, ads and jobs. They could also give market designers fair allocation tools that can actually be computed.
Known grants
From NIH and NSF research grants. Labs often have other funding we can't see.
Closest labs
Christian Kroer
Columbia University, NY·Computer Science·Early-career
Develop algorithms for online fair allocation and dynamic markets using online learning and first-order optimization methods, aiming for robustness across different input models rather than a single assumed arrival process.
Hadi Hosseini
Pennsylvania State University, PA·Computer Science·Early-career
Design matching and allocation algorithms that remain fair when participants' preferences are uncertain or noisy, rather than assuming preferences are reported exactly.
Simina Branzei
Purdue University, IN·Computer Science·Early-career
Analyze market dynamics in which computationally limited players with only local information interact over time, testing whether globally efficient allocations emerge and whether markets grow or shrink.
The school
University of California-Irvine: 46 labs on PI Pages, $645M a year on research, 524 research doctorates a year.
Reach out
A start for your email. Fill in the brackets.