PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Fair Division under Eligibility Constraints

Joes Biburger, Nicole Megow, Golnoosh Shahkarami

arXiv:2610.08064v1cs.GT

TL;DR

The paper asks how fair allocation should be defined and achieved when items are eligible for only some agents. It uses eligibility-aware proportional and envy notions to study online restricted assignment, finding different patterns for proportionality and envy across goods and chores.

  • Problem

    When items are restricted to eligible agents, standard fair-division benchmarks do not account for which items agents could receive or how entitlement should be shared.

    Source: §1 · p. 2

  • Method

    The paper studies identical valuations using proportional shares that divide each item equally among its eligible agents, alongside eligibility-aware envy comparisons.

    Source: §1 · pp. 2–3

  • Results

    Eligibility separates goods from chores for proportionality, while goods and chores are equivalent under eligibility-aware envy notions; offline Prop1 always exists, though exact proportionality and PropX may fail for chores.

    Source: §1 · p. 3, §6 · p. 20

  • Takeaways & Limitations

    The study identifies Prop1 as the strongest exact proportionality notion always achievable offline under restricted assignment and distinguishes strong from weak envy guarantees.

    Source: §6 · p. 20

    The results assume identical valuations and online adversarial arrivals with irrevocable assignments; whether additional information or milder online models yield stronger guarantees remains open.

    Source: §1 · p. 3, §6 · p. 20

Abstract

from arXiv · show

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $\Theta(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $\Theta(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

1 Introduction

The introduction frames fair division under eligibility constraints, where items can go only to some agents, and develops eligibility-aware proportional and envy benchmarks. It studies online restricted assignment, finding that proportionality distinguishes goods from chores while eligibility-aware envy brings them together.

1.1 Our Results

  • For online Prop1, eligibility creates a sharp chore–goods separation, while eligibility-aware envy notions make the two settings equivalent under identical valuations.The results concern deterministic algorithms and adversarial arrivals with irrevocable assignments.Source: §1 · p. 3, §1.1 · p. 4
  • For chores, Prop1 always exists offline although exact proportionality and PropX may fail; online deterministic Prop1 has optimal factor Θ(√m), with the lower bound already for unit-size jobs.The online lower bound applies even when every job has unit size.Source: §1.1 · p. 4
  • For goods, offline Prop1 always exists while exact proportionality and PropX are not guaranteed; online deterministic Prop1 has optimal factor Θ(log m).The lower bound holds even for unit values.Source: §1.1 · p. 4
  • Strong EF1 may fail offline and admits no deterministic online approximation, whereas weak EF1 is maintainable online and weak EFX exists offline but not online.Under identical valuations, the envy results transfer between chores and goods.Source: §1.1 · p. 4

1.2 Overview of techniques

  • The online chore algorithm assigns each job to an eligible machine with maximum approximate Prop1-slack at α = Θ(√m), using a potential that penalizes negative slack.For goods, the approach uses maximum α-deficit at α = Θ(log m), with value-class grouping for arbitrary values; envy results use a goods–chores equivalence.Source: §1.2 · pp. 5–6

1.3 Related Work

  • Prior online fair-division work did not allow eligibility constraints; this paper’s online bounds identify losses due to eligibility relative to exact online Prop1 in the unrestricted identical-valuation setting.Offline Prop1 existence results use assignment-LP rounding machinery.Source: §1.2 · p. 5, §1.3 · p. 7

2 Preliminaries

The section defines an eligibility-aware proportional benchmark and the relaxations used for indivisible chores and goods. Offline, Prop1 is achievable in both settings, while stronger proportionality guarantees can fail.

2 Preliminaries

  • The proportional share divides each job equally among its eligible machines, partitioning total job size; exact proportionality compares machine load with that share.For chores, load must be at most the share; for goods, it must be at least the share.Source: §2 · p. 8
  • Prop1 relaxes proportionality by discounting a received job for chores or crediting an eligible unreceived job for goods.Source: §2 · p. 8

2.1 Offline allocation of chores and goods

  • Prop1 in chores and goods is not interchangeable: an allocation can satisfy it in either setting while failing it in the other.Source: §2.1 · p. 9
  • PropX can fail for both chores and goods, so exact proportionality can fail as well; Prop1 is the strongest proportionality guarantee that always survives eligibility.Source: §2.1 · p. 9
  • Prop1 allocations exist and can be computed in polynomial time for restricted-assignment chores and goods.These offline existence results were independently obtained for general additive valuations and mixed items by Sun, Wang, and Li [SWL26].Source: §2.1 · p. 9

3 Online Proportionality for Chores

For online restricted-assignment chores, Prop1 requires a Θ(√m) approximation for deterministic algorithms. The section proves this bound first for unit jobs, then extends the upper bound to arbitrary processing times with a Fit/Shadow algorithm.

3 Online Proportionality for Chores

  • Θ(√m) is the optimal online Prop1 approximation for chores, with the lower bound holding even for unit-size jobs.For arbitrary processing times, a deterministic algorithm achieves O(√m)-Prop1.Source: §3 · p. 9, §3.1 · p. 13, §3.2 · p. 14

3.1 Unit Processing Times

  • For unit jobs, Greedy α-slack assignment with α = √m + 1 achieves α-Prop1 by keeping its potential from increasing.The potential penalizes small positive slack exponentially and adds a unit penalty for negative slack; fewer than √m machines can have negative α-slack.Source: §3.1 · pp. 10–11
  • No deterministic online algorithm guarantees o(√m)-Prop1 for unit jobs, even with prior knowledge of final proportional shares.The adversary can force this lower bound using eligibility constraints.Source: §3.1 · p. 13

3.2 General Processing Times

  • For arbitrary processing times, Fit/Shadow assigns jobs that fit by updated α-Prop1-slack and otherwise chooses an eligible machine whose largest job can be shadowed.The deterministic algorithm achieves O(√m)-Prop1.Source: §3.2 · p. 14
  • The Fit/Shadow analysis maintains that every job that does not fit can shadow the largest jobs on more than half of its eligible machines.A job-dependent potential includes a local penalty for machines whose largest job is too large to be shadowed.Source: §3.2 · p. 14

4 Online Proportionality for Goods

For online restricted-assignment goods, the optimal Prop1 approximation is logarithmic in the number of agents. A greedy α-deficit rule gives the upper bound for equal values, and bucketing extends it to arbitrary values.

4 Online Proportionality for Goods

  • O(log m)-Prop1 is achievable for arbitrary-value goods, while no deterministic algorithm guarantees α-Prop1 for α < ln(m) −1, even for unit values.Together, the bounds give a Θ(log m) approximation factor.Source: §4 · pp. 15, 17
  • For equal-value goods, Greedy α-deficit assignment achieves α-Prop1 with α = log2(m).The rule assigns each arriving good to an eligible agent with maximum α-deficit.Source: §4 · p. 16
  • The equal-value guarantee follows from a potential that does not increase when a good is assigned to the eligible agent with largest α-deficit.The analysis bounds the potential by m, yielding the stated α-Prop1 guarantee.Source: §4 · pp. 16–17
  • For arbitrary values, the algorithm rounds goods up to powers of two and runs a separate equal-value greedy instance for each rounded value.This bucketing scheme extends the equal-value result to arbitrary values.Source: §4 · p. 17

5 Envy-based Fairness under Eligibility Constraints

Eligibility-aware envy compares bundles in different ways depending on the notion used. Strong EF1 can fail offline and cannot be approximated online, while weak EF1 is achievable online and weak EFX is not.

5 Envy-based Fairness under Eligibility Constraints

  • Strong envy compares only jobs both machines could receive, whereas weak envy compares the envied machine’s full load against the envying machine’s eligible jobs.EF1 removes one job and EFX requires the condition to hold after removing any qualifying job.Source: §5 · pp. 17–18
  • With identical valuations, goods and chores are equivalent for strong and weak EF, EF1, and EFX under eligibility constraints.The equivalence contrasts with proportionality-based notions, where goods and chores can have different guarantees.Source: §5 · p. 18

5.1 Strong Envy

  • Strong EF1 may fail offline, even with seven machines, and no deterministic online algorithm guarantees strong α-EF1 for any α > 0, even with three machines.The offline nonexistence result uses general processing times.Source: §5.1 · pp. 18–19

5.2 Weak Envy

  • Weak EF1 is maintainable online for chores with arbitrary processing times, while weak EFX exists and is computable offline in polynomial time but cannot be guaranteed online, even with two machines.The offline EFX construction sorts jobs by non-increasing processing time before running the online algorithm.Source: §5.2 · pp. 19–20

6 Conclusion

The paper studies online proportional and envy-based fairness under restricted assignment. Its results identify different guarantees for goods and chores under proportionality, and for strong and weak envy notions.

6 Conclusion

  • The study initiates online proportional and envy-based fairness under restricted assignment, finding a chore–goods separation for proportionality and a decisive role for the envy notion.Several questions remain open.Source: §6 · p. 20
  • Offline, Prop1 always exists under restricted assignment, while Prop and PropX may fail; optimal approximation guarantees for stronger proportionality notions remain open.The conclusion identifies α-Prop and α-PropX guarantees in offline and online settings as open questions.Source: §6 · p. 20
  • For envy, strong EF1 may fail offline, weak EF1 is achievable online, and weak EFX is achievable offline but not online.Open directions include approximating strong EF1 and investigating other eligibility-aware notions and constraint settings.Source: §6 · p. 20
  • The online results assume adversarial arrivals and irrevocable assignments; stronger guarantees under randomized or random-order models remain open.The conclusion also lists predictions, known final proportional shares, and limited recourse as settings for future study.Source: §6 · p. 20

A Omitted Proofs from Section 2 (Offline Goods and Chores)

The offline proofs establish that Prop1 is achievable in restricted-assignment goods and chore allocation, while stronger proportionality guarantees can fail. They also show that Prop1 depends on whether items are treated as goods or chores.

A Omitted Proofs from Section 2 (Offline Goods and Chores)

  • An allocation can satisfy Prop1 for chores but not goods, or satisfy it for goods but not chores.The observation uses fully eligible unit-size items in each direction.Source: A Omitted Proofs from Section 2… · p. 21
  • PropX, and therefore exact proportionality, is not always achievable in either chores or goods.The proof gives separate counterexamples for the two settings.Source: A Omitted Proofs from Section 2… · p. 21
  • Prop1 allocations exist for both restricted-assignment chores and goods and can be computed in polynomial time.For chores, the proof uses LP rounding; the goods proof modifies the rounding method.Source: A Omitted Proofs from Section 2… · pp. 21–22
  • The proof scales each job by its eligible machines’ proportional shares and rounds a fractional assignment to an integral one.For goods, the rounding allows each agent to miss at most one partially allocated good.Source: A Omitted Proofs from Section 2… · p. 22

B Omitted Proofs from Section 3 (Online Chore Setting)

The appendix examines an online fairness analogue of least-loaded-machine scheduling. The maximum-hypothetical-Prop1-slack rule fails to guarantee even a sublinear approximation, including for unit-size jobs.

B.1 Simple Greedy strategy fails

  • The proposed greedy rule assigns each arriving job to an eligible machine with the greatest hypothetical Prop1-slack after assignment.It is presented as a fairness analogue of assigning jobs to a least-loaded eligible machine.Source: §B.1 · p. 23
  • The maximum-hypothetical-Prop1-slack rule cannot achieve an o(m)-approximation, even for unit-size jobs.The result is established by an adversarial restricted-assignment instance.Source: §B.1 · p. 23
  • The construction produces an allocation violating α-Prop1 for the greedy rule.Source: §B.1 · p. 23

B.2 Upper bound online chores

A deterministic online algorithm achieves O(√m)-Prop1 for restricted-assignment chores. Its proof handles jobs with few eligible machines separately and uses a fit-or-shadow rule for the others.

B.2 Upper bound online chores

  • O(√m)-Prop1 is achievable by a deterministic online algorithm for chores with general processing times.The proof sets α = 8√m and maintains nonnegative α-Prop1-slack throughout allocation.Source: §B.2 · pp. 23, 30
  • Jobs with at most α eligible machines are assigned arbitrarily and ignored in the algorithm’s intermediate slack calculations.The proof later reintroduces them, showing their proportional-share contribution makes them harmless to the guarantee.Source: §B.2 · pp. 24, 30
  • For jobs with more than α eligible machines, the algorithm assigns a job to a machine where it fits or where it shadows the previous largest job.The fit case requires updated slack at least 2·pj; otherwise the shadow case selects among machines whose largest job is at most αpj/kj.Source: §B.2 · p. 24
  • A potential-function argument bounds the number of machines with small slack and establishes the shadow condition when the fit case fails.The potential is designed for the arriving job; its penalty terms account for machines where that job cannot shadow an earlier largest job.Source: §B.2 · p. 24

C.1 Greedy by deficit fails

The appendix shows that allocating goods to an eligible agent with the largest 1-deficit can fail to provide strong Prop1 approximation guarantees. It also supplies a technical inequality used in the proof of Theorem 11.

C.1 Greedy by deficit fails

  • A tie-breaking order does not avoid the lower bound: the construction arranges distinct deficits and then preserves their order for the greedy choices.The first phase adds at most one unit of utility per agent, and its proportional-share contribution makes the final ratio improvement strictly less than twofold.Source: §C.1 · pp. 30–31
  • Lemma 23 shows that allocating each arriving good immediately and irrevocably to an eligible agent with largest 1-deficit may fail to yield allocations satisfying m/8-Prop1, even when all goods have utility 1.Source: §C.1 · p. 30

C.2 Proof of Lemma 10 (technical Lemma used in the proof of Theorem 11)

  • Lemma 10 considers integers k≥2 and m≥3 with m≥k; in the cited case k≥3, applying m≥k and m≥3 yields a quantity less than zero.Source: §C.2 · p. 31

C.3 Proof of Theorem 9 (upper bound log m for online goods)

A deterministic online algorithm achieves O(log m)-Prop1 for restricted-assignment goods. With identical valuations, eligibility-preserving relabeling makes goods and chores equivalent for the paper’s envy notions.

C.3 Proof of Theorem 9 (upper bound log m for online goods)

  • O(log m)-Prop1 is achievable by a deterministic online algorithm for restricted-assignment goods with arbitrary values.The algorithm rounds good sizes up to powers of two and applies the equal-size-goods algorithm to separate virtual instances.Source: §C.3 · pp. 31–32

D.1 Equivalence of Goods and Chores

  • Relabeling each chore as a good of equal value while preserving eligibility and allocation preserves strong and weak EF, EF1, and EFX.The equivalence applies in both directions.Source: §D.1 · p. 32

D.2 Strong Envy

Strong EF1 can fail offline and cannot be approximated online for chores with general processing times. Weak EF1 remains achievable online, whereas weak EFX is achievable offline but not online.

D.2 Strong Envy

  • Strong EF1 may fail offline for chore instances with general processing times, even with m = 7 machines.The constructed instance has no allocation satisfying EF1.Source: §D.2 · pp. 33–34
  • For every α > 0, no deterministic online algorithm can guarantee strong α-EF1 in restricted-assignment chore allocation with general processing times, even when the instance has m = 3 machines.Source: §D.2 · p. 35

D.3 Weak Envy

  • A deterministic online algorithm maintains weak EF1 for restricted-assignment chores with arbitrary processing times.The proof uses the minimum-current-load eligible-machine rule and removes the job that first creates envy.Source: §D.3 · pp. 35–36
  • Weak EFX has an offline polynomial-time allocation, but no deterministic online algorithm guarantees it, even with m = 2 machines.The offline construction sorts jobs by non-increasing processing time before applying the greedy algorithm.Source: §D.3 · pp. 35–36

E Impossibility Results for Scheduling Objectives and General Valuations

For general valuations, no deterministic online algorithm can guarantee o(m)-Prop1 for restricted-assignment chores. With unit-size jobs, requiring α-Prop1 can increase the optimum makespan.

E.1 General Valuations Rule Out Sublinear Online Guarantee

  • No deterministic online algorithm guarantees o(m)-Prop1 for restricted-assignment chores with general valuations.The result is established by an adversarial instance.Source: §E.1 · p. 36

E.2 Fairness Can Be Incompatible with Makespan

  • Requiring α-Prop1 can increase the optimum makespan by a factor bounded below asymptotically, even for unit-size jobs.The construction forces at least N jobs onto d designated machines, while assigning both jobs of each non-designated machine there gives makespan 2 without the fairness requirement.Source: §E.2 · p. 37

Related papers

Loading 2610.08064v1…