Den klassiska kaka skär problemet ger en modell för att ta itu med rättvis och effektiv fördelning av en delbar, heterogen resurs (metaforiskt, kakan) bland agenter med tydliga preferenser. Med fokus på en standardformulering av kakskärning, där varje agent måste få en sammanhängande bit av kakan, etablerar detta arbete algoritmiska och hårdhet resultat för flera rättvisa / effektivitet åtgärder. För det första anser vi att den välstuderade uppfattningen om avundsfrihet och utveckla en effektiv algoritm som finner en kaka division (med anslutna bitar) där avund är multiplikativt inom en faktor av 3. Samma algoritm uppnår i själva verket en approximation förhållandet 3 för problemet med att hitta kaka divisioner med så stor en Nash social välfärd (NSW) som möjligt. NSW är ett annat standardmått på rättvisa och detta arbete etablerar också en koppling mellan avund-frihet och NSW: ungefär avund-fri kaka divisioner (med anslutna bitar) har alltid nära-optimal Nash social välfärd. Dessutom utvecklar vi en approximationsalgoritm för att maximera det ρ-mean välfärd-detta enande mål, med olika värden av ρ, interpolerar mellan begreppen rättvisa (NSW) och effektivitet (genomsnittlig social välfärd). Slutligen kompletterar vi dessa algoritmiska resultat genom att bevisa att maximering NSW (och i allmänhet ρ-mean välfärd) är APX-hård i kak-division sammanhang.
Nyligen, REF utvecklat en effektiv algoritm som beräknar en sammanhängande kaka division med multiplikativt avgränsad avund-i synnerhet, varje agents avund begränsas av en multiplikativ faktor 3.
Fair and Efficient Cake Division with Connected Pieces
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}