Vi studerar problemet med att fördela en uppsättning odelbara varor mellan en uppsättning agenter på ett rättvist och effektivt sätt. En tilldelning sägs vara rättvis om den är avundsfri upp till en god (EF1), vilket innebär att varje agent föredrar sin egen bunt framför bunten av någon annan agent upp till avlägsnande av en god. Dessutom anses en tilldelning vara effektiv om den uppfyller Paretos effektivitet. Medan var och en av dessa välstuderade egenskaper är lätt att uppnå separat, är det långt ifrån självklart att uppnå dem tillsammans. Nyligen, Caragiannis et al. [11] fastställde det överraskande resultatet att när agenter har additiva värderingar för varorna, finns det alltid en tilldelning som samtidigt uppfyller dessa två till synes oförenliga egenskaper. De visade särskilt att en tilldelning som maximerar Nash sociala välfärdsmål är både EF1 och Pareto effektiv. Problemet med att maximera Nash sociala välfärd är dock NP-hård. Detta tillvägagångssätt ger därför inte någon effektiv algoritm för att finna en rättvis och effektiv fördelning. I detta dokument förbigår vi denna barriär, och utvecklar en pseudopolynom tid algoritm för att hitta tilldelningar som är EF1 och Pareto effektiva; i synnerhet, när värderingarna begränsas, vår algoritm finner en sådan tilldelning i polynom tid. Dessutom etablerar vi en starkare existens resultat jämfört med Caragiannis et al. [11] : För additiva värderingar finns det alltid en tilldelning som är EF1 och fraktionerat Pareto effektiv. Ett annat viktigt bidrag i vårt arbete är att visa att vår algoritm ger en polynom-tid 1,45-uppskattning till Nash sociala välfärdsmål. Detta förbättrar på den mest kända approximation förhållandet för detta problem (nämligen, 2- approximation algoritm Cole et al. [12] ), och matchar även den nedre gränsen på integrality gap av konvexa programmet Cole et al. [12]................................................................ Till skillnad från många av de befintliga tillvägagångssätten är vår algoritm helt kombinatorisk, och bygger på att bygga integrerade Fisher-marknader där specifika jämvikter inte bara är effektiva, utan också rättvisa.
Barman m.fl. REF erhöll en pseudopolynomalgoritm för att hitta en tilldelning som är både EF1 och Paretooptimal.
Finding Fair and Efficient Allocations
{'venue': "EC '18", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}