Fair Division with Market Values
Authors: Siddharth Barman, Soroush Ebadian, Mohamad Latifian, Nisarg Shah
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce a model of fair division with market values, where indivisible goods must be partitioned among agents with (additive) subjective valuations, and each good additionally has a market value. The market valuation can be viewed as a separate additive valuation that holds identically across all the agents. We seek allocations that are simultaneously fair with respect to the subjective valuations and with respect to the market valuation. We show that an allocation that satisfies stochastically-dominant envy-freeness up to one good (SD-EF1) with respect to both the subjective valuations and the market valuation does not always exist, but the weaker guarantee of EF1 with respect to the subjective valuations along with SD-EF1 with respect to the market valuation can be guaranteed. We also study a number of other guarantees such as Pareto optimality, EFX, and MMS. In addition, we explore non-additive valuations and extend our model to cake-cutting. |
| Researcher Affiliation | Academia | Siddharth Barman1, Soroush Ebadian2, Mohamad Latifian3, Nisarg Shah2 1Indian Institute of Science Bangalore 2University of Toronto 3University of Edinburgh EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | No | Minimal Envied Swap (MES) Algorithm. As we did for establishing Corollary 1, we consider πv the ranking induced by the (additive) market valuation v. Then, we partition the items into (M1, . . . , M m/n ) such that Mk := {g M : (k 1)n < πv(g) kn}. As noted previously, for any allocation A, if |Ai Mk| 1 for each k [ m/n ] and all agents i, then A is SD-EF1 w.r.t. v. We now provide an algorithm that finds such an allocation that is 1/2-EF1 w.r.t. monotone, subadditive subjective utilities. We start with an allocation A with empty bundles, Ai = , for all agents i N. Also, initialize charity C = M as the set of all the unallocated goods. A subset T C is said to be an envied feasible subset of the charity if (1) there exists an agent i N envying it, i.e., ui(Ai) < ui(T), and (2) |T Mk| 1 for each k [ m/n ]. Further, we say that an envied feasible subset T P is minimal if no agent envies any strict subset of T. It is easy to verify that while there exists an envied feasible subset of the charity, there also exists a minimal envied feasible subset of the charity. The algorithm now works in two phases. Phase 1: While there exists a minimal envied feasible subset T of the charity C, select an agent i who envies T, and update Ai = T and charity (unallocated good) C = M \ ( i N Ai). Phase 2: Once Phase 1 has terminated, allocate goods in C arbitrarily subject to maintaining |Ai Mk| 1 for all agents i N and each k [ m/n ]. |
| Open Source Code | No | The paper does not contain any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper presents theoretical research, focusing on models, definitions, and theorems related to fair division. It does not utilize or refer to any experimental datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments using datasets, thus there is no mention of dataset splits. |
| Hardware Specification | No | The paper describes theoretical models and proofs; it does not detail any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper describes theoretical models and proofs; it does not mention any specific software dependencies or version numbers for experimental replication. |
| Experiment Setup | No | The paper focuses on theoretical analysis and proofs, and as such, it does not describe any experimental setup details such as hyperparameters or training configurations. |