| paper | Computing Efficient and Envy-Free Allocations under Dichotomous Preferences using SAT |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\ge0\) summing to \(1\), item kinds \(O\), rational supplies \(q_o\in[0,1]\), and a dichotomous formula \(\phi_\theta\) over \(O\) for each type, where \(Nq_o\) denotes identical indivisible copies of kind \(o\) at scale \(N\), decide whether there exists a rational table \(a_{\theta,B}\ge0\) for \(B\subseteq O\) satisfying \(\sum_B a_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:o\in B}a_{\theta,B}=q_o\), with \(a_{\theta,B}>0\) and \(\phi_\theta(B)=0\) implying that every used bundle \(B'\) satisfies \(\phi_\theta(B')=0\), and such that no feasible table weakly increases \(h_\theta=\sum_{B:\phi_\theta(B)=1}a_{\theta,B}\) for every type while strictly increasing it for some positive-mass type; output such a table if one exists.
A high-multiplicity fair-allocation model with agent types \(\theta\), masses \(\mu_\theta\), and identical indivisible copies of item kinds with normalized supplies \(q_o\); \(a_{\theta,B}\) is mass assigned whole bundle \(B\), with feasibility, typewise envy-freeness, and Pareto dominance defined through happy mass.
Theorem 1's bounded item-incidence promise is destroyed when a positive-mass type is replicated, and treating repeated copies through item kinds changes the original formula's bundle semantics, so the theorem's reduction does not automatically transfer.
fatal: False
It covers the fair-allocation existence question for Pareto-efficient and envy-free allocations under dichotomous preferences in a high-multiplicity regime; it leaves the Boolean hedonic-game result, SAT/CEGAR procedures, minimum-envy objectives, and empirical phase-transition claims outside the mirror.
My strongest mirror is the fair-allocation result, specifically Theorem 1. The theorem is proved in this paper, not merely cited: it states that deciding whether a Pareto-efficient and envy-free allocation exists for monotonic dichotomous preferences in logical form is \(\Sigma^p_2\)-hard, even when every preference is a positive 3DNF with at most four terms and every item occurs in at most three agents’ preferences. The paper’s membership argument and conclusion present the unrestricted problem as \(\Sigma^p_2\)-complete, but the named theorem itself asserts hardness.
The natural high-multiplicity setting is a large course, computing-resource, or service-slot allocation market. There may be \(N\) students or jobs but only a small catalogue of preference types: students in the same programme and year, or jobs with the same resource requirements, have the same dichotomous formula. A type \(\theta\) is therefore the complete preference description \(\phi_\theta\), together with any other parameters relevant to allocation. Its mass \(\mu_\theta\) is the fraction of the population having that type, with \(\sum_\theta\mu_\theta=1\). This is a sensible regime when \(N\) is in the hundreds of thousands while the number of types is perhaps tens or hundreds. The paper’s own citation of high-multiplicity fair allocation, Bredereck et al. [23], supports this regime rather than colliding with it.
The continuous problem I would put forward is \(\mathrm{EEF\mbox{-}PE}^{\mathrm{FA}}_\infty\).
An instance consists of:
A bundle is still an ordinary indivisible bundle \(B\subseteq O\): an agent receives whole item copies, not fractions. Let \(a_{\theta,B}\) be the mass of type-\(\theta\) agents receiving bundle \(B\). The allocation constraints are \(\sum_{B\subseteq O}a_{\theta,B}=\mu_\theta\) for every \(\theta\), and \(\sum_{\theta,B:o\in B}a_{\theta,B}=q_o\) for every item kind \(o\). Thus \(a\) is the normalized high-multiplicity version of integer allocation counts.
Write \(\phi_\theta(B)=1\) when type \(\theta\) is happy with \(B\). The allocation is envy-free when, for every \(\theta,\theta'\) and bundles \(B,B'\), \(a_{\theta,B}>0\) and \(\phi_\theta(B)=0\) imply that every bundle \(B'\) used with positive mass satisfies \(\phi_\theta(B')=0\). In words, an unhappy member of a type cannot coexist with any positively populated bundle that the type would prefer. This is the exact anonymous limit of the paper’s individual envy condition, not a weaker average-utility condition.
Define the happy mass of type \(\theta\) by \(h_\theta(a)=\sum_{B:\phi_\theta(B)=1}a_{\theta,B}\). Allocation \(a'\) dominates \(a\) if \(h_\theta(a')\ge h_\theta(a)\) for every type and the inequality is strict for at least one positive-mass type. The allocation is Pareto-efficient if no such \(a'\) exists. This aggregate formulation is equivalent to agentwise Pareto dominance after measure-preserving relabelling within each identical type, since utilities are dichotomous.
The question is: does there exist a feasible \(a\) satisfying both conditions, and, if so, output its rational bundle-mass table? At finite scale \(N\), this becomes the paper’s problem with \(N\mu_\theta\) agents of each type and \(Nq_o\) indivisible item copies. Hence the bridge is genuine: the continuous instance is the normalized high-multiplicity form, not merely a fractional allocation problem.
I expect this mirror to be Class A in the intended regime where the preference and item catalogues are fixed or moderately sized, even though the original problem is \(\Sigma^p_2\)-hard when the number of logically distinct agents grows. For a fixed catalogue, one can enumerate the finite support patterns induced by envy-freeness and solve the resulting rational configuration LPs. Pareto efficiency can then be checked by LP dominance tests. With \(2^{|O|}\) bundle configurations, the interesting general case has exactly the programme’s characteristic shape: an LP with exponentially many columns, whose tractability depends on a pricing problem over bundles satisfying or violating the dichotomous formulas.
This also identifies the boundary rather than hiding it. If \(|\Theta|\) and \(|O|\) grow with the input, the Boolean structure may reintroduce hardness. Theorem 1’s reduction uses many distinct agents and item identities, so its hardness may survive when the type catalogue grows linearly; that would be Class B or possibly Class C. The continuous mirror therefore tests whether the paper’s second-level hardness is caused by population multiplicity or by the logical allocation structure itself.
The main follow-up questions are whether a continuous EEF allocation can be rounded to an exact EEF allocation for sufficiently large \(N\), what additive envy is unavoidable when exact rounding fails, and whether bounded-term DNF admits an efficient pricing oracle. The phase-transition behaviour observed empirically in the paper also suggests studying continuous feasibility regions as functions of \(\mu\) and \(q\).
My weakest point is that the paper’s goods are individually named and indivisible, whereas the mirror groups repeated copies into item kinds and uses normalized supplies. A referee could regard that as introducing outcome-space continuity. The defense is that every finite approximation still contains only indivisible goods and whole bundles; only the counts of identical agents and repeated goods are normalized. If the authors insist that the item set remain fixed while the population becomes large, exact envy-freeness degenerates: almost everyone receives nothing and any useful item can create envy. For that narrow interpretation there is no convincing mirror. The case depends on accepting the standard high-multiplicity extension with repeated item copies, which is precisely the regime already validated by the high-multiplicity fair-allocation literature.
The strongest objection is that the proposed \(\mathrm{EEF\mbox{-}PE}^{\mathrm{FA}}_\infty\) is not actually the high-multiplicity limit of Theorem 1.
The theorem’s items are named objects occurring in named agents’ formulas. Its key restriction is that each item occurs in at most three agents’ preferences. If a positive-mass type \(\theta\) is replicated \(N\mu_\theta\) times, every item mentioned by \(\phi_\theta\) occurs in \(N\mu_\theta\) agents’ preferences, immediately destroying that restriction. Enforcing the restriction would force every item mentioned by a positive-mass type to have zero population incidence, leaving only a trivial instance.
The obvious repair is to give each replicated agent private copies of the relevant items. But then the reduction decomposes into independent local gadgets: the shared item identities that connect variable choices to clause checks have disappeared. Alternatively, retain shared item kinds and duplicate their supply. That gives a different valuation model. The original formula is defined on \(B\subseteq O\), whereas a repeated item kind requires preferences over multisets or count vectors. Whether \(p_o\) means “at least one copy,” “exactly one,” or “enough copies” is a new modelling choice. Clearing denominators therefore recovers a new repeated-goods problem, not an instance of the paper’s allocation problem.
Keeping the paper’s fixed item set is no better. With \(N\) agents and \(O(1)\) indivisible goods, only finitely many agents can receive nonempty bundles. For any positive-mass type that regards such a bundle as happy while the empty bundle is unhappy, envy-freeness fails: almost all clones receive the empty bundle and envy the recipient. The limit consequently either has no envy-free allocation or makes all relevant types unhappy, so the interesting fairness predicate collapses.
Thus the proponent has to scale both agents and goods and introduce symmetric item kinds with a new bundle semantics. That is a legitimate high-multiplicity fair-allocation extension, and the existing high-multiplicity literature supports its plausibility. But it is not a continuous mirror of the paper’s \(\Sigma^p_2\) result: it removes the named-item incidence structure responsible for the theorem and replaces the paper’s Boolean preference language by a new count-based one.
This is a serious objection to the claimed anchor, but it does not support the requested universal negative. The repaired repeated-goods problem could itself be worthwhile, even if it should be labelled an extension or re-modelling rather than a direct mirror. I would reject the proposed formulation as faithful to Theorem 1, but I could not honestly claim that no valuable continuous fair-allocation question exists for this paper.
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.