Research map / Learning theory and algorithms / Submodular and game algorithms
The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the price of cardinality, a parametric worst-case welfare loss measure for cardinality-constrained allocations of indivisible goods, and gives exact or near-exact bounds for utilitarian and egalitarian welfare in single- and multi-category settings.
Problem
Quantifying the worst-case multiplicative loss in utilitarian or egalitarian social welfare when each agent can receive at most k indivisible items (cardinality constraint, possibly per category), as an exact function of instance parameters rather than an asymptotic bound.
Approach
Defines the price of cardinality and derives exact expressions as functions of m, k (and per-category m_j, k_j) instead of asymptotic bounds; for utilitarian welfare the single-category bound is (1/2)(1+sqrt(1+(m-1)/k)), refining the Theta(sqrt(n)) price of balancedness, using a preprocessing reduction and a greedy reassignment procedure.
Key results
- Single-category utilitarian price of cardinality is exactly (1/2)(1+sqrt(1+(m-1)/k)) (tight up to additive constant below 1 for all instances), refining the Theta(sqrt(n)) price of balancedness.
- Single-category egalitarian price of cardinality is exactly max{(m-n+1)/k, 1}, tight for all instances.
- Two-agent multi-category utilitarian price of cardinality is exactly 2/(k1/m1 + k2/m2); for general n it is at most m1/k1, tight when there are n categories with equal ratios k_j/m_j.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the per-agent item limit k | Cardinality-constrained allocation · Single category | utilitarian price of cardinality | Helped |
| Increase the per-agent item limit k | Cardinality-constrained allocation · Single category | egalitarian price of cardinality | Helped |
Surprising findings
- The utilitarian price of cardinality in the single-category case depends only on m and k, not directly on n.
Limitations
- Exact utilitarian bound for multiple categories with n >= 3 agents remains open.
- Analysis restricted to additive utilities and normalized instances.
- Dual problem where each agent must receive at least k items is not studied.
Experimental setup
Metrics: price of cardinality (worst-case ratio of optimal to constra
Baselines: price of balancedness (Bei et al.)
Builds on: price of balancedness price of fairness
Closest papers by meaning
- Finding Fair Allocations under Budget Constraints (AAAI 2023 · similarity 0.89)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.88)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.88)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (AAAI 2024 · similarity 0.88)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.87)
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.