Stabil matchande polytop

Inom matematik , ekonomi och datavetenskap är den stabila matchande polytopen eller den stabila äktenskapspolytopen en konvex polytop som härrör från lösningarna på en instans av det stabila matchningsproblemet .

Beskrivning

Den stabila matchande polytopen är det konvexa skrovet för indikatorvektorerna för de stabila matchningarna för det givna problemet. Den har en dimension för varje par av element som kan matchas, och en vertex för varje stabil matchning. För varje vertex är de kartesiska koordinaterna en för par som matchas i motsvarande matchning och noll för par som inte matchas.

Den stabila matchande polytopen har ett polynomantal av fasetter . Dessa inkluderar de konventionella ojämlikheterna som beskriver matchningar utan krav på stabilitet (varje koordinat måste vara mellan 0 och 1, och för att varje element ska matchas måste summan av koordinater för paren som involverar det elementet vara exakt ett), tillsammans med olikheter som begränsar resulterande matchning för att vara stabil (för varje potentiellt matchat parelement måste summan av koordinater för matchningar som är minst lika bra för ett av de två elementen vara minst ett). Punkterna som tillfredsställer alla dessa begränsningar kan ses som fraktionella lösningar av en linjär programmeringsrelaxation av det stabila matchningsproblemet.

Integritet

Det är en sats av Vande Vate (1989) att polytopen som beskrivs av facettbegränsningarna som anges ovan endast har de hörn som beskrivs ovan. I synnerhet är det en integrerad polytop . Detta kan ses som en analog till Garrett Birkhoffs teorem att en analog polytop, Birkhoff-polytopen som beskriver mängden av alla bråkmatchningar mellan två uppsättningar, är integral.

Ett ekvivalent sätt att ange samma sats är att varje bråkmatchning kan uttryckas som en konvex kombination av integralmatchningar. Teo & Sethuraman (1998) bevisar detta genom att konstruera en sannolikhetsfördelning på integralmatchningar vars förväntade värde kan sättas lika med varje given bråkmatchning. För att göra det utför de följande steg:

Betrakta för varje element på ena sidan av det stabila matchningsproblemet (läkarna, t.ex. i ett problem som matchar läkare med sjukhus) de bråkvärden som tilldelats parningar med elementen på den andra sidan (sjukhusen), och sortera dessa värden i minskande ordning enligt den läkarens preferenser.
Dela upp enhetsintervallet i delintervall, med längder lika med dessa bråkvärden, i sorterad ordning. Att välja ett slumptal i enhetsintervallet kommer att ge en slumpmässig matchning för den valda läkaren, med sannolikhet lika med bråkvikten för den matchningen.
Symmetriskt, överväg för varje element på andra sidan av den stabila matchningen (sjukhusen), sortera bråkvärdena för parningar som involverar det elementet i ökande ordning efter preferens, och konstruera en partition av enhetsintervallet vars delintervall har dessa bråkvärden i sorterad ordning.
Det kan bevisas att för varje matchat par är delintervallen associerade med det paret desamma i både partitionen för läkaren och partitionen för sjukhuset i det paret. Att välja ett enstaka slumptal i enhetsintervallet och använda det valet för att samtidigt välja ett sjukhus för varje läkare och en läkare för varje sjukhus ger därför en matchning. Dessutom kan denna matchning visas vara stabil.

Den resulterande slumpmässigt valda stabila matchningen väljer vilket speciellt matchat par som helst med sannolikhet lika med bråkkoordinatvärdet för det paret. Därför sannolikhetsfördelningen över stabila matchningar konstruerade på detta sätt en representation av den givna bråkmatchningen som en konvex kombination av integral stabila matchningar.

Gitter av bråkmatchningar

Familjen av alla stabila matchningar bildar ett distributivt gitter , gittret av stabila matchningar , där sammanfogningen av två matchningar ger alla läkare deras preferens bland deras tilldelade sjukhus i de två matchningarna, och mötet ger alla sjukhus deras preferenser. Detsamma gäller familjen av alla fraktionerade stabila matchningar, punkterna för den stabila matchande polytopen.

I den stabila matchande polytopen kan man definiera en matchning för att dominera en annan om, för varje läkare och sjukhus, det totala bråkvärde som tilldelas matchningar för den läkaren som är minst lika bra (för läkaren) som det sjukhuset är minst lika stor i den första matchningen som i den andra. Detta definierar en partiell ordning på bråkmatchningarna. Denna delorder har ett unikt största element, den stabila heltalsmatchningen som hittas av en version av Gale–Shapley-algoritmen där läkarna föreslår matchningar och sjukhusen svarar på förslagen. Den har också ett unikt minsta element, den stabila heltalsmatchningen som hittas av en version av Gale–Shapley-algoritmen där sjukhusen lägger fram förslagen.

I enlighet med denna partiella ordning kan man definiera mötet av två bråkmatchningar som en bråkmatchning som är så låg som möjligt i den partiella ordningen samtidigt som den dominerar de två matchningarna. För varje läkare och sjukhus tilldelar den det potentiella matchade paret en vikt som gör att den totala vikten för det paret och alla bättre par för samma läkare är lika med den största av motsvarande totalsummor från de två givna matchningarna. Sammanfogningen definieras symmetriskt.

Ansökningar

Genom att tillämpa linjär programmering på den stabila matchande polytopen kan man hitta den minsta eller maximala viktstabila matchningen. Alternativa metoder för samma problem inkluderar att applicera stängningsproblemet på en partiellt ordnad uppsättning härledd från gittret av stabila matchningar, eller att tillämpa linjär programmering på ordningspolytopen av denna delordning.

Förhållande till beställningspolytop

Egenskapen hos den stabila matchande polytopen, att definiera ett kontinuerligt fördelningsgitter, är analog med den definierande egenskapen hos en distributiv polytop , en polytop i vilken koordinatvis maximering och minimering bildar mötes- och sammanfogningsoperationerna för ett gitter. Mötes- och sammanfogningsoperationerna för den stabila matchande polytopen definieras dock på ett annat sätt än koordinatmässig maximering och minimering. Istället ordningspolytopen för den underliggande partiella ordningen av gittret av stabila matchningar en fördelningspolytop som är associerad med uppsättningen av stabila matchningar, men en för vilken det är svårare att avläsa bråkvärdet associerat med varje matchat par. Faktum är att den stabila matchande polytopen och ordningspolytopen för den underliggande partiella ordningen är mycket nära besläktade med varandra: var och en är en affin transformation av den andra.