Målet med rättvis fördelning är att fördela resurser mellan konkurrerande aktörer på ett "rättvist" sätt. Avund-frihet är den mest studerade rättvisebegreppet i rättvis uppdelning. Avundslösa tilldelningar finns inte alltid med odelbara varor, vilket motiverar studiet av avslappnade versioner av avundsfrihet. Vi studerar avundsjuka-frihet upp till någon bra (EFX) egendom, som säger att ingen spelare föredrar bunten av en annan spelare efter avlägsnandet av någon enskild god, och bevisa de första allmänna resultaten om denna egendom. Vi använder oss av leximinlösningen för att visa förekomsten av EFX-tilldelningar i flera sammanhang, ibland tillsammans med Pareto optimalitet. För två spelare med värderingar som följer ett milt antagande, ger en av dessa resultat starkare garantier än den nuvarande algoritmen på Spliddit, en populär rättvis division webbplats. Tyvärr kan det kräva exponentiellt lång tid att hitta leximinlösningen. Vi visar att detta är nödvändigt genom att bevisa en exponentiell lägre gräns för antalet värdefrågor som behövs för att identifiera en EFX tilldelning, även för två spelare med identiska värderingar. Vi anser både additiva och mer generella värderingar, och vårt arbete tyder på att det finns ett rikt landskap av problem att utforska i den rättvisa uppdelningen av odelbara varor med olika klasser av spelarvärderingar.
Plaut och Roughgarden REF bevisar förekomsten av EFX tilldelningar för att ställa med två agenter endast eller med fler agenter och identiska värderingar.
Almost Envy-Freeness with General Valuations
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}