| paper | Truthful and Fair Mechanisms for Matroid-Rank Valuations |
| authors | Siddharth Barman, Paritosh Verma |
| venue | AAAI 2022 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper contains no numbered theorem, lemma, corollary, or proposition asserting polynomial-time solvability, hardness, FPT, or an approximation guarantee. Theorem 1 is a characterization, Theorem 2 an impossibility result, and Theorem 3 a mechanism property; the unnumbered polynomial-time footnote does not satisfy the stated computational criterion. The repeated-seat mass model is a plausible research direction, but it cannot supply the missing qualifying anchor.
fails bit a — no named computational result to mirror
The proposed mirror covers a high-multiplicity course-seat allocation problem with matroid-rank types, Lorenz objectives, and attempted fairness and coalition-truthfulness guarantees. It leaves the original finite-good strategic definitions without a direct continuum interpretation and supplies no qualifying computational result.
The strongest honest positive case is narrow. This paper offers a plausible high-multiplicity mirror of its fair-allocation mechanism, but it does not contain a qualifying ChoCo complexity anchor.
The numbered results are:
The only polynomial-time claim is an unnumbered footnote saying that PE is executable in polynomial time, attributed to Babaioff, Ezra, and Feige (2021). Thus, strictly speaking, the paper has no named computational-complexity anchor. It cannot support a Class A/B/C verdict without extending the programme’s notion of “computational result.”
If mechanism theorems are admitted as provisional anchors, my lead would be Theorem 3. A natural scenario is large-scale course allocation: \(N\) students, \(N\gg\tau\), with only \(\tau\) distinct matroid-rank preference types. Type \(t\) is the complete matroid \(M_t=(G,\mathcal I_t)\), including all substitutability information; \(\mu_t\) is the fraction of students of that type. There are \(Nq_g\) individually indivisible copies of each course-seat category \(g\). A normalized allocation is described by \(x_{t,S}\), the mass of type-\(t\) students receiving bundle \(S\), subject to
\[ \sum_{S\subseteq G}x_{t,S}=\mu_t \]
and
\[ \sum_{t,S:g\in S}x_{t,S}\le q_g. \]
At finite scale, \(Nx_{t,S}\) is integral and every seat is assigned to one student; \(x\) records only the high-multiplicity limit. The objective is to find a non-wasteful Lorenz-dominating allocation, with the same lexicographic tie-breaking as PE.
The continuous problem would be:
Given \(G\), the finite type set \(\mathcal T\), the mass vector \(\mu\), and per-capita supplies \(q\), compute an asymptotically implementable Lorenz-dominating allocation and determine whether the induced direct mechanism is Pareto-efficient, EF1, index-oblivious, and group strategy-proof against coordinated changes in reported type mass.
This is recognisably the paper’s problem: same matroid-rank valuations, same Lorenz/NSW objective, same PE mechanism, same EF1 and strategic guarantees. I would expect the allocation part to be Class A in this regime. The existing polynomial PE result, together with matroid exchange and type aggregation, suggests a polymatroid or configuration-optimization formulation whose input depends on \(m\), \(\tau\), and the encoding of the matroids rather than on \(N\). The new work would be proving the precise pricing, rounding, and strategy-proofness statements for the mass formulation.
A second, weaker mirror follows Theorem 2:
Does there exist a deterministic direct mechanism on \((\mathcal T,\mu,q)\) that is truthful, index-oblivious, Pareto-efficient, and gives almost every type-\(t\) agent her asymptotic maximin share?
Here the continuum MMS threshold can be defined as the limit of the finite MMS values in the \(N\)-scaled indivisible market. I would expect the impossibility to survive: Theorem 2’s obstruction is a local six-good valuation gadget, so one can try to replicate it across many identical cohorts. But this is a structural impossibility, not a Class B computational-hardness result, and the lifting is nontrivial.
The weakest point is decisive: if the goods remain literally the paper’s fixed finite set, a nonatomic population cannot receive nonempty indivisible bundles on positive mass. The proposed mirror therefore needs many repeated indivisible copies, which makes it a high-multiplicity repeated-goods version rather than a literal continuum of the paper’s original instance. Moreover, the paper itself supplies no numbered \(P\), NP-hardness, or parameterized-complexity theorem. So this is a credible research question inspired by Theorems 2 and 3, but only a provisional positive case for the continuization programme.
The strongest objection is a scope objection: this paper has no qualifying ChoCo complexity anchor. Theorem 1 is a characterization of truthful mechanisms, Theorem 2 is an impossibility theorem, and Theorem 3 is a group-strategy-proofness theorem. None states the complexity of a computational problem. The only polynomial-time statement is an unnumbered attribution that PE is executable in polynomial time, inherited from Babaioff, Ezra, and Feige. Thus the paper does not itself supply a Class A, B, or C problem for continuization.
Even granting mechanism theorems as provisional anchors, Theorem 3 does not survive as the proposed continuous object without changing several central features at once. With the paper’s fixed finite set of indivisible goods, an atomless population can give nonempty bundles to at most \(m\) agents. Almost every agent therefore receives the empty bundle. In finite approximations with \(n>m\), every agent’s MMS is \(0\), since every partition into \(n\) bundles contains an empty bundle. EF1 and MMS consequently lose the content they have in the paper.
The proposed repair—replicating course seats and writing an allocation as \(x_{t,S}\)—is sensible as a high-multiplicity assignment model, but it is not a continuum of the paper’s problem. It replaces the finite ground set of goods by a sequence of replicated ground sets or by multi-unit categories. That may be a worthwhile new fair-division problem, but Theorem 3 gives no result about it.
More importantly, the strategic guarantee does not have a nontrivial atomless interpretation. If the mechanism depends only on the reported mass vector \(\mu\), one agent’s report changes \(\mu\) by zero. Individual truthfulness is then vacuous: every report produces the same outcome. The paper’s group strategy-proofness quantifies over every finite coalition and requires every member to gain. A positive-measure coalition changing type mass is a different notion, not the continuum version of that definition. If one retains \(1/N\)-scale effects, one is studying a sequence of finite mechanisms and its rounding or stability properties, rather than a mechanism on a continuous society.
The type-mass allocation also forgets the assignment kernel needed to discuss strategic gains. Two allocations can have identical \(x_{t,S}\) but assign the bundles to different individuals. That distinction is irrelevant for aggregate welfare but essential to group strategy-proofness. Restoring it requires identities, an ordering, or a measurable assignment rule. The PE mechanism’s lexicographic tie-breaking by agent index is especially problematic: an atomless population has no canonical first agent, while adding an order makes identity part of the operative type and defeats the intended aggregation. Random or anonymous tie-breaking would change the deterministic mechanism and its theorem.
Theorem 2 is no stronger. Its contradiction depends on exactly six goods, two agents, and the forced allocation of the two special goods. Keeping those goods while increasing the population makes MMS collapse to zero. Replicating the six-good gadget privately across many cohorts merely produces a distribution of independent finite instances; the continuum is computationally inert. Sharing replicated goods destroys the proof’s forcing argument: the MMS values and scarcity relations change, and the claims that both agents must receive one of the two special goods no longer follow. Preserving the gadget would require finite bottlenecks or cohort labels, again introducing a new discrete structure. “Almost every type receives asymptotic MMS” also weakens the original universal guarantee precisely where the finite contradiction acts.
Theorem 1 has the same problem in miniature. Its gradualness conditions concern changing one agent’s valuation by deleting a good and bounding the change in that agent’s bundle size. In a mass model, one such report is a null perturbation, so the condition becomes vacuous. Replacing it with a Lipschitz or derivative condition in \(\mu\) would be an interesting new characterization, but not a continuous mirror of Theorem 1.
The honest limitation is that a replicated-seat market with many students sharing matroid preferences is a plausible high-multiplicity scenario. The negative case cannot prove that nobody could formulate a useful new paper around it. But every version that avoids degeneration changes at least one of the following: fixed goods into replicated capacities, individual incentives into positive-mass coalition manipulation, exact MMS into an asymptotic variant, or deterministic allocations into assignment kernels or lotteries. That is too much reconstruction to count this paper as supplying a worthwhile continuous mirror for ChoCo.
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.