Avundsfri matchning
I ekonomi och sociala valteori är en avundsfri matchning (EFM) en matchning mellan människor till "saker", vilket är avundsfritt i den meningen att ingen person skulle vilja byta sin "grej" med en annan persons. Denna term har använts i flera olika sammanhang.
I ovägda tvådelade grafer
I en ovägd tvådelad graf G = ( X + Y , E ), är en avundsfri matchning en matchning där ingen omatchad vertex i X är intill en matchad vertex i Y . Anta att hörnen på X representerar människor, ytorna på Y representerar hus och en kant mellan en person x och ett hus y representerar det faktum att x är villig att bo i y . Sedan är en EFM en partiell tilldelning av hus till människor så att varje huslös person inte avundas någon person med ett hus, eftersom han/hon inte gillar något tilldelat hus ändå.
Varje matchning som mättar X är avundsfri, och varje tom matchning är avundsfri. Dessutom, om | NG ( X ) | ≥ |X| ≥ 1 (där N G ( X ) är uppsättningen av grannar till X i Y ), då medger G en icke-tom EFM. Detta är en uppmjukning av Halls äktenskapsvillkor , som säger att, om | N G ( X ')| ≥ |X'| för varje delmängd X ' av X existerar en X- mättande matchning.
På marknader med pengar
Tänk på en marknad där det finns flera köpare och flera varor, och varje vara kan ha ett pris. Med en prisvektor har varje köpare en efterfrågeuppsättning - en uppsättning paket som maximerar köparens användbarhet över alla paket (denna uppsättning kan inkludera den tomma bunten, om köparen anser att alla paket är för dyra).
En prisavundsfri matchning (med en prisvektor) är en matchning där varje agent får ett paket från sin efterfrågan. Det betyder att ingen agent skulle föredra att få ett annat paket med samma priser. Ett exempel på denna inställning är hyresharmoni - att matcha hyresgästerna (ombuden) till rummen (objekten) samtidigt som ett pris sätts till varje rum.
Ett avundsfritt pris är en prisvektor för vilken det finns en avundsfri matchning. Det är en avslappning av en Walrasian-jämvikt : en Walrasian-jämvikt består av ett EF-pris och EF-matchning, och dessutom måste varje artikel antingen matchas eller ha nollpris. Det är känt att i en Walrasian-jämvikt maximerar matchningen summan av värden, dvs det är en maximalviktsmatchning . Däremot kan säljarens intäkter vara låga. Detta motiverar en lättnad till EF-prissättning, där säljaren kan använda reservpriser för att öka intäkterna; se avundsfria priser för mer information.
På marknader utan pengar
Termen avundsfri matchning används ofta för att beteckna ett svagare tillstånd - ingen motiverad avundsmatchning .
I tårtskärning
Termen avundsfri matchning har också använts i ett annat sammanhang: en algoritm för att förbättra effektiviteten av avundsfri kakskärning .