Tvåvägsmatchning

Tvåvägsmatchning är ett problem inom spelteori och algoritmdesign där två uppsättningar av aktörer korresponderas med varandra utifrån deras preferenser eller nytta. Vanliga exempel är arbetsmarknaden där arbetssökande och arbetsgivare paras ihop, eller romantiska marknader där två kön eller två par bildar par. Målet är att hitta en stabil matchning som ger en rimlig avvägning mellan aktörernas önskemål.

En central begrepp i tvåvägsmatchning är stabilitet. En matchning är stabil om det inte finns några blocking pairs – par av aktörer som båda skulle föredra varandra framför sina nuvarande partners. Om ett sådant par existerar, kan de två aktörerna bli oense och vilja bryta sin nuvarande överenskommelse till förmån för varandra.

Den mest använda algoritmen för att hitta stabila matchningar är Deferred Acceptance (fördröjd acceptans). En sida (ofta den som får föga inflytande högre preferens) gör erbjudanden till motparten, som håller de bästa erbjudandena tillfälligt och avvisar resten. Processen upprepas tills alla par är slutgiltigt par. Denna metod producerar vanligtvis en man-optimal och kvinno-optimal stabil matchning beroende på vilken sida som föreslår först, och resultatet är alltid stabilt inom modellen.

Vanliga varianter inkluderar one-to-one och many-to-one-matching (till exempel sjukhus-resident- eller colleges-admissions), uppdelningar med kapacitet, oavklara listor och kopplade risker som pockets av strategiskt beteende. Marknadsdesign används ofta för resursfördelning i offentlig sektor och ekonomisk forskning, med tillämpningar som medicinska residensfördelningar, högre utbildning och organbyte.