| paper | Approximating APS Under Submodular and XOS Valuations with Binary Marginals |
| authors | — |
| venue | AAMAS 2024 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given an explicitly represented finite indivisible-good set \(G\), a population scale \(N\), a rational distribution \(\mu\) over complete submodular valuation types whose marginal values lie in \(\{0,1/2,1\}\), and a target type \(t\) with \(N\mu_t\in\mathbb{Z}\), decide whether \(\operatorname{MMS}_{N,t}(G)=\max_{(S_1,\ldots,S_N)\in\Pi_N(G)}\min_{j\in[N]}v_t(S_j)\ge q\), or approximate this value within a factor better than \(5/6\), without expanding the \(N\mu_t\) identical agents. The one-type case \(\mu=\delta_t\), with \(3N\) goods and the paper’s ternary valuation, is the hardness instance.
A high-multiplicity fair-division model with indivisible goods \(G\), population mass \(N\mu_t\) for each complete valuation type \(t\), and no fractional goods: the decision variable is an \(N\)-way integral partition or its type-compressed representation, and the objective is the target type’s maximin-share value.
Theorem 5.1’s point-mass society \(\mu=\delta_t\) carries little population heterogeneity, while the valuation and goods grow with the encoded triple system, so the mirror is primarily a high-multiplicity restatement whose substantive hardness lives in the goods.
fatal: False
The mirror covers the MRF \(\operatorname{APS}=\operatorname{MMS}\) structure and APS-welfare algorithm in Theorems 3.1–3.2 as a proposed high-multiplicity extension, and the ternary-submodular MMS hardness of Theorem 5.1 and its APS corollary. It leaves the binary-XOS bounds, approximation algorithm, and impossibility results of Theorems 4.1–4.3 without a comparably strong mirror.
The strongest honest mirror is a high-multiplicity fair-division model. The paper is unusually suitable for this because its agents are already described by structured valuation types, and its central fairness notions are defined for each agent from that type.
I would not claim that the price vector in the APS definition makes the paper itself continuous. That is continuity in an auxiliary optimization problem, not continuity of the population. The mirror instead replaces the named agent list by a distribution over complete valuation types.
Let \(G\) be the finite set of indivisible goods, let \(\mathcal T\) be a finite set of valuation types, and let \(\mu\) be a rational distribution over \(\mathcal T\). A type includes the entire valuation representation: for an MRF, its matroid; for an XOS valuation, its additive clauses or oracle; and all other parameters relevant to the agent. Let \(N\) be the population scale, with \(N\mu_t\) agents of type \(t\). The relevant regime is \(N\) large, \(|\mathcal T|=\tau\ll N\), and typically \(|G|=\Theta(N)\), so that the problem does not collapse because there are far fewer goods than agents.
Goods remain indivisible. A type-level allocation can be represented by integers \(y_{t,S}\), where \(y_{t,S}\) is the number of type-\(t\) agents receiving the whole bundle \(S\subseteq G\). Thus
\[ \sum_{S\subseteq G} y_{t,S}=N\mu_t \]
for each type \(t\), and
\[ \sum_{t\in\mathcal T}\sum_{S\ni g}y_{t,S}=1 \]
for every good \(g\). This is merely a compressed representation of an allocation to indistinguishable agents; it does not split goods or give fractional value to a bundle.
For a type \(t\), define
\[ \operatorname{APS}_N(t) = \min_{\substack{p\ge 0\\ \sum_{g\in G}p_g=1}} \; \max_{\substack{S\subseteq G\\ \sum_{g\in S}p_g\le 1/N}} v_t(S). \]
The continuous-population computational question is whether one can compute APS-feasible allocations, or optimize their welfare, from \((N,\mu)\) and the \(\tau\) types without expanding the population into \(N\) named agents. This is the high-multiplicity version of the paper’s problem. Exact indivisibility requires \(N\mu_t\in\mathbb Z\); the genuinely new complexity question is whether the running time can depend on \(\log N\), rather than linearly on \(N\).
My lead anchor is Theorem 3.2, proved in this paper, using the cited algorithmic result of [8]. It states that for MRF valuations one can compute an allocation that gives every agent at least her APS and simultaneously maximizes social welfare. The structural result behind it, Theorem 3.1, is also proved here: for every MRF, \(\operatorname{APS}=\operatorname{MMS}\).
I would call the corresponding problem HM-MRF-APS-Welfare:
Given \(G\), \(N\), a distribution \(\mu\) over MRF types, and a welfare threshold \(W\), decide whether there exists a type-level allocation \(y\) satisfying the allocation constraints above, such that every type-\(t\) agent receiving \(S\) has
\[ v_t(S)\ge \operatorname{APS}_N(t), \]
and
\[ \sum_{t,S} y_{t,S}v_t(S)\ge W. \]
The optimization version asks for the maximum such welfare and an allocation attaining it.
I expect this mirror to be Class A, although that extension is not proved by the paper. The reason is not merely that the original theorem is polynomial. The proof exposes the relevant structure: APS equals MMS, the capped valuation remains a matroid rank function by Lemma 3.1, and the key existence argument is matroid-union/base-packing machinery. Repeated copies of the same matroid are exactly the kind of structure that high-multiplicity algorithms should compress. A plausible route is a multiplicity-aware matroid-union or polymatroid optimization algorithm whose dependence on the population is logarithmic rather than linear.
The regime is also credible. The paper itself mentions public housing and course-seat assignment. One can have millions of students or applicants but only a small number of complete eligibility and substitutability patterns: students in the same programme, cohort, or geographic category may share the same matroid-rank valuation over course seats or housing units. The type is not just a preference ranking; it includes every feature affecting value, as required by high multiplicity. The authors would recognize the mirror as their same fair-allocation problem with the agent list compressed into cohorts.
The main questions generated by this anchor are whether Theorem 3.2 can be made polynomial in \(m,\tau,L,\log N\); whether this remains true for arbitrary heterogeneous MRF types; and whether the welfare-maximization part, rather than merely APS feasibility, admits a compact type-level certificate. If the answer is yes, this would be a particularly clean continuization result: the paper’s exact APS theorem would become a genuine high-multiplicity algorithmic theorem.
My second anchor is Theorem 5.1, proved here. It states that computing MMS within a factor better than \(5/6\) is NP-hard for submodular valuations with marginal values in \(\{0,1/2,1\}\). The paper then notes the corresponding APS hardness using Claim 2.1. This gives a much more secure mirror, because the hardness construction already uses identical valuations.
The corresponding problem is HM-Ternary-MMS:
Given a population scale \(N\), a distribution \(\mu\) over submodular valuation types with marginal values in \(\{0,1/2,1\}\), and a target type \(t\), compute
\[ \operatorname{MMS}_N(t) = \max_{(S_1,\ldots,S_N)\in\Pi_N(G)} \min_{j\in[N]}v_t(S_j), \]
or decide whether this value is at least a threshold \(q\). A solution is an \(N\)-way partition of the indivisible goods, or an approximation to the optimum. The one-type special case has \(\mu_t=1\), so every member of the large population shares the same complete valuation.
The expected classification is Class B: hardness transfers from the discrete problem. Theorem 5.1 reduces from 3-D-MATCHING using \(N=r\) identical agents and \(3r\) goods. The single valuation type is
\[ v(S)= \begin{cases} 1 & |S|=1,\\ 2 & |S|=2,\\ 5/2 & |S|=3\text{ and }S\notin T,\\ 3 & |S|=3\text{ and }S\in T,\\ 3 & |S|\ge 4. \end{cases} \]
The MMS value is \(3\) exactly when the matching instance has a solution and is at most \(5/2\) otherwise. Hence an approximation factor better than \(5/6\) distinguishes the two cases. The combinatorics live in the goods and the triple system, not in population multiplicity. The population is already maximally high-multiplicity: one type and \(N\) interchangeable agents. This is precisely the kind of result the programme’s trichotomy predicts should survive continuization.
The weakest point is that fair division with a literal nonatomic continuum of agents and a fixed finite set of indivisible goods is not a sensible limit: almost all agents would receive nothing. I therefore would not sell this as a fluid limit with \(N=\infty\) and fixed \(G\). The defensible mirror is the programme’s high-multiplicity version: population composition is represented by \(\mu\), agents are indistinguishable within type, and \(N\) and the number of goods grow together. The other weakness is that Theorem 3.2’s polynomial algorithm is polynomial in the explicitly listed number of agents; its compressed dependence on \(\log N\) remains an open question. That limits the tractability claim, but it does not undermine the mirror itself. Theorem 5.1 remains a robust hardness anchor.
I would leave Theorem 4.3 as a follow-up rather than a third anchor. Its \(0.1222\)-APS algorithm gives a natural binary-XOS population problem, but the theorem’s runtime is stated for explicitly listed agents, while its \(0.5\) impossibility uses only three agents. The MRF exact result and the ternary-marginal hardness result provide a cleaner and stronger positive case.
The strongest negative case is that fair division has no stable population-only limit. Here \(n\) is not merely the number of agents: it also determines the fairness benchmark. APS gives each agent budget \(1/n\), while MMS requires an \(n\)-way partition. With a fixed set \(G\) of indivisible goods, the limit is degenerate. For \(n>|G|\), uniform prices make every nonempty good unaffordable, so \(\operatorname{APS}=0\); MMS likewise has empty bundles and is \(0\) for the paper’s normalized valuations. The fairness constraint then disappears.
The proponent’s repair—scale the goods with \(N\)—is more credible, but weakens Theorem 3.2 as a continuization. A matroid type is then a valuation over a changing, explicitly named ground set \(G_N\), not a stable population type. If goods are repeated by class, one obtains a new capacitated resource model and generally loses the arbitrary item-level matroid structure. If goods remain indivisible, the variables \(y_{t,S}\) must remain integral; allowing them to be real masses fractionally allocates goods and is no longer the paper’s problem. Thus the proposed HM-MRF-APS-Welfare is either a compressed finite allocation problem or a newly designed replicated-resource model. The paper gives no multiplicity-aware theorem, and the suggested logarithmic-\(N\) matroid-union algorithm is only conjectural. This makes Theorem 3.2 a fragile anchor, though not an impossible research direction.
Theorem 5.1 is harder to defeat. Its reduction already has identical valuations, so it passes the high-multiplicity test in the strongest formal sense: one valuation type is repeated \(N\) times. The natural objection is that with fixed goods the benchmark vanishes, while in the reduction the number of goods grows as \(3N\) and the common valuation itself changes with an arbitrary triple system \(T\). Hence \(\mu=\delta_t\) carries no population information; all substantive structure lies in the growing indivisible-goods instance.
But that objection does not survive the programme’s rules. A point mass is an admissible high-multiplicity society, resources may scale with population, and hardness in the goods or agenda is explicitly allowed as Class B rather than being dismissed as an inert restatement. Theorem 5.1 therefore supplies a legitimate continuous-population question: does the \(5/6\) APS/MMS hardness remain under a type-compressed representation? In fact, the reduction strongly suggests that it does.
So the honest negative case can downgrade Theorem 3.2 as a speculative and semantically delicate mirror, but it cannot defeat Theorem 5.1. Since one surviving anchor is enough, the universal claim that no worthwhile continuous mirror exists is not defensible under ChoCo’s stated standard.
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.