d4-conf-atal-2021-0037 (d4-conf-atal-2021-0037)

Given a finite support \(T\) of \(\tau\) operational types, rational masses \(\mu_t>0\) summing to \(1\), and a sequence length \(h\), construct finite mass partitions \(\Pi_1,\ldots,\Pi_h\). Each coalition is a nonzero vector \(q\in\mathbb{Q}_{\ge 0}^{\tau}\), and each \(\Pi_i\) must sum to \(\mu\). For every \(i<h\), require that each \(q'\in\Pi_{i+1}\) has a parent \(q\in\Pi_i\) with \(q'_t\le q_t\) for all \(t\), and that \(|\Pi_i|<|\Pi_{i+1}|\).

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; types impose no additional constraints.
The input also contains a positive integer \(h\), encoded in unary. Let \(L\) be the total input bit length. State running times in \(\tau,h,L\); there is no separate candidate or feature parameter \(m\).
A mass partition \(\Pi\) is a finite nonempty indexed family of nonzero vectors \(q\in\mathbb{Q}_{\ge0}^{\tau}\) with \(\sum_{q\in\Pi}q=\mu\). Equal vectors may occur as distinct coalitions, and \(|\Pi|\) counts occurrences.
A sequence \(\Pi_1,\ldots,\Pi_h\) is feasible if, for every \(1\le i<h\), \(|\Pi_i|<|\Pi_{i+1}|\) and each \(q'\in\Pi_{i+1}\) has some \(q\in\Pi_i\) satisfying \(q'_t\le q_t\) for every \(t\in T\). These are the entire transition requirements. The first partition is unrestricted, and coalition counts have no prescribed upper bound.

Is this feasibility problem in \(\mathrm{P}\), with a polynomial-time algorithm constructing an explicit rational sequence whenever one exists, or is it \(\mathrm{NP}\)-hard?

For finite societies, MC-Link is guaranteed to construct a feasible sequence under strict partition refinement whenever one exists, in polynomial time assuming polynomial-time feasibility checks and valuation access ([Krausburg, Dix and Bordini, 2021](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p719.pdf)).
No result settling exactly the rational mass feasibility problem above was identified in the literature search.

Result

The problem is in \(\mathrm{P}\). Every valid input is feasible, and an explicit rational sequence can be constructed in time \(O\!\left(h^2\bigl(L+\tau\log(h+1)\bigr)\right)\).

This conclusion holds for arbitrary support size and horizon under exactly the stated transition requirements.

Construction and proof

For each \(i\in\{1,\ldots,h\}\), let \(\Pi_i\) be the indexed family of \(i\) copies of the vector \(\mu/i\). Equivalently, its occurrence indexed by \(j\in\{1,\ldots,i\}\) is

\(q^{(i,j)}_t=\mu_t/i\qquad(t\in T).\)

Repeated vectors are expressly permitted. We verify every requirement.

• Each coalition is a nonzero rational vector. Every coordinate \(\mu_t/i\) is positive and rational, since \(\mu_t>0\) and \(i\) is a positive integer.

• Each family partitions the prescribed mass. For every \(t\in T\),

\(\displaystyle\sum_{j=1}^{i}q^{(i,j)}_t=i\frac{\mu_t}{i}=\mu_t.\)

• Coalition counts strictly increase. Occurrences are counted separately, so \(|\Pi_i|=i<i+1=|\Pi_{i+1}|\).

• Every later coalition has a dominating predecessor. For \(i<h\), every occurrence \(q'\in\Pi_{i+1}\) and every occurrence \(q\in\Pi_i\) satisfy, coordinatewise,

\(\displaystyle q'_t=\frac{\mu_t}{i+1}\le\frac{\mu_t}{i}=q_t.\)

Thus each later coalition has the required predecessor.

Consequently, \(\Pi_1,\ldots,\Pi_h\) is feasible. When \(h=1\), the construction gives the single partition \(\Pi_1=(\mu)\), and there are no transition conditions.

Explicit encoding and running time

Write each input mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers encoded in binary. Output each coordinate of \(\mu/i\) as \(a_t/(i b_t)\). Coprimality is unnecessary for an explicit rational representation.

Let \(\ell_t\) be the combined bit length of \(a_t\) and \(b_t\). Then \(\sum_t\ell_t\le L\), and one output vector requires

\(O\!\left(L+\tau\log(h+1)\right)\)

bits. There are exactly \(\sum_{i=1}^{h}i=h(h+1)/2\) vector occurrences. Hence the complete explicit output has size

\(O\!\left(h^2\bigl(L+\tau\log(h+1)\bigr)\right).\)

To achieve the same time bound, maintain the denominators \(d_{t,i}=i b_t\). Initialize \(d_{t,1}=b_t\), and update by binary addition:

\(d_{t,i+1}=d_{t,i}+b_t.\)

Each update costs \(O(\ell_t+\log(h+1))\) bit operations. At stage \(i\), write \(i\) copies of the resulting vector. Summing the update and output costs gives the claimed running time. Because \(h\) is encoded in unary, this bound is polynomial in the input length.

The number of coalition occurrences is also minimal: any feasible sequence has \(|\Pi_1|\ge1\), and strict integer increases imply inductively that \(|\Pi_i|\ge i\).

Relation to the cited work

The conclusion follows directly from the mass model’s stated conditions; it requires no application of the finite-agent MC-Link algorithm discussed in [Krausburg, Dix and Bordini (2021)](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p719.pdf).

⟨structured verdict parsed — rendered above⟩

The prover fully resolves the stated problem. The construction satisfies every partition and transition requirement, and its explicit output and running time are polynomial in the input length. No mathematical or computational gaps were found.

• Scope and quantifiers. The argument applies to every valid input: a nonempty support with positive rational masses summing to \(1\), and a positive integer horizon \(h\). It uses exactly the permitted transition conditions. In particular, equal vectors may occur as separate coalitions, and a predecessor may dominate multiple later coalitions.

• Validity of the partitions. For each \(1\le i\le h\), the indexed family \(\Pi_i\) contains exactly \(i\) occurrences of \(\mu/i\). Each coordinate is positive and rational, so every occurrence is a nonzero vector in \(\mathbb{Q}_{\ge0}^{\tau}\). The family is finite and nonempty. For every coordinate \(t\), its total mass is

\[ \sum_{j=1}^{i}\frac{\mu_t}{i}=\mu_t. \]
Thus every \(\Pi_i\) is a mass partition as defined in the task.

• Strict increase in coalition counts. Because the definition counts occurrences, including equal vectors, \(|\Pi_i|=i\). Hence every required inequality \(|\Pi_i|<|\Pi_{i+1}|\) holds. The construction does not inadvertently count distinct vector values instead of occurrences.

• Domination requirement. For every \(1\le i<h\), every later occurrence and every earlier occurrence satisfy

\[ \frac{\mu_t}{i+1}\le\frac{\mu_t}{i} \]
for every \(t\). Positivity of \(\mu_t\) and of the denominators justifies this inequality. Since \(\Pi_i\) is nonempty, the required existential predecessor exists. No injectivity, assignment of children, or conservation of mass within predecessor groups is required by the task; the proof correctly avoids assuming such additional requirements.

• Boundary cases. When \(h=1\), the single partition \((\mu)\) is valid and no transitions need verification. The same argument covers \(\tau=1\). Positivity and nonemptiness exclude zero coalitions and empty supports throughout.

• Explicit rational encoding. Writing each coordinate as \(a_t/(i b_t)\) represents the required rational number exactly. The task does not require reduced fractions, so retaining unreduced denominators is permissible. Their bit lengths are bounded by the input denominator lengths plus \(O(\log(h+1))\). Including numerators and ordinary delimiters, the stated per-vector bound \(O(L+\tau\log(h+1))\) is valid.

• Output size and running time. There are exactly \(h(h+1)/2\) vector occurrences. Multiplying this count by the per-vector bound gives the claimed total output size. The denominator recurrence \(d_{t,i+1}=d_{t,i}+b_t\) is exact, and binary addition has the stated linear bit cost. Summing these updates and the cost of writing all occurrences yields

\[ O\!\left(h^2\bigl(L+\tau\log(h+1)\bigr)\right). \]
Loop control and partition delimiters fit within this bound. Unary encoding gives \(h\le L\), and the explicit support encoding also bounds \(\tau\) by \(L\), so this running time is polynomial in \(L\).

• Minimality and cited work. The additional claim about coalition occurrences is correct: nonemptiness gives \(|\Pi_1|\ge1\), and strict integer increases imply \(|\Pi_i|\ge i\). The construction attains these bounds. The proof invokes no theorem from the cited MC-Link work, so no external theorem hypotheses need verification.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩