d4-conf-wine-2022-0017 (d4-conf-wine-2022-0017)

Given finitely many types \(t=(r,o)\), rational masses \(\mu_t>0\) summing to \(1\), nomination densities \(\rho_{st}\in[0,1]\), and a cap \(\kappa\in(0,1]\), define \(d_t=\sum_s\mu_s\rho_{st}\). Compute quotas \(q_t\in[0,1]\) with \(0<\sum_t\mu_tq_t\le\kappa\) that maximize \(\min_{t:q_t>0}d_t\), subject to equal quotas for types sharing incoming class \(r\); \(o\) records outgoing nomination patterns.

A society is given by its support: the list of \(\tau\) types \(t=(r_t,o_t)\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input includes binary-rational nomination densities \(\rho_{st}\in[0,1]\) and a cap \(\kappa\in(0,1]\). Define the incoming profile \(r_t=(\rho_{st})_s\), the outgoing profile \(o_t=(\rho_{ts})_s\), and \(m=|\{r_t:t\in T\}|\). Individuals are nonatomic; nominations between distinct individuals of the same type are permitted, so \(\rho_{tt}\) need not vanish.
Set \(d_t=\sum_s\mu_s\rho_{st}\) and \(\Delta=\max_t d_t\). Feasible binary-rational quotas satisfy \(q_t\in[0,1]\), \(0<\sum_t\mu_tq_t\le\kappa\), and \(q_t=q_u\) whenever \(r_t=r_u\). Their quality is \(Q(q)=\min_{t:q_t>0}d_t\).
Let \(L\) denote the total input bit length; state running times in \(m,\tau,L\) and any additional approximation parameters.

What is the optimal worst-case additive guarantee \(\alpha(\kappa)\ge0\) achievable by a polynomial-time algorithm returning feasible quotas with \(Q(q)\ge\Delta-\alpha(\kappa)\) on every such society?

Discrete: for loopless directed graphs with \(n\ge2\) vertices and \(2\le k\le n\), an impartial mechanism selects a nonempty set of at most \(k\) vertices, each with indegree at least \(\Delta-\lfloor(n-2)/(k-1)\rfloor-1\); impartiality means a vertex’s selection is invariant under changes to its own outgoing edges. [Verified discrete guarantee](https://arxiv.org/abs/2301.04544v1).
The [journal version](https://link.springer.com/article/10.1007/s00355-025-01631-9) explicitly requires nonempty selections and retains this bound. No result settling this precise mass-and-quota formulation was located.

Answer for the stated formulation

The optimal guarantee is \(\alpha(\kappa)=0\) for every \(\kappa\in(0,1]\). It is attained by an exact polynomial-time algorithm.

Here I use precisely the feasibility conditions in USER_TASK. Equality of quotas for equal incoming profiles is a condition within a society; it does not impose invariance between different societies. To address the stronger mechanism interpretation as well, the last section proves a matching bound under an explicitly added impartiality axiom.

Exact algorithm and proof

Compute every score \(d_t=\sum_s\mu_s\rho_{st}\), and let

\(H=\{t\in T:d_t=\Delta\}\).

Return

\(q_t=\kappa\) if \(t\in H\), and \(q_t=0\) otherwise.

We verify every requirement.

Quota bounds and encoding. Each quota is either zero or the input value \(\kappa\). Hence every quota is binary-rational and belongs to \([0,1]\).

Equality on incoming profiles. If \(r_t=r_u\), then \(\rho_{st}=\rho_{su}\) for every \(s\). Consequently,

\(d_t=\sum_s\mu_s\rho_{st}=\sum_s\mu_s\rho_{su}=d_u\).

Thus \(t\in H\) exactly when \(u\in H\), and the algorithm returns \(q_t=q_u\).

Positive selected mass and the cap. The finite, nonempty support has at least one score maximizer. Because every support mass is positive,

\(0<\sum_{t\in H}\mu_t\le 1\).

Therefore,

\(0<\sum_t\mu_tq_t=\kappa\sum_{t\in H}\mu_t\le\kappa\).

In particular, even an arbitrarily small positive cap permits positive selection from the maximizing types.

Quality. Since \(\kappa>0\), the types with positive quotas are exactly \(H\). Hence

\(Q(q)=\min_{t\in H}d_t=\Delta\).

This proves the zero additive guarantee.

Optimality. Every feasible quota vector selects at least one type, and every type has score at most \(\Delta\). Thus \(Q(q)\le\Delta\) for every feasible vector. The algorithm attains this upper bound on every input, so its worst-case additive loss is exactly zero.

The proof allows arbitrary diagonal densities \(\rho_{tt}\), unequal masses, and any number of incoming-profile classes.

Bit complexity

There are \(\tau^2\) score contributions. They can be evaluated exactly with polynomially bounded intermediate encodings.

For completeness, write the input masses and densities as rational numerators and positive denominators. Let \(D\) be the product of all denominators appearing in those masses and densities. Its bit length is \(O(L)\), because the sum of their encoded lengths is at most \(L\).

Each product \(\mu_s\rho_{st}\) has a denominator dividing \(D\). Thus we can compute the integer scores

\(z_t=Dd_t=\sum_s D\mu_s\rho_{st}\)

and compare these integers. Since \(0\le d_t\le1\), every partial sum is between zero and \(D\), so its bit length is \(O(L)\).

Using ordinary quadratic-time integer multiplication and division gives a conservative bound of \(O(\tau^2L^2)\) bit operations. The output has \(O(\tau L)\) bits. This bound is independent of \(m\), with \(1\le m\le\tau\), and requires no approximation parameter.

Stronger cohort impartiality: a separate, tight bound

The cited discrete model requires invariance of an agent’s selection under changes to that agent’s outgoing nominations. This is explicitly a condition comparing different inputs. [Journal definition of impartiality](https://link.springer.com/article/10.1007/s00355-025-01631-9)

One possible extension to the supplied representation is the following additional axiom: keep positive-mass cohorts and their masses fixed, and require a cohort’s quota to remain unchanged whenever only its entire outgoing row changes.

Under this stronger axiom, together with the stated feasibility conditions, the optimal guarantee is instead \(\alpha(\kappa)=1\). Here is a complete proof.

Fix any binary-rational \(\varepsilon\in(0,1/2)\). Use two cohorts \(a,b\), with masses \(\mu_a=1-\varepsilon\) and \(\mu_b=\varepsilon\), and nomination matrix

\(A=\begin{pmatrix}0&0\\1&1\end{pmatrix}\).

Their incoming profiles coincide: \(r_a=r_b=(0,1)\). Their outgoing profiles differ, so they are distinct support types. Feasibility forces \(q_a=q_b\); positive selected mass then forces both quotas to be positive.

Now change only cohort \(a\)’s outgoing row, producing

\(A'=\begin{pmatrix}0&1\\1&1\end{pmatrix}\).

The added impartiality axiom preserves \(q_a>0\). In the new society,

\(d_a=\varepsilon,\qquad d_b=(1-\varepsilon)+\varepsilon=1,\qquad\Delta=1\).

Because \(a\) must still receive a positive quota, the quality is \(Q(q)=\varepsilon\), regardless of whether \(b\) is selected. Thus the additive loss is \(1-\varepsilon\).

Taking \(\varepsilon=2^{-j}\) for arbitrarily large integers \(j\) shows that any uniform guarantee under this additional axiom must satisfy \(\alpha(\kappa)\ge1\).

Conversely, the constant rule \(q_t=\kappa\) for every type satisfies feasibility, incoming-profile equality, and the added impartiality axiom. Since \(Q(q)\ge0\) and \(\Delta\le1\), it guarantees \(Q(q)\ge\Delta-1\). Therefore the lower bound is tight.

This additional axiom concerns changes by an entire positive-mass cohort. It is stronger than an individual deviation in a nonatomic population and is not among the written quota constraints. For the formulation actually stated, the exact answer remains \(\alpha(\kappa)=0\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated quota problem correctly: \(\alpha(\kappa)=0\) for every \(\kappa\in(0,1]\), attained by an exact polynomial-time algorithm. I found no major or minor mathematical gaps.

• Interpretation of the assignment.

The continuous formulation requires quota equality for types with identical incoming profiles within the same society. It does not require quota invariance under outgoing-row changes between societies.

The prover explicitly distinguishes these conditions. This is a faithful reading of the stated feasibility requirements, not an exploitation of a degenerate case. The discrete impartiality condition supplies context but is not stated as an additional constraint on continuous quotas.

• Construction and quota encoding.

The construction uses
\[ H=\{t\in T:d_t=\Delta\} \]
and assigns quota \(\kappa\) to every type in \(H\), with zero quota elsewhere.

Since the input cap is binary-rational and satisfies \(0<\kappa\le1\), every output quota has the required encoding and lies in \([0,1]\). No approximation or irrational output is introduced.

• Equality for identical incoming profiles.

Equality \(r_t=r_u\) means \(\rho_{st}=\rho_{su}\) for every support index \(s\). Applying the same weights \(\mu_s\) therefore gives \(d_t=d_u\).

Consequently, either both types belong to \(H\) or neither does, so their quotas agree. The argument uses the full incoming profile and does not incorrectly substitute outgoing-profile equality.

• Positive selected mass and cap compliance.

The support is nonempty because its positive masses sum to one. Its finite set of scores therefore has a maximizer, so \(H\) is nonempty.

Positivity of the support masses gives
\[ 0<\sum_{t\in H}\mu_t\le1. \]
Multiplication by the positive cap yields
\[ 0<\sum_t\mu_tq_t =\kappa\sum_{t\in H}\mu_t \le\kappa. \]

Thus both strict positivity and the upper cap hold, including for arbitrarily small positive caps. The construction does not require filling the cap exactly.

• Quality and optimality.

Because \(\kappa>0\), the positively selected types are exactly the maximizers. Hence \(Q(q)=\Delta\).

Conversely, positive selected mass forces every feasible vector to select at least one type, and every type has score at most \(\Delta\). Thus \(Q(q)\le\Delta\) for every feasible vector.

These statements establish pointwise optimality, which implies the claimed optimal worst-case additive guarantee. The restriction \(\alpha(\kappa)\ge0\) is respected.

The proof also covers \(\tau=1\), all scores equal to zero, ties among maximizers, unequal masses, \(\kappa=1\), and arbitrary diagonal densities.

• Exact arithmetic and running time.

The denominator construction is valid when the product includes every encoded denominator occurrence. Each contribution \(\mu_s\rho_{st}\) then has a denominator dividing \(D\), so every scaled score \(z_t=Dd_t\) is an integer.

The bit length of \(D\) is \(O(L)\), since the logarithm of a product is the sum of the logarithms of its factors. Also,
\[ 0\le d_t\le\sum_s\mu_s=1. \]
Nonnegative contributions ensure that scaled partial sums remain between zero and \(D\). The intermediate products used to form individual contributions likewise have \(O(L)\) bits.

There are \(\tau^2\) contributions. The stated conservative bound \(O(\tau^2L^2)\) using ordinary integer arithmetic is justified, including denominator construction and exact comparisons. The output bound \(O(\tau L)\) is valid.

Independence from \(m\) is acceptable: the algorithm need not explicitly construct incoming-profile classes because its score rule already guarantees equality within every class. No approximation parameter is needed.

• Supplementary cohort-impartiality argument.

This section concerns an explicitly different problem and is correctly separated from the main conclusion. The cited journal’s impartiality condition does compare selection across changes to an agent’s nominations. [Journal article](https://link.springer.com/article/10.1007/s00355-025-01631-9)

The two displayed societies are valid support representations. Initially, both incoming profiles equal \((0,1)\), while the outgoing profiles differ. Quota equality and positive selected mass therefore force both quotas to be positive.

After changing only cohort \(a\)’s outgoing row, the additional axiom preserves its positive quota. The recomputed scores are correctly
\[ d_a=\varepsilon,\qquad d_b=1. \]
Selecting \(a\) therefore forces quality \(\varepsilon\), whether or not \(b\) is selected.

The family \(\varepsilon=2^{-j}\), for integers \(j\ge2\), consists of admissible binary-rational inputs. Its losses approach one, establishing the claimed uniform lower bound under the added axiom. The constant-quota rule supplies the matching upper bound and satisfies all stated constraints.

This supplementary result does not establish a result for an unspecified individual-level nonatomic impartiality model, and the prover appropriately limits its conclusion to the added cohort axiom.

No repair or additional clarification is needed to verify the stated result.

⟨structured verdict parsed — rendered above⟩