d4-conf-atal-2017-0012 (d4-conf-atal-2017-0012)

Given a finite category set \(H\), rational per-capita capacities \(q_h\) summing to \(1\), and paired ranking types \(s=(t_s,t'_s)\) with rational masses \(\kappa_s\) summing to \(1\), consider two profiles on the same atomless unit-mass population and the same feasible allocations, where each person receives one category and category \(h\) is assigned to mass \(q_h\). Decide whether the majority edge weights agree between the profiles for every pair of feasible allocations \(f,g\), where each edge weight is the integral of the assigned individuals' pairwise ranking comparisons. If not, return a pair of allocations witnessing unequal edge weights.

Let \(H\) be a nonempty category set, \(m=|H|\), with positive binary-rational capacities \(q_h\) satisfying \(\sum_h q_h=1\). A society is given by its support: the list of \(\tau\) paired types \(s=(t_s,t'_s)\) with positive binary-rational masses \(\kappa_s\) summing to \(1\); both rankings are strict total orders on \(H\). Here \(\tau\) is the support size, not the number of possible types, and \(L\) is the total input bit length.
Represent the atomless population by \([0,1)\) with Lebesgue measure \(\lambda\), partitioned into consecutive type intervals \(I_s\) of lengths \(\kappa_s\). The two profiles assign rankings \(t_s\) and \(t'_s\), respectively, to every individual in \(I_s\).
An allocation is any measurable function \(f:[0,1)\to H\) satisfying \(\lambda(f^{-1}(h))=q_h\) for every \(h\); individuals of the same type may receive different categories.
Define \(\phi_t(h,k)=1\) if \(h\succ_t k\), \(-1\) if \(k\succ_t h\), and \(0\) if \(h=k\). The edge weights are \(w(f,g)=\sum_s\int_{I_s}\phi_{t_s}(f(x),g(x))\,d\lambda(x)\) and \(w'(f,g)=\sum_s\int_{I_s}\phi_{t'_s}(f(x),g(x))\,d\lambda(x)\).
Decide whether \(w(f,g)=w'(f,g)\) for every pair of feasible allocations; otherwise return a witnessing pair, encoded by allocations constant on a finite interval partition with rational endpoints.

Is this decision problem in \(\mathrm{P}\) or NP-hard? In the polynomial-time case, can a witnessing pair also be returned in time polynomial in \(m,\tau,L\)?

For finite societies with equally many agents and distinct houses, equality of all weighted majority comparisons has a polynomial-time test, characterized by cyclic rotation of the finest common ordered blocks with unchanged within-block rankings. [Verified source](https://pub.dss.in.tum.de/brandt-research/assigngraph.pdf).
No result settling this exact atomless, rational-capacity problem was located in the literature search.

Result

The decision problem is in \(\mathrm{P}\). Whenever equality fails, a witnessing pair can be constructed in time polynomial in \(m,\tau,L\), using at most \(\tau m^2\) intervals with rational endpoints of bit length \(O(L)\).

The proof gives an explicit criterion that depends only on the paired rankings, provided every capacity and every listed type mass is positive.

1. A finite representation of allocation pairs

Define
\(d_s(h,k)=\phi_{t_s}(h,k)-\phi_{t'_s}(h,k)\).
Then \(d_s(h,h)=0\), \(d_s(k,h)=-d_s(h,k)\), and \(d_s(h,k)\in\{-2,0,2\}\).

For a feasible allocation pair \((f,g)\), let
\(x_{s,h,k}=\lambda(\{u\in I_s:f(u)=h,\ g(u)=k\})\).
These joint measures satisfy:

• \(x_{s,h,k}\geq 0\);
• \(\sum_{h,k}x_{s,h,k}=\kappa_s\) for every \(s\);
• \(\sum_{s,k}x_{s,h,k}=q_h\) for every \(h\);
• \(\sum_{s,h}x_{s,h,k}=q_k\) for every \(k\).

Conversely, every real table satisfying these constraints is realized by an allocation pair. Indeed, fix an ordering of \(H\times H\), partition each \(I_s\) consecutively into intervals of lengths \(x_{s,h,k}\), and assign \(f=h\), \(g=k\) on the corresponding interval. The first constraint ensures nonnegative lengths, the second fills each type interval, and the last two give the required capacities.

Thus the comparison difference is the linear functional
\(D(x)=\sum_{s,h,k}d_s(h,k)x_{s,h,k}\).

A strictly positive feasible table is
\(x^0_{s,h,k}=\kappa_s q_hq_k\).
Its feasibility follows from \(\sum_s\kappa_s=\sum_hq_h=1\). Moreover, \(D(x^0)=0\): for each \(s\), the terms indexed by \((h,k)\) and \((k,h)\) cancel because \(q_hq_k=q_kq_h\) and \(d_s(h,k)=-d_s(k,h)\).

2. An exact criterion

Theorem. Equality holds for every feasible allocation pair if and only if there is a single function \(a:H\to\mathbb Z\) such that
\(d_s(h,k)=a(h)-a(k)\)
for every \(s,h,k\).

Fix a reference category \(r\in H\), and define
\(a_s(h)=d_s(h,r)\).
In particular, \(a_s(r)=0\). The algorithm checks the following two conditions:

• \(d_s(h,k)=a_s(h)-a_s(k)\) for every \(s,h,k\).
• \(a_s(h)=a_1(h)\) for every \(s,h\).

These conditions are equivalent to the theorem’s potential representation. If they hold, take \(a=a_1\). Conversely, any common potential satisfies
\(a_s(h)=a(h)-a(r)\), which gives both conditions.

Sufficiency. Suppose the common potential representation holds. For any feasible joint table,

\(D(x)=\sum_h a(h)\sum_{s,k}x_{s,h,k}-\sum_k a(k)\sum_{s,h}x_{s,h,k} =\sum_h a(h)q_h-\sum_k a(k)q_k=0\).

Consequently, all feasible allocation pairs have equal comparisons.

We prove necessity constructively: a failed check produces a witnessing table.

3. Explicit witnesses for failed checks

Let \(E_{s,h,k}\) denote the table with value \(1\) at coordinate \((s,h,k)\) and value \(0\) elsewhere. Set
\(\varepsilon=\frac12(\min_s\kappa_s)(\min_hq_h)^2>0\).
Every coordinate of \(x^0\) is at least \(2\varepsilon\).

3.1. Failure within one type

Suppose condition 1 fails at \((s,h,k)\), and write
\(R=d_s(h,k)-a_s(h)+a_s(k)\neq 0\).

The categories \(h,k,r\) must be distinct. If \(h=k\), both sides of condition 1 are zero. If \(k=r\), the condition is the definition of \(a_s(h)\). If \(h=r\), it follows from antisymmetry.

Define
\(\Delta=E_{s,h,k}-E_{s,h,r}-E_{s,r,k}+E_{s,r,r}\).

These four coordinates are distinct. The perturbation preserves every constraint:

• Its total within type \(s\) is \(1-1-1+1=0\).
• For the first allocation, its contributions cancel separately at categories \(h\) and \(r\).
• For the second allocation, its contributions cancel separately at categories \(k\) and \(r\).
• All other coordinates are unchanged.

Therefore \(x=x^0+\varepsilon\Delta\) is feasible. Its coordinates remain positive, since the only decreases have size \(\varepsilon\).

Using \(d_s(r,k)=-a_s(k)\) and \(d_s(r,r)=0\), we obtain
\(D(\Delta)=d_s(h,k)-d_s(h,r)-d_s(r,k)+d_s(r,r)=R\).
Hence
\(D(x)=D(x^0)+\varepsilon D(\Delta)=\varepsilon R\neq 0\).

The interval realization from Section 1 gives a witnessing allocation pair.

3.2. Failure of agreement between types

Suppose condition 1 holds, but condition 2 fails at \((s,h)\). Then \(s\neq 1\), \(h\neq r\), and
\(a_s(h)-a_1(h)\neq 0\).

Define
\(\Delta=E_{s,h,r}-E_{s,r,r}-E_{1,h,r}+E_{1,r,r}\).

Again, its four coordinates are distinct. Its total is zero separately within each affected type. For the first allocation, the change at category \(h\) in type \(s\) is canceled by the change in type \(1\), and likewise for category \(r\). For the second allocation, every affected coordinate assigns category \(r\), and the changes cancel within each type.

Thus \(x=x^0+\varepsilon\Delta\) is feasible and positive. Since diagonal coefficients vanish,
\(D(\Delta)=d_s(h,r)-d_1(h,r)=a_s(h)-a_1(h)\neq 0\).
Consequently,
\(D(x)=\varepsilon(a_s(h)-a_1(h))\neq 0\).

This completes the proof of necessity and of the theorem.

4. Polynomial running time and rational output

From the two rankings of each type, construct tables recording each category’s position. Each coefficient \(d_s(h,k)\) can then be computed using a constant number of position comparisons. Computing the coefficients and checking both conditions takes \(O(\tau m^2)\) such operations.

If a check fails, the construction above changes four coordinates of the rational table \(x^0\). Realizing the resulting table requires at most one interval per coordinate, hence at most \(\tau m^2\) intervals.

To bound the bit complexity explicitly, let \(B\) be the product of all denominators in the input encodings of the capacities and masses. Its bit length is \(O(L)\). Write
\(\kappa_s=K_s/B\) and \(q_h=Q_h/B\),
where \(K_s,Q_h\) are positive integers at most \(B\). Let
\(K_{\min}=\min_s K_s\) and \(Q_{\min}=\min_h Q_h\).

Then
\(x^0_{s,h,k}=K_sQ_hQ_k/B^3\)
and
\(\varepsilon=K_{\min}Q_{\min}^2/(2B^3)\).
Every coordinate of either constructed witness table therefore has the common denominator \(2B^3\), with numerator
\(2K_sQ_hQ_k+K_{\min}Q_{\min}^2\Delta_{s,h,k}\).

All interval endpoints are cumulative sums of these coordinates, so they also have denominator \(2B^3\). Because every endpoint lies in \([0,1]\), its numerator lies between \(0\) and \(2B^3\). Thus each endpoint has bit length \(O(L)\).

The type boundaries are respected because the coordinates of each type sum to \(\kappa_s\). Using half-open intervals makes both allocations well-defined on all of \([0,1)\).

All required arithmetic uses integers of bit length \(O(L)\), and there are polynomially many operations and output entries. Witness construction therefore runs in time polynomial in \(m,\tau,L\).

5. Structural interpretation

The criterion also yields a simple ranking characterization.

If the common potential \(a\) is constant, then every \(d_s(h,k)=0\). Hence every pairwise comparison is unchanged, so \(t_s=t'_s\) for every type.

Otherwise, let \(c=\min_h a(h)\), and choose \(b\) with \(a(b)=c\). For every \(h\),
\(a(h)-c=d_s(h,b)\in\{-2,0,2\}\).
Since this difference is nonnegative, every potential value is either \(c\) or \(c+2\). Both values occur.

Define the nonempty blocks
\(A=\{h:a(h)=c+2\}\) and \(B=\{h:a(h)=c\}\).

Within either block, \(d_s(h,k)=0\), so each type’s restricted ranking is unchanged. Across blocks, \(d_s(h,k)=2\) for \(h\in A\), \(k\in B\). This forces \(h\succ_{t_s}k\) and \(k\succ_{t'_s}h\).

Thus, in the nontrivial case, there is one common partition into two blocks such that every original ranking places \(A\) above \(B\), every modified ranking places \(B\) above \(A\), and all within-block rankings are preserved. Conversely, this structure gives the common potential \(a=2\) on \(A\) and \(a=0\) on \(B\), so it guarantees equality.

The case \(m=1\) is included automatically: every comparison is zero.

⟨structured verdict parsed — rendered above⟩

Verification report

The prover resolves the stated problem correctly. The decision criterion, both witness constructions, and the polynomial bit-complexity bound are valid. I found no major or minor issues.

1. Representation of feasible allocation pairs

For measurable allocations \(f,g\), the sets defining \(x_{s,h,k}\) are measurable. Within each type interval, they form a finite partition, so their measures are nonnegative and sum to \(\kappa_s\). Summing over types and the second category gives the capacity constraints for \(f\); summing over types and the first category gives those for \(g\).

The converse realization is also valid. A nonnegative table satisfying the stated constraints partitions each \(I_s\) into finitely many intervals of the prescribed lengths. Zero-length intervals can be omitted. The resulting functions are measurable and satisfy both sets of capacities. This argument works for real tables; the later witness constructions specifically produce rational tables.

On each joint cell, the comparison difference is the constant \(d_s(h,k)\), so the identity
\[ D(x)=\sum_{s,h,k}d_s(h,k)x_{s,h,k} \]
correctly represents \(w(f,g)-w'(f,g)\).

The proposed table \(x^0_{s,h,k}=\kappa_s q_hq_k\) satisfies all constraints. Every coordinate is strictly positive because all listed masses and capacities are positive. Antisymmetry cancels the off-diagonal terms in \(D(x^0)\), and the diagonal terms vanish. Thus \(D(x^0)=0\).

2. Criterion and sufficiency

The two checks are equivalent to the existence of a common potential:

• If they pass, \(a=a_1\) has the required representation.
• If a common potential exists, \(a_s(h)=a(h)-a(r)\) for every type, establishing both checks.

The integer-valued requirement causes no problem: each constructed \(a_s(h)=d_s(h,r)\) is an integer.

The sufficiency calculation correctly uses the two global marginal constraints. Consequently, every feasible table has \(D(x)=0\), and hence every feasible allocation pair has equal comparisons.

3. Witness for failure within a type

The assertions that \(h,k,r\) must be distinct are correct: each possible equality makes the checked identity hold by the diagonal identity, the definition of \(a_s\), or antisymmetry.

The four affected coordinates are therefore distinct. The perturbation preserves the type total and both allocation marginals exactly as stated.

The positivity bound is valid:
\[ x^0_{s,h,k}\geq (\min_s\kappa_s)(\min_hq_h)^2=2\varepsilon. \]
Each decreased coordinate loses only \(\varepsilon\), so the perturbed table remains strictly positive.

The objective calculation has the correct signs:
\[ D(\Delta)=d_s(h,k)-a_s(h)+a_s(k)=R. \]
Since \(D(x^0)=0\) and \(R\neq0\), the constructed feasible table is a genuine witness.

4. Witness for disagreement between types

A failed second check necessarily has \(s\neq1\) and \(h\neq r\), making the four affected coordinates distinct.

The perturbation preserves each affected type total. Its first-allocation marginal changes cancel between the two types; its second-allocation changes cancel within each type. The same positivity bound applies.

The two diagonal coefficients vanish, giving
\[ D(\Delta)=d_s(h,r)-d_1(h,r)=a_s(h)-a_1(h)\neq0. \]
Thus this construction also gives a feasible witnessing pair.

Together, the two constructions establish necessity: every failure of the proposed criterion produces unequal comparisons. No external characterization theorem is needed.

5. Running time and rational encoding

Constructing ranking-position tables and checking all identities requires \(O(\tau m^2)\) position comparisons and coefficient operations. Their bit costs are polynomial in the input length.

The common-denominator argument is correct. The product \(B\) of input denominators has bit length \(O(L)\), and every input mass or capacity can be expressed with denominator \(B\). Both the baseline coordinates and the perturbation have common denominator \(2B^3\), with the stated numerators.

Cumulative interval endpoints therefore have that denominator as well. Nonnegativity and total mass \(1\) place every endpoint in \([0,1]\), so its numerator has bit length \(O(L)\). The construction respects the original type boundaries because each type’s coordinates still sum to its mass.

There are at most \(\tau m^2\) intervals. All arithmetic and output have polynomial size, proving the claimed polynomial-time witness guarantee.

6. Structural interpretation and edge cases

The structural characterization follows correctly from the potential representation. Choosing a category attaining the minimum potential shows that every potential value differs from that minimum by either \(0\) or \(2\). In the nonconstant case, both levels occur.

A cross-block difference of \(2\) forces the stated reversal, since it can only arise from comparison values \(1\) and \(-1\). Within-block difference zero means the two rankings agree on every comparison within that block. The stated converse also satisfies the criterion.

The case \(m=1\) is handled correctly. A single supported type presents no difficulty: the agreement check is then vacuous. Nonempty support follows from the positive masses summing to \(1\).

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩