Source-linked AI summary
Fractional Assignment with $\ell_1$ Preferences
Yasushi Kawase, Warut Suksompong, Hanna Sumita, Yu Yokoi
TL;DR
The paper asks how to assign divisible objects when agents have potentially mixed ideal distributions and evaluate outcomes by ℓ1 distance or overlap. It proposes water filling and quadratic programming mechanisms, proving shared efficiency, fairness, and incentive properties while identifying distinct comparative strengths. WF provides group-strategyproofness, whereas QP offers stronger robustness in egalitarian overlap welfare, within bounds established by the paper.
Problem
The paper studies fractional assignment with non-degenerate ideal distributions, where agents evaluate received distributions by ℓ1 distance rather than ordinal preferences over indivisible objects.
Method
The paper proposes a water filling mechanism and a quadratic programming mechanism for fractional assignment with ℓ1 preferences.
Results
Both mechanisms are utilitarian-optimal, envy-free, strategyproof, and equal-treatment-of-equals; WF is group-strategyproof, while QP is more robust in egalitarian overlap welfare.
Takeaways & Limitations
WF and QP provide different advantages: WF resists beneficial coordinated manipulation, while QP offers robust minimum overlap utility across agents.
Takeaways & Limitations
The tightest universal comparison constant for WF and QP egalitarian overlap welfare remains open, with the paper establishing 7/6 ≤ c ≤ 2.
Abstract
from arXiv · showhide
We study a fractional assignment setting where $n$ objects are to be assigned to $n$ agents with unit capacity, and each agent specifies an ideal distribution over the objects. Unlike in classic random assignment, these ideal distributions are not necessarily degenerate, as agents may prefer a mixture of objects rather than any single object. We assume that agents seek to minimize the $\ell_1$ distance between their ideal distribution and the distribution they receive, which is equivalent to maximizing the overlap between the two distributions. We propose two mechanisms, one based on water filling (WF) and the other on quadratic programming (QP), and show that both mechanisms are utilitarian-optimal (and hence Pareto efficient), envy-free, strategyproof, and satisfy equal treatment of equals. Moreover, we highlight a distinct advantage of each mechanism: while the WF mechanism satisfies the stronger property of group-strategyproofness, the QP mechanism is more robust in terms of egalitarian overlap welfare.
1 Introduction
The paper studies fractional assignment with non-degenerate ideal distributions and ℓ1 preferences, then introduces WF and QP mechanisms with strong fairness, efficiency, and incentive guarantees. The mechanisms share core properties but differ in group-strategyproofness and egalitarian overlap welfare.
- Motivation: Agents may prefer diversified distributions over divisible objects, motivating fractional assignment rather than lotteries over indivisible objects.Applications include dividing time among facilities or tasks, allocating resources across domains, and rotating chores over repeated assignments.
- Preferences: ℓ1 preferences measure summed per-object deviations from an ideal distribution and equivalently maximize summed overlap.Overlap is the sum, across objects, of the minimum received and ideal amounts.
- Mechanisms: The WF mechanism iteratively fills allocation entries at equal speed, first respecting caps and object exhaustion, then continuing without caps until completion.Its filling process resembles probabilistic serial, although the setting uses ideal distributions rather than ordinal rankings.
- Mechanisms: The QP mechanism returns, in one step, the minimum-ℓ2-norm allocation among utilitarian-optimal allocations.Minimum ℓ2 norm means minimizing the sum of squared allocation entries.
- Guarantees: Both mechanisms are utilitarian-optimal, envy-free, strategyproof, and satisfy equal treatment of equals.Utilitarian optimality implies Pareto efficiency in the paper’s setting.
- Comparative strengths: WF is group-strategyproof, whereas QP is more robust for egalitarian overlap welfare: QP can exceed WF by Ω(n) and is never worse by more than a factor of 2.The two mechanisms therefore trade off coalition-resistance against worst-agent overlap performance.
2 Preliminaries
The paper models fractional assignment as choosing a doubly stochastic allocation that minimizes agents’ ℓ1 distance from target distributions. It characterizes utilitarian-optimal allocations and introduces water-filling and quadratic-programming mechanisms for selecting among them.
- 2.1 Model: A fractional assignment is a doubly stochastic matrix whose rows give agents’ received distributions and whose columns allocate each object fully.Each agent has a target distribution, and disutility is the ℓ1 distance between received and target distributions.
- 2.1 Model: Minimizing ℓ1 disutility is equivalent to maximizing overlap between received and target distributions.
- 2.2 Basic Properties of ℓ1 Preferences: An allocation is utilitarian-optimal exactly when it matches targets on exactly demanded objects, falls below targets on over-demanded objects, and exceeds targets on under-demanded objects.The classification compares each object’s total reported demand with its unit supply.
- 2.3 The WF and QP Mechanisms: The WF mechanism fills all entries simultaneously up to target caps before completing the doubly stochastic matrix without cap constraints.Phase 1 stops entries when their caps or column capacities are reached; Phase 2 completes remaining rows and columns.
- 2.3 The WF and QP Mechanisms: The QP mechanism selects the unique minimum-ℓ2-norm allocation among utilitarian-optimal allocations.Strict convexity over the nonempty, closed, convex optimal set makes the mechanism well-defined.
- 2.3 The WF and QP Mechanisms: Both mechanisms can be implemented in polynomial time and satisfy equal treatment of equals.
3 Properties of the WF Mechanism
The WF mechanism preserves the overlap utilities established at the end of its capped filling phase and is utilitarian-optimal, envy-free, and group-strategyproof.
- 3 Properties of the WF Mechanism: For every agent and object, final overlap equals the Phase 1 allocation, so Phase 2 does not change agents’ overlap utilities.Phase 2 only increases entries that already reached their target caps.
- 3 Properties of the WF Mechanism: The WF mechanism is utilitarian-optimal, envy-free, and group-strategyproof.
- 3 Properties of the WF Mechanism: Envy-freeness follows because each agent’s received overlap is at least the overlap obtained from another agent’s allocation evaluated against that agent’s target.
- 3 Properties of the WF Mechanism: For any coalition misreport, the coalition’s total overlap on every object cannot increase, preventing all members from weakly improving with one strict improvement.
4 Properties of the QP Mechanism
The QP mechanism chooses a unique quadratic optimum within the utilitarian-optimal set. It is utilitarian-optimal, envy-free, and strategyproof, but not weakly group-strategyproof.
- 4 Properties of the QP Mechanism: The QP mechanism is utilitarian-optimal, envy-free, and strategyproof.
- 4 Properties of the QP Mechanism: Unlike WF, QP fails even weak group-strategyproofness.
- 4 Properties of the QP Mechanism: QP minimizes a strictly convex quadratic objective over the utilitarian-optimal allocation set, yielding a unique solution.
- 4 Properties of the QP Mechanism: Its allocation satisfies coordinatewise bounds that keep each agent’s allocation within the range of that agent’s reported amounts.The KKT representation underlies this bound and the envy-freeness proof.
- 4 Properties of the QP Mechanism: Strategyproofness is proved by tracing outcomes along report line segments, where fixed active constraints make outcomes and truthful disutility affine.A minimum-ℓ2-norm circulation argument rules out negative slopes on each interval.
5 Comparing the WF and QP Mechanisms
Both mechanisms share utilitarian, fairness, and individual incentive guarantees, but WF is stronger against coalitional manipulation while QP offers more robust egalitarian overlap welfare. QP’s advantage can grow with n, although its worst-case relative disadvantage is bounded by 2.
- 5 Comparing the WF and QP Mechanisms: Both mechanisms are utilitarian-optimal, envy-free, strategyproof, and equal-treatment-of-equals, while WF is group-strategyproof and QP is not weakly group-strategyproof.
- 5 Comparing the WF and QP Mechanisms: QP’s egalitarian overlap welfare can exceed WF’s by a factor of Ω(n), while WF’s welfare is never more than twice QP’s.Egalitarian overlap welfare is the minimum overlap utility among agents.
- 5 Comparing the WF and QP Mechanisms: There are profiles with EG(φWF(P), P) = 1/n and EG(φQP(P), P) = 1/2, producing a welfare ratio of n/2.
- 5 Comparing the WF and QP Mechanisms: For every profile, EG(φWF(P), P) ≤ 2 · EG(φQP(P), P).
- 5 Comparing the WF and QP Mechanisms: QP does not always dominate WF: one example gives EG(φWF(P), P)/EG(φQP(P), P) = 7/6.
- 5 Comparing the WF and QP Mechanisms: The smallest universal comparison constant remains open, with the paper establishing 7/6 ≤ c ≤ 2.
6 Conclusion and Future Work
The paper studies fractional assignment with mixed ideal distributions and ℓ1-based overlap preferences, proposing two mechanisms with shared desirable properties but different advantages. Future work includes characterizing optimal mechanisms in this class and extending the setting beyond ℓ1 distances.
- The paper proposes two mechanisms that are utilitarian-optimal, envy-free, strategyproof, and satisfy equal treatment of equals.
- The fractional assignment model allows ideal distributions to be mixed rather than degenerate, with outcomes evaluated by ℓ1 distance or equivalently overlap utility.
- Future work could characterize whether the proposed mechanisms are optimal within the class satisfying utilitarian-optimality, envy-freeness, strategyproofness, and equal treatment of equals.
- The model could be extended to ℓp distances for p > 1, whose lack of a simple overlap representation may produce substantially different mechanism structures.
AI Declaration
The authors used ChatGPT and Codex to help develop the proof of Proposition 8, specifically by identifying the tangent program approach. They verified the final argument and retained responsibility for its correctness.
- ChatGPT and Codex assisted in developing Proposition 8’s proof by helping identify the tangent program approach.
- The authors verified the final argument and stated that they take full responsibility for its correctness.
A Comparison to the Work of Ramezanian [2024]
The paper compares WF and QP with Ramezanian’s URC mechanisms, showing differences in equal treatment, welfare equivalence, in-betweenness, and group-strategyproofness. These mechanisms also answer three open questions posed by Ramezanian.
- WF satisfies equal treatment of equals, unlike URC mechanisms, because URC’s sequential second phase violates this property.
- The paper identifies three open questions from Ramezanian’s work and answers them using the proposed WF and QP mechanisms.
- QP is strategyproof, Pareto efficient, anonymous, and envy-free, yet is not welfare-equivalent to URC mechanisms.
- WF provides an example of a strategyproof and Pareto-efficient mechanism that does not satisfy the in-betweenness property.
- In a comparison example, the first agent receives less of the first object despite demanding more, because 5/12 < 11/24.
- QP provides an example of a strategyproof and Pareto-efficient mechanism that is not non-bossy, while preserving the stated qualifications concerning Ramezanian’s non-bossiness notion.
- QP can change other agents’ allocations of an over-demanded object even when the manipulated agent receives the same amount as before.
B The QP Mechanism Is Not Weakly Group-Strategyproof
The appendix proves that QP is not weakly group-strategyproof by constructing a four-agent manipulation whose two coalition members both strictly improve. KKT certificates establish the relevant QP outcomes.
- The result establishes failure of weak group-strategyproofness and therefore also failure of group-strategyproofness.
- QP is not weakly group-strategyproof when n = 4.
- A coalition S := {1, 4} is given a manipulated profile Q, and both coalition members strictly improve through the manipulation.
- The proof certifies the allocations at profiles P and Q using KKT conditions, with strict convexity ensuring the displayed optimizer is unique.
C Proof of Proposition 8
The proof reduces strategyproofness to showing that truthful reporting weakly minimizes the agent’s loss. It connects this to the endpoint inequality f(1) ≥ f(0) along the path from the truthful to deviating report.
- The proof suffices to establish FP,i(qi) ≥ FP,i(pi) for every alternative report qi.
- For a deviation qi, the proof interpolates between pi and qi using d := qi − pi and pi + τd.
- The central goal is the endpoint inequality f(1) ≥ f(0), which compares deviation and truthful-report losses.
C.1 Ray structure
Along the report segment, the QP outcome is continuous and piecewise affine after partitioning at column-sum boundaries and critical regions. Refining further at loss-sign changes makes the agent’s loss piecewise affine as well.
- C.1 Ray structure: Column-sum expressions are affine in τ and change feasibility regime at most once, yielding intervals with fixed inequality directions.At a column-sum boundary, the column-sum and QP constraints force all corresponding coordinates to match.
- C.1 Ray structure: The QP outcome X(τ) is continuous and piecewise affine on [0, 1] after finitely refining the report path into critical regions.This follows from parametric strictly convex quadratic programming on intervals with fixed inequality directions.
- C.1 Ray structure: Refining at zeros of affine slacks and at points where xij(τ) = pij fixes the sign of every absolute-value term in the loss.
- C.1 Ray structure: The loss f(τ) is affine on each refined interval because every absolute-value term has an affine argument with constant sign.
C.2 Endpoint inequality from interval slopes
The endpoint loss difference telescopes into interval slopes, and each slope is shown nonnegative through a tangent quadratic program and a circulation argument. Consequently, the loss at the deviating report is no smaller than at the truthful report.
- C.2 Endpoint inequality from interval slopes: f(1) − f(0) equals the sum of interval slopes multiplied by their interval lengths.
- C.2 Endpoint inequality from interval slopes: On each interval, the outcome slope is the unique optimizer of a strictly convex tangent quadratic program determined by the active constraints.
- C.2 Endpoint inequality from interval slopes: Every interval slope a(ℓ) is nonnegative, so each term in the telescoping sum is nonnegative.
- C.2 Endpoint inequality from interval slopes: A circulation decomposition supplies a feasible perturbation that contradicts tangent-program optimality if an interval slope were negative.
- C.2 Endpoint inequality from interval slopes: Therefore f(1) ≥ f(0), implying FP,i(qi) ≥ FP,i(pi) for every deviation.