Vi anser att problemet med en rättvis fördelning av odelbara varor, mellan agenter, under kardinalitetsbegränsningar och additiva värderingar. I denna inställning, vi ges en uppdelning av hela uppsättningen varor-dvs., varorna kategoriseras-och en gräns anges på antalet varor som kan fördelas från varje kategori till alla agenter. Målet här är att hitta en rättvis fördelning där den delmängd av varor som tilldelats en agent uppfyller de givna kardinalitetsbegränsningarna. Detta problem fångar naturligtvis upp ett antal resursfördelningstillämpningar, och är en generalisering av det välstuderade (okonstruerade) problemet med rättvis uppdelning. De två centrala begreppen rättvisa, i samband med rättvis fördelning av odelbara varor, är avund upp till en god (EF1) och (ungefär) maximal aktiegaranti (MMS). Vi visar att existensen och algoritmiska garantier som fastställts för dessa lösningskoncept i den okonstruerade miljön i huvudsak kan uppnås under kardinalitetsbegränsningar. Specifikt utvecklar vi effektiva algoritmer som beräknar EF1 och cirka MMS-tilldelningar i den begränsade inställningen. Dessutom, med fokus på det fall där alla agenter har samma additiva värdering, fastställer vi att EF1 tilldelningar finns och kan beräknas effektivt även under matris begränsningar.
Nyligen undersökte REF kardinalitetsbegränsningarna för enskilda rättvisa uppdelningar, där varorna kategoriseras och det finns en begränsning av antalet varor från varje kategori som kan tilldelas varje agent.
Fair Division Under Cardinality Constraints
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}