| paper | Achieving Envy-Freeness with Limited Subsidies under Dichotomous Valuations |
| authors | Siddharth Barman, Anand Krishna, Yadati Narahari, Soumyarup Sadhukhan |
| venue | IJCAI 2022 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given a finite slot catalogue \(G\), rational masses \(\mu_t\) over complete dichotomous valuation types \(v_t\), and rational per-capita capacities \(\kappa_g\) for repeated indivisible slot copies, construct a mass allocation \(x_{t,B,p}\ge0\) over integral bundles \(B\) and subsidies \(p\in\{0,1\}\) satisfying \(\sum_{B,p}x_{t,B,p}=\mu_t\), \(\sum_{t,B,p}x_{t,B,p}B_g=\kappa_g\), and \(v_t(B)+p\ge v_t(B')+p'\) whenever \(x_{t,B,p}>0\) and \(x_{u,B',p'}>0\); determine whether this can be done exactly in time polynomial in the catalogue, type, capacity, and encoding sizes without expanding the clone population.
A high-multiplicity capacitated indivisible-goods model in which \(\tau\) complete dichotomous valuation types carry masses \(\mu\), integral bundle classes consume repeated slot capacity, and \(x\) assigns type mass to bundles with binary subsidies under envy-freeness, without a welfare or subsidy-minimization objective.
Even with the exact clone correspondence, it remains unresolved whether arbitrary value-oracle dichotomous valuations admit a compact representation or separation procedure for the potentially exponential support of integral bundle classes.
fatal: False
The mirror targets Theorem 4's existence and polynomial-time construction of an envy-free solution with \(p_i\in\{0,1\}\); it leaves the cited minimum-subsidy hardness, prior characterization results, and the future EF1 direction outside its scope.
The strongest honest case is a single algorithmic mirror, anchored in Theorem 4, which is proved in this paper. The theorem states that for every discrete fair-division instance with dichotomous valuations, an envy-free allocation with subsidies \(p_i\in\{0,1\}\) exists and can be computed in polynomial time using value oracles. The paper has no numbered NP-hardness theorem of its own; the cited hardness of minimum-subsidy optimization is not an anchor here.
My lead problem is Dichotomous Envy-Free Subsidy Allocation\(_\infty\).
The natural regime is the paper’s own scheduling example: a large employer assigns repeated indivisible time-slot positions to a large workforce. There are \(N\) employees but only \(\tau\ll N\) complete scheduling types. A type specifies the employee’s entire dichotomous valuation function, including contiguity, shift-rotation, and time-of-day effects; additivity, submodularity, and subadditivity are not assumed. The population is represented by rational masses \(\mu_t\), where \(\mu_t\) is the fraction of employees of type \(t\). Time slots remain indivisible. To avoid the degenerate situation in which finitely many goods are assigned to a vanishing fraction of an ever-growing population, the application has repeated slot copies or parallel positions, represented by integer capacities. This is still allocation of indivisible goods, not fractional assignment of a good.
Formally, an instance consists of a finite slot catalogue \(G\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita slot supplies \(\kappa_g\), and dichotomous valuation functions \(v_t\). An integral bundle \(B\) is a bundle of indivisible slot copies. The decision variable is \(x_{t,B,p}\ge 0\): the mass of type-\(t\) employees receiving bundle \(B\) and subsidy \(p\in\{0,1\}\). It must satisfy
\( \sum_{B,p}x_{t,B,p}=\mu_t \) for every type \(t\),
and
\( \sum_{t,B,p}x_{t,B,p}\,B_g=\kappa_g \) for every slot category \(g\), with all available goods assigned.
The plan is envy-free if, whenever \(x_{t,B,p}>0\) and \(x_{u,B',p'}>0\),
\( v_t(B)+p\ge v_t(B')+p'. \)
The task is to output such a mass allocation and binary subsidy assignment. Its primary objective is constructive feasibility—exact envy-freeness with per-agent subsidy at most \(1\)—rather than welfare maximization. A natural follow-up would minimize total subsidy mass among these feasible plans, but that optimization problem is not what Theorem 4 proves.
This is a faithful continuation of the paper’s question. The paper explicitly motivates dichotomous valuations with indivisible time slots, employees, and subsidies interpreted as bonuses. Replacing “\(16.8\%\) of employees have scheduling pattern \(t\)” by \(\mu_t\) changes the population representation, not the fairness criterion, valuation domain, or indivisibility of goods. For rational masses, a common denominator \(N\) expands the instance into \(N\mu_t\) employees of type \(t\) and the corresponding integer number of slot copies. Applying Theorem 4 and aggregating the resulting allocation gives a feasible \(x\). Conversely, any rational mass plan can be disaggregated into a finite clone instance. Thus the high-multiplicity bridge is exact at the level of rational instances.
I would provisionally expect this problem to be Class A. Theorem 4 already supplies polynomial-time machinery in the number of named agents: maximum-weight matchings, envy-graph shortest paths, and the EXTEND and FINDSINK routines. The continuous question is whether those routines can be batched over repeated types and repeated goods. Maximum-weight matching should become a type–bundle transportation problem; envy-graph computations should operate on occupied type–bundle classes; and identical slot copies should be processed in batches rather than one at a time. The desired result would be an exact algorithm polynomial in \(m\), \(\tau\), and the encoding length of \(\mu\) and the capacities, without expanding \(N\) employees.
That compression theorem is not in the paper, so this is a genuine ChoCo research question rather than a claimed corollary. It also generates useful descendants: minimum total subsidy mass, rounding continuous solutions to finite populations, approximate masses, strategic reporting by positive-mass type coalitions, and the effect of succinct versus oracle representations of dichotomous valuations.
The weakest point is that Theorem 4’s proof is organized around named agents and their individual bundles. Even when two employees have the same valuation type, they may receive different bundles, so the relevant state may be a large collection of type–bundle classes rather than merely \(\tau\) types. An arbitrary value oracle could conceal exponentially many such patterns. If that support cannot be compressed, the mirror may be continuum-specifically hard—or merely fail to improve on the finite algorithm. The fixed-good limit is also genuinely bad: with finitely many one-off goods and \(N\to\infty\), almost every employee receives nothing. The repeated-slot scheduling regime is therefore essential, not cosmetic.
Still, the positive case survives that objection: it preserves the paper’s exact fairness problem, its arbitrary dichotomous valuation model, its indivisible goods, and its subsidy semantics, while replacing named-agent multiplicities by a distribution over complete employee types. It covers Theorem 4 emphatically; it does not claim to continuize the paper’s cited minimum-subsidy hardness or its future EF1 direction.
The strongest case against the mirror is that Theorem 4 is fundamentally about assigning a finite set of indivisible goods to named agents. If the goods remain fixed while the population grows, only finitely many agents receive goods, hence almost every agent has the empty bundle in the continuum limit. The bundle-allocation problem then disappears on a positive-mass scale; subsidies, rather than allocation, determine envy-freeness. This is a genuine continuum degeneracy.
The proposed repair—scaling the number of slot copies with the population—avoids that degeneration only by changing the object. In the continuum limit, the copies of each slot category become divisible capacity, and the allocation is described by \(x_{t,B,p}\), a fractional distribution over bundles. The indivisibility survives only in the finite clone approximations, not in the limiting resource. For arbitrary dichotomous valuations this also creates an exponential allocation state space: equal valuation types can be split among exponentially many distinct bundles, and the paper’s value-oracle model supplies no pricing or separation procedure over those bundles. Thus \(\mu\) does not yield a compact continuous society; it is accompanied by a potentially exponential measure over allocation states.
Restricting valuations to copy-symmetric or additive scheduling types makes batching more plausible, but it gives up precisely the paper’s notable generality—binary marginals without additivity, submodularity, or subadditivity. One then obtains a new capacitated allocation model whose relation to Theorem 4 is mainly motivational. Conversely, retaining arbitrary valuations leaves no evident finite-dimensional continuization beyond expanding a large cloned instance in disguise.
That is the best substantive objection, but it does not defeat the proponent’s stronger formulation. With a fixed finite slot catalogue, repeated copies, complete valuation types, and rational masses, the clone-and-aggregate correspondence is exact: clearing denominators gives a finite instance to which Theorem 4 applies, while any rational mass allocation can be disaggregated. The goods remain indivisible in every finite realization, and repeated cohorts of employees with identical scheduling preferences are a credible high-multiplicity regime. The fact that the aggregate allocation may need many bundle classes is a computational obstacle, not a modelling invalidity.
Nor can the stronger alternative of minimizing total subsidy mass be dismissed: it is closely tied to the paper’s motivation and may produce an even more natural continuous optimization problem. The absence of an immediate compressed algorithm is exactly the sort of question the programme is meant to investigate.
So I cannot honestly defeat this anchor universally. The fixed-good limit is bad, and the scaled-good version risks becoming an exponential fractional allocation problem rather than a clean \(\tau\)-type mirror. But the repeated-slot, high-multiplicity scenario is sufficiently faithful and plausible that Theorem 4 survives. The negative case is therefore weak; the paper should be greened on this anchor.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.