| paper | Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule |
| authors | — |
| venue | AAAI 2023 |
| filed under | voting · combinatorial |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given a connected graph G and a rational distribution over complete weak edge-ranking types, find a minimum-cardinality H subset of E such that every positive-mass type has an MST of G contained in H.
Types are complete weak rankings of edges; \(\mu_t\) is their population mass; the decision variable is an indivisible edge set \(H\); the objective is to minimize \(|H|\); type \(t\) is satisfied when \(H\) contains one of its MSTs.
Because universal satisfaction makes the distribution masses irrelevant beyond support, the mirror may be only a support-compressed finite constraint problem; the mass-sensitive quota repair is outside the paper and loses its submodular proof.
fatal: False
Covers the MMCP results in Theorems 1, 2, 3, and 4 for supported ranking types, while leaving the omitted submodular-cost and matroid-rank extensions and quota-based partial satisfaction outside.
The strongest honest mirror is a population version of MMCP in which roads remain indivisible and only the population is continuized.
Let \(G=(V,E)\) be the road graph. A type \(t\) is a complete weak ranking \(\rho_t\) of the edges; this is enough because the paper’s Lemma 1 shows that the set of MSTs depends only on the ranking, not on the particular consistent cardinal weights. A society is a rational distribution \(\mu\) over \(\tau\) such types. For \(H\subseteq E\), write
\[ \operatorname{sat}_t(H)=1 \]
if \(H\) contains some MST of \(G\) under \(\rho_t\).
My lead problem is Continuous Multiagent MST Cover (\(\mathrm{MMCP}_\infty\)):
Given \(G\), the supported types \((\rho_t,\mu_t)_{t=1}^{\tau}\), and \(\sum_t\mu_t=1\), find a set of roads \(H\subseteq E\) minimizing \(|H|\) subject to
\[ > \sum_{t=1}^{\tau}\mu_t\operatorname{sat}_t(H)=1. > \]
Equivalently, every positive-mass type must have at least one of its MSTs contained in \(H\).
This is exactly the paper’s “please every agent” requirement, expressed for a distribution. It does not fractionalize roads or trees: the action remains the construction of a subgraph. That is appropriate here, since the programme continuizes the population, not the outcome.
A plausible high-multiplicity regime is a large network provider serving millions of repeated customer or service units. Units with the same accessibility, reliability, environmental, or maintenance profile share one edge-ranking type. The number of units \(N\) can be enormous while the number of distinct profiles \(\tau\) is moderate. The downward dictionary is immediate: group the \(N\) agents by type and set \(\mu_t=n_t/N\). Conversely, any rational \(\mu\) can be expanded into a finite population with \(D\mu_t\) copies of type \(t\), for a common denominator \(D\). For the exact all-types requirement, this expansion preserves the feasible sets and optimum exactly.
The lead anchor is Theorem 4, proved in this paper. Its \(O(\ln k)\)-approximation algorithm becomes an \(O(\ln \tau)\)-approximation algorithm for \(\mathrm{MMCP}_\infty\): discard zero-mass types, take one representative agent for each supported type, and run Algorithm 3. The proof carries over directly. Define
\[ f_t(H)=\max_{T\in \operatorname{MST}(G,\rho_t)}|T\cap H| \quad\text{and}\quad F(H)=\sum_{t=1}^{\tau}f_t(H). \]
The paper’s Lemma 2 supplies a polynomial-time oracle for each \(f_t\), and Lemma 3 proves submodularity. The greedy algorithm therefore returns a feasible \(H\) with
\[ |H|\leq H_\tau\cdot \mathrm{OPT}=O(\ln \tau)\mathrm{OPT}. \]
I would classify this anchor as tractable in the approximation sense, with the exact optimization problem lying on a hardness boundary. The paper’s Theorem 2, stated here with its proof deferred to the authors’ full version, gives the matching \((1-o(1))\ln \tau\) barrier on uniform-support instances. Thus the continuous mirror preserves the paper’s meaningful approximation landscape rather than making the problem artificially easy.
A second, narrower anchor is Theorem 1, proved here by reduction from Set Cover. Define Binary-\(\mathrm{MMCP}_\infty\) to be the same continuous problem, restricted to types whose edge weights are binary, \(w_t(e)\in\{0,1\}\). The question is to find the minimum-size \(H\) containing an MST for every positive-mass binary type. The Set Cover reduction is unchanged: assign positive mass to the \(p+1\) types used in the reduction, and interpret selected up-edges as selected sets. Replicating every type arbitrarily many times produces a genuinely high-multiplicity population without changing the optimum.
Hence Binary-\(\mathrm{MMCP}_\infty\) is NP-hard, with hardness transferring from the discrete problem. The combinatorics live in the edge structure and the variety of supported preference types, not in the number of named agents. This is a Class B mirror, and that is a legitimate positive result: the continuous formulation identifies which hardness survives high multiplicity instead of pretending that continuization must dissolve every obstruction.
A third worthwhile, non-padding anchor is Theorem 3, also proved in this paper. Define Perfect-MST-\(\infty\) as follows:
Given \(G\) and a distribution over edge-ranking types, decide whether there exists a spanning tree \(T\) that is an MST for every positive-mass type; if so, output such a \(T\).
Algorithm 2 applies after replacing the agent list by the supported type list: sort edges lexicographically by their \(\tau\)-dimensional rank vectors, run Kruskal, and test whether the resulting tree is an MST for every supported type. Theorem 3 says this returns a common MST exactly when one exists. Thus Perfect-MST-\(\infty\) is in P, with running time polynomial in \(|V|,|E|,\tau\). This is a clean Class A mirror of the paper’s exact tractable special case.
The authors should recognise these mirrors as their problem. The graph, the public construction decision \(H\), the “one ideal MST per stakeholder type” satisfaction notion, the cardinality objective, and the ordinal-information model are all unchanged. The only replacement is that a list of named agents becomes a distribution over repeated preference types. I would not claim to mirror the paper’s omitted submodular-cost and matroid-rank extensions here, although the same population replacement is available for them.
The weakest point is that the exact all-agents requirement makes \(\mu\) matter only through its support. A society with masses \((0.99,0.01)\) and one with \((0.5,0.5)\) have the same feasible solutions if their supports coincide. If a referee requires mass to affect the optimization continuously, this may look like a compressed finite MMCP rather than a genuinely mass-sensitive model. The natural repair is the generated family
\[ \min |H| \quad\text{s.t.}\quad \sum_t\mu_t\operatorname{sat}_t(H)\geq q, \]
where \(q<1\) allows a specified fraction of the population to be satisfied. The paper’s problem is exactly the \(q=1\) endpoint; the \(q<1\) variants raise new questions about mass-weighted greedy algorithms, partial submodular cover, and possible continuum-specific hardness. So the case is strongest as an exact high-multiplicity mirror with a tractable approximation theory and a clearly identified mass-sensitive extension—not as a claim that this paper already yields a smooth population model.
The proponent has found a valid compression of MMCP, but not a worthwhile continuization. In the paper’s model, multiplicity is structurally irrelevant.
For a fixed graph, agent \(i\) matters only through the family \(\operatorname{MST}(G,\rho_i)\). By Lemma 1, cardinal weights consistent with the same ranking induce exactly the same family of MSTs. Thus if two agents have the same type, every feasible \(H\) satisfies them together or fails them together. For any distribution \(\mu\),
\[ \{H:\sum_t\mu_t\operatorname{sat}_t(H)=1\} = \{H:\operatorname{sat}_t(H)=1\text{ for every }t\text{ with }\mu_t>0\}. \]
The masses themselves disappear. A type with mass \(0.000001\) has exactly the same veto power as one with mass \(0.9\), and changing positive masses continuously changes nothing until one reaches zero. This is not a technical failure of the proposed formalism; it is a degeneracy forced by the paper’s universal “please every agent” objective.
This defeats the proposed mirror of Theorem 4. Let \(r\) be the number of distinct supported ranking types. The continuous instance can be compressed exactly to those \(r\) types, and Algorithm 3 can simply be run on that compressed list. The resulting \(O(\log r)\) guarantee is a deduplicated version of the paper’s theorem, not a population algorithm. The claimed downward and upward dictionaries merely replicate or delete redundant copies. Nothing about the feasible set, optimum, or computational difficulty depends on the population size or proportions.
Theorem 2 does not repair this. Its lower-bound instances use many distinct agent constraints. Replicating each constraint a million times produces a large population, but only by padding the input with duplicates. The logarithmic hardness is a property of the number and structure of distinct MST requirements, not of population multiplicity. That may be a legitimate Class B result for a finite constraint-cover problem, but the distribution is decorative rather than computationally operative.
Theorem 1 has exactly the same defect. In the Set Cover reduction, one agent represents each universe element. Giving those agents positive masses and then requiring all positive-mass types to be satisfied changes nothing: selecting an up-edge still covers a set of distinct constraints, and repeated copies of an element-agent are irrelevant. The reduction therefore establishes ordinary Set Cover hardness of a compressed family of MST requirements, not a meaningful continuous-population phenomenon.
Theorem 3 is even more clearly support-only. Existence of a common MST depends solely on the intersection of the supported agents’ MST families. Algorithm 2 already operates on the distinct rank vectors; a distribution over those vectors adds no object to decide. A cardinal type space does not help, because Lemma 1 collapses all cardinal refinements having the same weak ranking.
The strongest possible repair is to replace universal satisfaction by a quota,
\[ \sum_t\mu_t\operatorname{sat}_t(H)\ge q. \]
That would at least make mass affect the optimum, but it is a new weighted partial-cover problem rather than a continuization of any theorem in this paper. More importantly, the paper’s key structural proof no longer transfers. Its submodular function is the partial-MST overlap \(f_t(H)\), whose maximum encodes complete satisfaction. The actual quota coverage function
\[ g_\mu(H)=\sum_t\mu_t\,\mathbf 1[f_t(H)=|V|-1] \]
is not generally submodular. Even for a triangle with all edges tied, a type is satisfied exactly when \(H\) contains two edges; the marginal value of an edge increases after one edge has already been selected. Thus Lemma 3 and the greedy proof behind Theorem 4 do not survive the natural mass-sensitive modification.
One could certainly study quotas, expected MST overlap, or average regret. Those might be sensible network-design problems. But they require choosing a new social objective absent from the paper, and their continuity comes only from assigning weights to a finite list of constraints. They are not mirrors of MMCP’s named computational results.
So the negative case is not that MMCP is uninteresting, nor that its hardness survives. It is that every faithful mirror of the paper’s actual problem factors exactly through the support of a finite set of ranking types. The proposed “society” is therefore a redundant encoding of the original agent list, while the only natural way to make masses matter changes the problem and loses the paper’s central theorem. The case against is consequently strong, though not absolute: a deliberately new quota-based network problem could be worthwhile, but it would be a successor problem rather than a continuous mirror of 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.