Conceptual
Browse Instruct Curate
Login

Price of Cardinality in Fair Division of Indivisible Goods

The price of cardinality measures the worst-case multiplicative loss of social welfare when an allocation of indivisible goods must give each agent at most k items, a constraint generalizing balanced allocations. For utilitarian welfare (sum of utilities) the price is (1/2)(1 + sqrt(1 + (m-1)/k)) with m items, and for egalitarian welfare (worst-off agent) it is exactly max{(m-n+1)/k, 1}; both extend to items partitioned into categories with per-category limits, giving decision makers exact tradeoffs between balancedness and welfare.