Two courses on matching and market design in Stanford's MS&E department, by Ashlagi and Saberi (first meeting is today)

Itai Ashlagi and  Amin Saberi are offering courses on matching theory and market design this quarter. First meetings are today, in the morning and in the afternoon:

MS&E 230: Market design for engineers

Itai Ashlagi  T-Thu 9:45-11:15

Course description:  Marketplaces use algorithms and sets of rules in order to allocate resources among self-interested agents, who often hold necessary information. This course will provide key principles in engineering a marketplace, to identify relation between the rules in the marketplace and market failures, and how to redesign them to achieve desirable outcomes.  The course provides foundations of resource allocation systems building on game theoretic analysis.  The course explores economic and algorithmic tools from matching, mechanism design, auction theory and information design. Cases of existing and future marketplaces will be discussed, including ride-sharing systems, school choice programs, online dating, online advertising and organ allocation.

Some applied questions include: How should we assign students to schools? How should we match doctors to residency programs? Shall we price roads and the impact of tolls? How should we allocate affordable housing and arrange waiting lists? How should we incentivize hospitals to collaborate on kidney exchanges? How should we allocate food to food banks? How should reduce organ discards?  How can we assist in migration?  Why is some marketplace decentralized (college admissions) and others are more controlled? How should platforms set incentives? What incentives and frictions arise in blockchains? 

 **********

MS&E 319: Matching Theory
Amin Saberi  T Th 01:30p-03:00p

The theory of matching with its roots in the work of mathematical giants like Euler and Kirchhoff has played a central and catalytic role in combinatorial optimization for decades. More recently, the growth of online marketplaces for allocating advertisements, rides, or other goods and services has led to new interest and progress in this area.  

The course starts with classic results characterizing matchings in bipartite and general graphs and explores connections with algebraic graph theory and discrete probability. Those results are complemented with models and algorithms developed for modern applications in market design, online advertising, and ride-sharing.

Topics include: 

Matching, determinant, and Pfaffian
Matching and polynomial identity testing
Isolating lemma and matrix inversion, matching in RNC

Combinatorial and polyhedral characterizations 
The assignment problem and its dual, primal-dual, and auction algorithms
Tutte’s theorem, Edmond’s LP, and the Blossom algorithm

The Gallai-Edmonds decomposition, Berge-Tutte formula, and applications in Nash bargaining

The stable marriage problem
Gale-Shapley theorem, incentive and fairness issues
LP characterization, counting stable matchings

Matching in dynamic environments
Online matching under various arrival models
Applications in ride-sharing and online advertising

 

Computation of matching  

Combinatorial vs continuous algorithms, near-linear time algorithms

Matchings in sub-linear time, streaming computational models

Sparsifiers and stochastic matching 

Counting matchings  
The Van der Waerden conjecture, Bregman-Minc’s inequality
Deterministic approximations, counting matchings in planar graphs
Markov chain Monte Carlo algorithms, sequential importance sampling
The Ising model, applications, and basic properties

***********

 

 

Stanford celebrates Itai Ashlagi and the UAE-Israel kidney exchange

Here's a Stanford story celebrating Itai Ashlagi's role in this summer's UAE-Israel kidney exchange. (His matching software is embedded in the software suite of the Alliance for Paired Kidney Exchange (AKPD) which is a partner with a remarkable Abu Dhabi effort to further kidney exchange.)

Stanford engineers develop algorithm to aid kidney transplant exchanges. A historic and complex kidney exchange between Israel and Abu Dhabi put a spotlight on the Stanford algorithm that made it all possible. BY ANDREW MYERS.  AUGUST 12, 2021

"A historic kidney transplant exchange recently took place in the Middle East, but it might never have transpired without an algorithm developed at Stanford by Itai Ashlagi, a Stanford associate professor of management science and engineering, and his graduate student Sukolsak Sakshuwong. In all, three ailing recipients received life-sustaining transplants while three healthy donors gave kidneys.

...

"“One of the nice things in the software we developed is the user interface. We collect all the relevant patient data, but then we let the user play with the various thresholds that determine successful matches to see what works for them,” Ashlagi said as he explained the team’s game-like approach to matching. The software acts as a platform and allows different organizations to easily collaborate and create more possibilities for exchanges. “Just a few days ago, I was looking for matches and found an unexpected exchange between pairs from Israel and other European countries. Hopefully, this will lead to new collaborations.”

“Itai’s software was used on both sides of that historic exchange between Abu Dhabi and Israel,” said Alvin Roth, Nobel Laureate and Ashlagi’s mentor and frequent collaborator, who was in Abu Dhabi in connection with the exchange.

"Roth says Ashlagi exemplifies the concept of scientist-engineer and is now a driving force in contemporary kidney exchange through both his deep understanding of the immunological issues of matching kidneys to patients and his intimate appreciation of the needs of transplant centers.

“He’s turned those practical theoretical insights into widely deployed digital tools with the power to change lives,” Roth added. “Having the chance to collaborate with him has been among the best experiences of my intellectual career.”

Kidney exchange in Israel using Itai Ashlagi's software

My colleague Itai Ashlagi has been inventing, building, distributing and updating state of the art kidney exchange software ever since he came to Harvard, some years ago. Since then he's been at MIT, and now Stanford, but this recent article from the Jewish Telegraphic Agency about how his software is propagating in Israel still thinks he's at Harvard:

New program finds donors for complicated kidney transplant patients

"JERUSALEM (JTA) — Kidney transplant patients who have had a hard time finding a match will have another opportunity through a new unit at an Israeli hospital.

"Kidney transplant patients who suffer from high levels of antibodies due to previous transplants or blood donations can go for many years without finding a suitable donor. A new and advanced software program can be used to cross-check through advanced information systems from hospitals in Israel and around the world.

"The program, developed by Professor Itai Ashlagi of Harvard University, was donated to the Matnat Chaim organization and will be operated out of Beilinson Hospital’s Department of Transplantation in Petach Tikvah, in central Israel."

Stanford Engineering celebrates Itai Ashlagi

Faculty Spotlight: Itai Ashlagi
Itai Ashlagi joined the MS&E faculty in 2015 to continue his intensive study of market design.

"He specializes in matching markets, such as kidney exchange programs, organ allocation, school choice, and the National Resident Matching Program.

"I can't think of a better intellectual environment for my research than MS&E, where the faculty and students share a common goal of designing systems and policies that impact our lives."