Abstrakt. Vi studerar problemet med att matcha sökande till jobb enligt ensidiga preferenser, det vill säga varje sökande rankar en icke-tom del av jobb enligt en ordning av preferenser, eventuellt med band. En matchande M sägs vara mer populär än T om de sökande som föredrar M att T överträffar dem som föredrar T till M. En matchning sägs vara populär om det inte finns någon matchning mer populär än det. Likvärdigt är en matchande M populär om.(M, T ) ≥.(T, M ) för alla matchningar T, där  ska (X, Y ) är antalet sökande som föredrar X till Y. Tidigare studerade lösningskoncept baserade på popularitetskriteriet är antingen inte garanterade att existera för varje instans (t.ex. populära matchningar) eller är NP-hårda att beräkna (t.ex. minst impopulära matchningar). I detta dokument behandlas denna fråga genom att man överväger blandade matchningar. En blandad matchning är helt enkelt en sannolikhetsfördelning över matchningar i inmatningsdiagrammet. Den funktion som jämför två matchningar generaliseras på ett naturligt sätt till blandade matchningar genom att ta förväntningar. En blandad matchande P är populär om P, Q) ≥ Q, P ) för alla blandade matchningar Q. Vi visar att populära blandade matchningar alltid finns och vi designar polynom tid algoritmer för att hitta dem. Sedan studerar vi deras effektivitet och ger snäva gränser för priset på anarki och priset på stabilitet i det populära matchningsproblemet.
Kavitha m.fl. REF introducerade begreppet blandad matchning, vilket är en sannolikhetsfördelning över matchningar, och visade att en blandad matchning som är populär alltid finns.
Popular Mixed Matchings
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}