Source-linked AI summary
A lone divider allocation algorithm with subjective divisibility
Uriel Feige
TL;DR
Subjective divisibility creates a lone-divider difficulty because agents may reject or be unable to discard newly created parts. The paper adapts the lone-divider framework with pure divisions, preliminary one-agent and two-agent steps, and a 2-matching procedure, establishing 3/5-MMS allocations.
Problem
Subjective divisibility makes lone-divider cuts problematic when other agents view divided items as indivisible.
Method
The approach uses pure divisions, preliminary one-agent and two-agent steps, and a 2-matching procedure when pure division fails.
Results
3/5-MMS allocations exist, improving the previous 1/2-MMS guarantee; the result also covers n ≤4.
Takeaways & Limitations
The adapted lone-divider framework improves existential MMS guarantees in the subjective divisibility setting, including the n ≤4 case.
Takeaways & Limitations
For suitably large n, the algorithm can fail to give some agent an acceptable bundle.
Abstract
from arXiv · showhide
In the subjective divisibility allocation model, all goods are divisible, every agent $i$ has a non-negative additive valuation function $v_i$, where for some goods $v_i$ is additive over fractions of the good, and for some goods, any fraction smaller than~1 has value~0. Previous work established the existence of $\frac{5}{9}$-MMS allocations in this setting. We show that $\frac{3}{5}$-MMS allocations exist. Our proof is based on an adaptation of the lone divider framework.
1 Introduction
The paper studies fair allocation with agent-dependent divisibility and improves existential MMS guarantees for larger agent populations. It adapts the lone divider framework using pure divisions and new preliminary procedures.
- Setting: Subjective divisibility assigns each item as divisible or indivisible separately for each agent, with allocations represented by item fractions.Agents have non-negative valuations over items, and the allocation is an n by m matrix of item fractions.
- Prior guarantees: Previous work established 5/9-MMS allocations generally and 2/3-MMS allocations when n ≤4, while some instances limit every allocation to 2/3-MMS for at least one agent.The paper targets improved existential guarantees for n ≥5.
- Challenge: The lone divider framework is adapted because a divider may split items that other agents regard as indivisible.Such splits can create pieces that other agents can neither accept nor discard without leaving only worthless fractions.
- Approach: Pure divisions forbid subdividing any previously undivided item, avoiding problematic cross-agent pieces but reducing the approximation ratio.The algorithm adds preliminary one-agent steps before applying the lone divider procedure.
- Contribution: The main contribution improves the approximation ratio from 1/2 to 3/5-MMS allocations.The proof combines two-agent steps with a fallback 2-matching procedure when the lone divider does not produce a pure division.
2 Our 3 5-MMS allocation algorithm
The algorithm combines preliminary one-agent and two-agent steps with a lone pure-divider procedure, using a 2-matching fallback when pure division cannot be obtained. Its analysis establishes that choosing ρ = 3/5 yields an acceptable bundle for every agent.
- Algorithm framework: The polynomial-time algorithm scales valuations so each agent’s MMS value is 1 and seeks bundles worth at least ρ.Items may remain free, become fully allocated, or become partial items whose unallocated fractions remain available.
- Preliminary steps: The algorithm first applies one-agent steps and then two-agent steps before using the lone pure-divider step.One-agent steps allocate part of a single item; two-agent steps allocate parts of three items to two agents, possibly sharing one item.
- Lone pure divider steps: Pure divisions forbid splitting any previously undivided item, preventing losses for agents who view that item as indivisible.The lone pure-divider step assigns acceptable parts through a bipartite matching between active agents and partition parts.
- Approximation analysis: The analysis compensates for losses from two-agent steps with indivisible shared items by eliminating one MMS part and using its surplus value.The resulting accounted loss is at most 3ρ − 1, which is bounded by 2 − 2ρ when ρ ≤ 3/5.
- Termination: If the preliminary and lone pure-divider steps are unavailable, the algorithm applies a 2-matching step in which every active agent receives two available items.Special items and matching arguments establish the required applicability for ρ ≤ 3/5.
3 Discussion
The discussion places the algorithm’s guarantees alongside computational considerations, stronger small-agent guarantees, and limitations for larger instances. It also describes an adversarial example and explains why it does not conclusively rule out better execution choices.
- Computational aspects: An FPTAS can produce a (3/5−ϵ)-MMS allocation when MMS values are unknown.With known MMS values, the algorithm runs in polynomial time; computing MMS values is NP-hard.
- Stronger guarantees: For n ≤ 4, the algorithm outputs 2/3-MMS allocations.After a two-agent step when n = 4, two agents remain, and one lone pure divider step completes the allocation.
- Stronger guarantees: For n > 4, the stated algorithm does not guarantee 2/3-MMS.The obstacle is a two-agent step with an indivisible shared item.
- Limitations: For sufficiently large n, instances exist where the algorithm fails to give some agent an acceptable bundle at 3/5+ϵ.The construction uses 5k items, 3k+1 agents, and ϵ = 1/(5k).
- Limitations: The failure example is not conclusive because it assumes an adversarial execution, whereas an angelic execution may achieve a better ratio.The proposed choices include selecting the best available two-agent step and interleaving step types in the best order.
- Related guarantees: The discussion notes that equal-value instances admit 2/3-MMS allocations, while whether 2/3-MMS always exists remains open.The cited result establishes 2/3-MMS allocations for such instances, not for the general setting.