Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective
Authors: Alexander Lam, Bo Li, Ankang Sun
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose the notion of the price of cardinality, which captures the worst-case multiplicative loss of utilitarian or egalitarian social welfare resulting from imposing the cardinality constraint. We then characterize tight or almost-tight bounds on the price of cardinality as exact functions of the instance parameters, demonstrating how the social welfare improves as k is increased. In particular, one of our main results refines and generalizes the existing asymptotic bound of Θ( n) on the price of balancedness. |
| Researcher Affiliation | Academia | Alexander Lam1 , Bo Li2, Ankang Sun2 1Department of Computer Science, City University of Hong Kong 2Department of Computing, The Hong Kong Polytechnic University EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithmic steps in natural language within the proof of Lemma 3.5, but does not present them in a structured pseudocode or algorithm block format. For example, 'Step 1: Set B A as the initial allocation, P S as the initial set of unsatisfied agents, and Q R as the initial set of active agents; Step 2: If there are no unsatisfied agents, then terminate and output the underlying allocation B (this will be Ak). Otherwise, find the item e S i P Bi and an active agent i Q such that reassigning e to agent i causes the minimum utilitarian social welfare loss among all single-item reassignments from items of unsatisfied agents to active agents. Reassign e to agent i , and update B accordingly. Step 3: Update P and Q, and return to Step 2.' |
| Open Source Code | No | The paper does not contain any statements about releasing code or provide links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not use or refer to any specific datasets for experimental evaluation. Therefore, there is no information regarding open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments using datasets, so there is no mention of dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental implementation, hence no software dependencies with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and bounds, not empirical experiments. Therefore, it does not provide details about experimental setup, hyperparameters, or training configurations. |