Source-linked AI summary
Online House Allocation with Subsidy
Nicholas Teh, Saar Cohen, Karen Frilya Celine, Benjamin Yu, Michael J. Wooldridge
TL;DR
Classical house allocation assumes all houses are known before assignment, but practical arrivals are sequential and the one-house-per-agent constraint can force reassignment. The paper studies online recourse and subsidy-based fairness, including prediction-based allocation; it establishes both sharp limits and guarantees, including no bounded subsidy ratio even with two agents and four houses.
Problem
Classical house allocation assumes all houses are known before assignment, while sequential arrivals and the one-house-per-agent constraint require decisions and possible reassignment before future houses are known.
Source: §1 · pp. 1–2Method
The paper studies online allocation and recourse for subsidy-based fairness, and uses predictions of which houses should remain for the final matching.
Source: §1 · p. 2, §6.1 · p. 9Results
At n = 2, m = 4, no bounded total-subsidy competitive ratio exists; the paper also establishes a one-extra-house threshold for exact minimization and prediction-based recovery of the offline optimum when predictions are correct.
Source: §4.3 · p. 8, §6.1 · p. 9, §7 · p. 10Takeaways & Limitations
Matching-structure predictions recover the offline optimum when correct while providing robustness guarantees when inaccurate.
Source: §7 · p. 10Achieving the score-prediction guarantee may require a full n-step update, and exact optimality under correct predictions does not improve worst-case loss under inaccurate predictions.
Source: §6.2 · p. 10
Abstract
from arXiv · showhide
House allocation is a fundamental problem in which each agent is assigned exactly one house. While the classical model assumes that all houses are available before the allocation is computed, many practical settings require decisions to be made as houses become available over time. We introduce the online house allocation problem, where houses arrive sequentially and the algorithm must maintain an allocation without knowledge of future arrivals. Unlike online fair division, the one-house-per-agent constraint makes recourse an inherent part of the problem, as accepting a newly arrived house may require reassigning previously allocated houses. We study online house allocation under subsidy-based fairness, where monetary subsidies eliminate envy among agents. We show that envy-freeability can always be maintained online using bounded recourse and that reassignment chains of length linear in the number of agents are unavoidable in the worst case. In contrast, minimizing the total subsidy is fundamentally harder: no deterministic online algorithm against an adaptive adversary, and no randomized online algorithm against a non-adaptive adversary, admits a bounded competitive ratio, even for two agents and four houses. We complement these impossibilities by showing that exact online subsidy minimization is possible whenever there is at most one extra house beyond the number of agents, and that this guarantee is best possible with respect to the number of extra houses. Finally, we develop learning-augmented algorithms that recover the offline optimum under accurate predictions while providing explicit robustness guarantees when predictions are inaccurate.
1 Introduction
The paper recasts house allocation for sequential arrivals, when future houses are unknown and the one-house-per-agent constraint makes reassignment part of allocation. It studies recourse and subsidy-based fairness, with online guarantees, lower bounds, subsidy results, and prediction-based recovery.
1 Introduction
- Houses arrive sequentially, with values revealed on arrival, so allocations must be updated without knowing future houses.Unlike the offline model, decisions cannot wait until the full housing stock is known.Source: §1 · p. 1
- The one-house-per-agent constraint means accepting a new house can require reassignment chains, unlike online fair division.The paper measures recourse by the maximum length of such a chain, called flexibility.Source: §1 · p. 2
- Subsidies can make an allocation envy-free, and the paper asks how to maintain that fairness while minimizing total subsidy.It also studies standard economic efficiency under the same online matching constraint.Source: §1 · p. 2
1.1 Our Contributions
- Online envy-freeability is always maintainable through welfare-maximizing allocations and a single reassignment chain.The paper shows the chain-length requirement is linear in the number of agents and asymptotically tight.Source: §1.1 · p. 2
- No online algorithm has a bounded competitive ratio for minimum subsidy, even with two agents and four houses.The impossibility holds even when allocations may be freely reoptimized using all available houses.Source: §1.1 · p. 2
- Exact subsidy minimization is possible with at most one extra house, while beyond that threshold additive guarantees and prediction-based recovery remain possible.Structure-based predictions recover the offline optimum when correct and provide robustness guarantees when inaccurate.Source: §1.1 · pp. 2–3
1.2 Related Work
- The related offline literature studies subsidy-based envy-freeability, including the NP-hard minimum-subsidy problem of Choo et al., while this paper adds online arrivals and recourse.Halpern and Shah introduced envy-freeability for indivisible goods.Source: §1.2 · p. 3
- Online matching work studies recourse for matching quality, whereas this paper uses recourse to preserve individual subsidy-based fairness under cardinal utilities [69].Prior dynamic house-allocation models instead involve agents arriving and departing and trading houses.Source: §1.2 · p. 3
2 Preliminaries
The preliminaries define the online allocation model, its update limits, and subsidy-based fairness, then connect those concepts to welfare and efficiency criteria.
2 Preliminaries
- The model has a fixed set of agents and sequentially arriving houses; future houses and their utilities are unknown to the algorithm.The adversary may be adaptive, observing past decisions, or non-adaptive, committing to the full input in advance.Source: §2 · pp. 3–4
2.1 Recourse
- Recourse is constrained through chain updates, and k-flexibility bounds the number of agents in one update chain.Validity requires a complete allocation whenever at least n houses have arrived; discarded houses cannot return.Source: §2.1 · p. 4
2.2 Fairness Goal: Envy-Freeability via Subsidies
- Envy-freeability means some subsidy vector can make a complete allocation envy-free, and minimum total subsidy is measured against the best complete allocation.For a fixed set of n houses, an allocation is envy-freeable exactly when it is a maximum-weight perfect matching; this matching also attains the minimum subsidy for that support.Source: §2.2 · pp. 4–5
- Subsidy performance is evaluated by competitive ratio against the minimum subsidy, and intermediate allocations must remain envy-freeable although payments apply only to the final allocation.The ratio is defined for instances with positive optimum subsidy.Source: §2.2 · p. 5, §2.3 · p. 5
2.3 Efficiency Solution Concepts
- The paper also defines non-wastefulness and Pareto optimality as efficiency criteria for complete allocations.Welfare-maximizing allocations are envy-freeable, linking efficiency to the fairness goal.Source: §2.3 · p. 5
- The active max-weight chain algorithm chooses a maximum-welfare feasible allocation using active houses, breaking ties by minimizing changes from the prior allocation.Houses not used in the selected allocation are discarded.Source: §2.3 · p. 6
3 Envy-Freeability
The section shows that online envy-freeability can be maintained by preserving welfare maximization, then establishes worst-case lower bounds on the recourse needed for fairness and welfare.
3 Envy-Freeability
- A welfare-maximizing allocation among non-discarded houses can be maintained online through a single chain update, despite the matching constraint.The algorithm maximizes welfare among feasible allocations on active houses and uses tie-breaking to favor the current allocation.Source: §3 · p. 6
- Algorithm 1 is valid and n-flexible, and its final allocation maximizes utilitarian welfare and is therefore envy-freeable.The invariant is that a maximum-welfare allocation remains available without using previously discarded houses.Source: §3 · p. 6
3.1 Recourse Lower Bounds
- For deterministic algorithms against an adaptive adversary, guaranteeing envy-freeability requires chain flexibility at least λ_n, while n-flexibility suffices.The lower bound matches the upper bound for n = 2 and n = 3; no randomized lower bound or total-reassignment bound is claimed.Source: §3.1 · pp. 6–7
- For welfare maximization, n-flexibility is exact: no deterministic algorithm against an adaptive adversary can guarantee maximum welfare with any smaller chain limit.The lower bound applies for every n ≥ 2 and every k < n.Source: §3.1 · p. 7
4 Limits of Online Subsidy Minimization
Online subsidy minimization has a universal subsidy ceiling under normalized utilities, but this does not ensure a bounded ratio to the instance optimum. Welfare-oriented guarantees cannot solve that gap, and even subsidy-focused online algorithms face an unbounded-competitive-ratio barrier.
4.1 A Universal Subsidy Bound
- For normalized utilities, every complete envy-freeable allocation has total subsidy at most n −1.Algorithm 1 therefore has final subsidy at most n −1, but this universal ceiling does not compare it with OPT(I).Source: §4.1 · p. 7, §4.2 · p. 7
4.2 Incompatibility of High Welfare and Minimum Subsidy
- When m = n, Algorithm 1 is subsidy-optimal because any maximum-weight perfect matching with minimum envy-eliminating subsidies is optimal.Thus, the separation between welfare and subsidy minimization arises once extra houses are allowed.Source: §4.2 · p. 7
- With one extra house, any allocation achieving at least a fixed fraction ρ of maximum welfare can have subsidy arbitrarily larger than OPT(I), even with identical utilities.Taking ρ = 1 shows that welfare maximization, non-wastefulness, and Pareto optimality do not guarantee a bounded subsidy ratio.Source: §4.2 · p. 7
4.3 Unbounded Competitive Ratio
- Even with two agents and four houses, no deterministic algorithm against an adaptive adversary or randomized algorithm against a non-adaptive adversary has a bounded subsidy ratio.The impossibility holds even under a permissive update rule allowing reoptimization over currently available houses.Source: §4.3 · p. 8
- Because multiplicative guarantees fail online, the paper turns to additive loss and settings where exact subsidy minimization remains possible.Utilities are normalized to [0, 1]; uniform rescaling scales additive bounds but leaves multiplicative lower bounds unchanged.Source: §4 · p. 7, §4.3 · p. 8
5 Positive Subsidy Guarantees
Exact online subsidy minimization is achievable when there are at most one extra house, and that threshold is tight. Beyond it, the paper gives additive guarantees for identical utilities, including an optimal two-agent bound.
Exact Minimization with at Most One Extra House
- A deterministic polynomial-time n-flexible algorithm is subsidy-optimal whenever m ∈ {n, n + 1}, without knowing which sequence length will occur.The algorithm is valid for every input sequence.Source: §5 · p. 8
- Once two extra houses may arrive, no deterministic valid algorithm has a bounded competitive ratio, even for two agents with identical normalized utilities.The corresponding randomized impossibility holds against a non-adaptive adversary.Source: §5 · p. 8
Identical Utilities
- For two agents with identical normalized utilities, the optimal deterministic additive loss against an adaptive adversary is exactly 1/2.A valid 1-flexible algorithm attains this bound.Source: §5 · p. 8
- For arbitrary n with identical utilities, a deterministic valid 1-flexible algorithm is optimal when m = n and has additive loss at most (n −1)2/n when m ≥ n + 1.The bound is best possible for the underlying one-step selection constant, but the optimal additive loss for n ≥3 remains open.Source: §5 · p. 8
6 Algorithms with Predictions
The paper uses predictions about which houses should remain available for the final matching, rather than predictions of welfare values. Accurate predictions recover the offline optimum, while guarantees quantify prediction-error costs and lower bounds describe limits.
6 Algorithms with Predictions
- Predictions identify houses to retain for the final matching, and correct predictions recover OPT(I) while error bounds quantify additional subsidy.The paper considers score predictions for arbitrary utilities and cutoff predictions for common-quality utilities.Source: §6 · pp. 8–9
6.1 Score Predictions
- The score-keeping algorithm maintains a maximum-welfare allocation on the predicted support Bt, the top min{t, n} houses under the score ranking.The final score-selected set contains n houses; its error ηsc is the additional subsidy over OPT(I).Source: §6.1 · p. 9
- For arbitrary utilities, the score-keeping algorithm is deterministic, valid, and n-flexible, with subsidy OPT(I) + ηsc(p; I) and a normalized-utility ceiling of n −1.Correct scores have ηsc(p; I) = 0 and therefore recover the minimum subsidy.Source: §6.1 · p. 9
- A correct score prediction still gives the exact optimum under sufficiently small perturbations that preserve the final top-n ranking.If the score gap Γ(p*) is positive, perturbations smaller than Γ(p*)/2 preserve that ranking; no positive guarantee follows when Γ(p*) = 0.Source: §6.1 · p. 9
- For common-quality utilities, a single cutoff prediction suffices; a cutoff at least τ* gives subsidy at most min{OPT(I) + (n −1)αn−1(τ −τ*), n −1}.A correct cutoff recovers OPT(I); if |bτ −τ*| ≤ ε, using bτ + ε gives an added term at most 2(n −1)αn−1ε.Source: §6.1 · p. 9
6.2 Limits of Prediction-Based Guarantees
- Against an adaptive adversary, matching the score-prediction guarantee may require n-flexibility, and exactness on correct predictions cannot prevent incorrect predictions from causing loss at least n −1 −γ.For cutoff predictions, even a small underestimate can incur loss arbitrarily close to n −1.Source: §6.2 · p. 10
7 Conclusion and Future Work
The conclusion highlights the contrast between recourse, which can maintain envy-freeability, and subsidy minimization, which is severely limited online. The related-work sections distinguish this matching-and-subsidy setting from online fair division, temporal fairness, and other online allocation models.
7 Conclusion and Future Work
- The paper concludes that envy-freeability can be maintained online, but long reassignment chains are unavoidable; exact subsidy minimization is possible with one extra house, not two or more.Additive guarantees remain for identical utilities, and matching-structure predictions recover the offline optimum when correct.Source: §7 · p. 10
A.1 Online Fair Division
- Unlike online fair division with irrevocable bundle allocation, online house allocation may require replacing or reassigning previously allocated houses when a new house arrives.The one-house-per-agent constraint makes recourse intrinsic to the matching problem.Source: §A.1 · p. 16
A.2 Semi-Online Fair Division
- Prior semi-online fair-division predictions often summarize future values; these predictions instead identify houses to retain for the final matching.The distinction follows from unit demand: predictions guide which houses remain active rather than how goods are distributed among bundles.Source: §A.2 · pp. 16–17
A.3 Temporal Fair Division
- Unlike temporal fair division, future houses and utilities are unknown here; updates revise the matching, and subsidies are assessed only for the final complete allocation.Theorem 3.2 provides a welfare guarantee after every arrival, while temporal work may evaluate fairness across periods.Source: §A.3 · p. 17
A.4 Online Matching
- Compared with standard online matching, this setting permits bounded reassignment chains and targets envy-freeability and subsidy rather than matching cardinality.Matching with replacements is identified as the closest algorithmic comparison.Source: §A.4 · pp. 17–18
A.5 Fairness in Online Matching
- Online matching fairness work may share the one-item-per-agent constraint, but evaluates fairness across classes rather than individual agents.The cited models do not combine individual subsidy-based fairness with bounded reassignment chains.Source: §A.5 · p. 18
A.6 Additional Related Problems
- Other feasibility-constrained allocation work differs because this model combines unit demand, possible reassignment and discard, and envy-freeability through subsidies.The related-work discussion also distinguishes evolving matchings from coalition or cluster structures in sequential partitioning problems.Source: §A.6 · p. 18
C.1 Proof of Lemma 2.7
Lemma 2.7 characterizes envy-freeable allocations on a fixed n-house support through maximum-weight perfect matchings. Lemma 3.1 shows that welfare is monotone and submodular, so a set of houses whose removal leaves welfare unchanged can also be removed from any superset without changing welfare.
C.1 Proof of Lemma 2.7
- On an n-house support, an allocation is envy-freeable exactly when its matching is maximum-weight; every maximum-weight perfect matching with minimum envy-eliminating subsidies attains μ(S).The subsidy value is independent of which maximum-weight perfect matching is chosen.Source: §C.1 · p. 19
D.1 Proof of Lemma 3.1
- If removing D from S leaves F unchanged, removing D from any superset T of S also leaves F unchanged.The proof applies diminishing returns successively to the houses in D.Source: §D.1 · p. 19
- F(S) is the maximum weight of a matching between agents and houses in S, and is monotone and submodular.The proof derives submodularity by exchanging edges across alternating components of two optimal matchings.Source: §D.1 · pp. 19–21
D.2 Proof of Theorem 3.2
Algorithm 1 maintains a welfare-maximizing allocation after every arrival and finishes with a complete, envy-freeable allocation. Each update can be implemented as a chain of at most n agents.
D.2 Proof of Theorem 3.2
- The final allocation maximizes utilitarian welfare among complete allocations and is therefore envy-freeable; Algorithm 1 is valid and n-flexible.The proof establishes the stronger invariant that welfare is maximized after every round.Source: §D.2 · pp. 21, 22, 24
- Discarding previously unused houses does not reduce the maximum welfare achievable after the next arrival.This follows from the welfare-preserving deletion property applied to the houses discarded so far.Source: §D.2 · p. 22
- Each nontrivial update follows one alternating path containing the new house, so at most n agents change assignments.Agents outside the path retain their houses, and the path may end by discarding a house.Source: §D.2 · pp. 22–23
D.3 Proof of Proposition 3.3
The proofs establish linear recourse lower bounds for maintaining envy-freeability and guaranteeing welfare maximization against an adaptive adversary. They also bound minimum subsidies for complete envy-freeable allocations when utilities lie in [0, 1].
D.3 Proof of Proposition 3.3
- For m = n, any deterministic valid k-flexible algorithm with k < λn can be forced by an adaptive adversary to finish without an envy-freeable allocation.The adversary chooses the final house after observing the algorithm’s intermediate assignment.Source: §D.3 · pp. 24, 26
D.4 Proof of Proposition 3.4
- For every n ≥ 2 and k < n, no deterministic valid k-flexible algorithm against an adaptive adversary can always finish with a welfare-maximizing complete allocation.The adversary can reveal one additional house after the first n houses, forcing a chain of length n to reach the unique welfare optimum.Source: §D.4 · pp. 26–27
E.1 Proof of Lemma 4.1
- For a complete envy-freeable allocation with all utilities in [0, 1], the minimum total subsidy is at most n − 1.The proof constructs envy-eliminating subsidies, each at most 1, with at least one agent receiving zero.Source: §E.1 · p. 27
E.2 Proof of Theorem 4.2
Theorem 4.2 constructs an identical-utilities instance with n + 1 houses where every complete allocation attaining a fixed fraction of optimal welfare has subsidy more than any specified multiple of the optimum subsidy.
E.2 Proof of Theorem 4.2
- For fixed n ≥ 2, ρ ∈ (0, 1], and R > 0, some identical-utilities instance with m = n + 1, values in [0, 1], and OPT(I) > 0 makes every feasible complete a with W(a) ≥ ρW*(I) satisfy sub(a) > R · OPT(I).Source: §E.2 · p. 28
- Welfare at least ρW*(I) requires the value-1 house, but the subsidy-minimizing support omits it and has subsidy δ.Among supports containing the value-1 house, the least subsidy is (n − 1)(1 − δ), which exceeds δ for the chosen δ.Source: §E.2 · pp. 28–29
E.3 Proof of Theorem 4.3
For two agents with identical utilities, the proof rules out bounded competitive ratios for total subsidy under deterministic algorithms facing adaptive adversaries and randomized algorithms facing non-adaptive adversaries. It does so by making a permanently discarded house valuable to the offline optimum but unavailable to the online algorithm.
E.3 Proof of Theorem 4.3
- For n = 2 and m = 4, no deterministic algorithm against an adaptive adversary or randomized algorithm against a non-adaptive adversary has a bounded total-subsidy competitive ratio.The impossibility holds for identical utilities in [0, 1], even under the more permissive update rule.Source: §E.3 · p. 29
- For two agents with identical utilities, total subsidy equals the absolute difference between the common values of the two assigned houses.This lets the proof compare subsidy directly with the gap between support values.Source: §E.3 · p. 29
- As ε → 0, the deterministic adversary makes the offline optimum ε while every available online support has a gap of at least 1/2 − ε.The adversary releases a fourth house after the algorithm has permanently discarded one of the first three houses.Source: §E.3 · p. 29
- For a randomized algorithm, a non-adaptive adversary can choose a prefix house discarded with probability at least 1/3, yielding the same diverging gap as ε → 0.The lower bound persists under the permissive update rule, and therefore also holds for more restrictive rules, including 2-flexibility.Source: §E.3 · p. 30
F.1 Proof of Theorem 5.1
The theorem gives a deterministic polynomial-time n-flexible algorithm that is subsidy-optimal when m is n or n + 1, without needing to know in advance whether arrivals stop after n or n + 1 houses. The proof selects an optimal support and matching while ensuring updates use at most one reassignment chain of length n.
F.1 Proof of Theorem 5.1
- For m ∈ {n, n + 1}, a deterministic polynomial-time n-flexible online algorithm is subsidy-optimal without knowing whether arrivals stop after n or n + 1 houses.For m = n, the first n houses form the support and the allocation is a maximum-weight perfect matching on that support.Source: §F.1 · pp. 30–31
- After round n + 1, the algorithm rejects every later arrival, remains valid on every input, and is n-flexible.It assigns exactly min{t, n} houses after round t and therefore ends with a complete allocation whenever m ≥ n.Source: §F.1 · pp. 30, 32
- When house n + 1 arrives, the algorithm chooses the n-house support with minimum subsidy and a maximum-weight perfect matching on that support.Among optimal choices, it minimizes the symmetric-difference distance from the previous matching, using a fixed deterministic order to break remaining ties.Source: §F.1 · p. 31
- The transition at round n + 1 either rejects the new house or changes assignments along one alternating path of length at most n agents.The proof rules out any additional alternating cycles, so the path between the arriving house and the omitted old house is the only nonempty component.Source: §F.1 · pp. 31–32
F.2 Additive Guarantees for Identical Utilities
For identical utilities, the paper establishes a tight deterministic additive-loss guarantee for two agents and a general one-chain algorithm for any number of agents. It also gives an n + 1-house instance showing that the general bound cannot be improved as a support-selection guarantee.
F.2 Additive Guarantees for Identical Utilities
- For n = 2 and utilities in [0, 1], the optimal worst-case deterministic additive loss against an adaptive adversary is 1/2, attained by a 1-flexible algorithm.The algorithm repeatedly selects the available two-house support with minimum value gap; after round 3 that gap cannot increase.Source: §F.2 · pp. 32–34
F.3 A 1-Flexible Algorithm for Every Number of Agents
- For every n, a deterministic 1-flexible algorithm is subsidy-optimal when m = n and has additive loss at most (n − 1)^2/n when m ≥ n + 1.After round n, it chooses a minimum-subsidy n-house subset from the current support plus the new arrival, replacing at most one assigned house per update.Source: §F.3 · pp. 34–35
F.4 An n + 1-House Example
- For every n ≥ 2, there are n + 1 houses in [0, 1] such that every n-house support has subsidy at least (n − 1)^2/n.This shows the constant in the support-selection lemma cannot be reduced.Source: §F.4 · p. 36
G.1 Proof of Theorem 6.1
The proof establishes guarantees for score-keeping, including an exact subsidy characterization and bounded recourse, and examines score-prediction stability and a cutoff-based specialization for common-quality utilities. For cutoff predictions, shifting upward by the error bound enforces a one-sided condition; the resulting linear dependence on cutoff error is tight, whereas omitting the shift can cause near-maximal additive loss.
G.1 Proof of Theorem 6.1
- The score-keeping algorithm is deterministic, valid, and n-flexible, with final subsidy OPT(I) + ηsc(p; I), at most n − 1 when utilities lie in [0, 1].Each update changes assignments along at most one alternating path, yielding a chain update of length at most n.Source: §G.1 · pp. 36, 38
G.2 Small Changes to Score Predictions
- When Γ(p*) > 0, a score-prediction error below Γ(p*)/2 preserves the final top n houses and yields subsidy OPT(I).When Γ(p*) = 0, this argument provides no positive error bound.Source: §G.2 · p. 38
G.3 Cutoff Predictions for Common-Quality Utilities
- For common-quality utilities, minimum-subsidy support can be chosen as n consecutive houses in quality order, with μ(S) = Σ_{r=1}^{n−1} rαr(qr+1 − qr).A consecutive optimal support is determined by its largest quality, motivating a single cutoff prediction.Source: §G.3 · pp. 39–40
- For common-quality utilities with utilities in [0, 1], the cutoff algorithm is deterministic, valid, and n-flexible, guarantees subsidy at most n − 1, and recovers OPT(I) for a correct cutoff.Overestimating a correct cutoff increases subsidy by at most an amount proportional to the prediction error.Source: §G.3 · p. 41
- A normalized common-quality instance attains additive loss (n −1)αn−1ε when τ* = 0 and the cutoff algorithm predicts τ = ε, for αnε ≤ 1.The instance has n houses of quality 0 and one of quality ε.Source: §G.3 · p. 42
- Without the upward shift, even a very small underestimate of a correct cutoff can produce additive loss arbitrarily close to n −1.This shows the shift is necessary for a two-sided error guarantee.Source: §G.3 · p. 42
G.4 Proof of Theorem 6.2
The proof shows that no deterministic valid k-flexible algorithm with k < n can always minimize subsidy exactly, even with score predictions and only n + 1 houses. The adversary forces an update that must reassign all n agents.
G.4 Proof of Theorem 6.2
- For every n ≥ 2 and k < n, no deterministic valid k-flexible algorithm given arriving-house scores guarantees exact subsidy minimization when m = n + 1.The guarantee fails against an adaptive adversary, even when score predictions are available.Source: §G.4 · p. 42
- The adversary can force the first n houses to be assigned in their unique maximum-weight matching, then make the optimal final support require a different complete matching.The proof uses increasing house qualities to make the matching unique; a continuation with a sufficiently high-value house keeps the original n houses as the top n support.Source: §G.4 · pp. 42–43
- The required update assigns the arriving house through agents n, n − 1, …, 1, so its chain length is n and any k < n algorithm cannot perform it.The resulting optimal support is the shifted set of houses, with each agent assigned the next house in the arrival order.Source: §G.4 · p. 43
G.5 Proof of Theorem 6.3
Theorem 6.3 shows that exactness on correct predictions does not prevent nearly n − 1 additive loss on an incorrect prediction. The proof uses adversarial continuations, and a separate result shows that even a tiny cutoff underestimate can incur nearly that loss.
G.5 Proof of Theorem 6.3
- For every γ > 0, an exact-on-correct-predictions deterministic algorithm has an identical-utilities instance with values in [0, 1] and an incorrect prediction causing loss at least n − 1 − γ.This lower bound applies to either the cutoff or score prediction model.Source: §G.5 · p. 44
- A shared prefix lets the adaptive adversary choose between a continuation where the prediction is correct and one where it is incorrect, while determinism preserves the allocation after the prefix.For cutoff predictions, the stopped instance leaves the algorithm with n − 1 zero-quality houses and one high-quality house; the score-prediction proof uses the same arrival sequence.Source: §G.5 · pp. 44–45
G.6 A Small Underestimate Can Be Costly
- For every ε-bar > 0 and γ > 0, a cutoff underestimate of at most ε-bar can cause additive loss at least n − 1 − γ.The result is for normalized identical-utilities instances with a correct cutoff τ* and prediction τ < τ*.Source: §G.6 · p. 46