d4-conf-atal-2021-0050 (d4-conf-atal-2021-0050)

Given rational masses \(\mu_\theta\) of owner types and \(\nu_\phi\) of viewer types, complete type data, and a rational relationship kernel \(w_{\theta\phi}\), choose a policy \(a\) maximizing \(\sum_\theta \mu_\theta u_{\theta,a}v_{\theta,a}\). The finite candidate set contains policies preferred by positive-mass owner types, a specified compromise policy, and the distinguished uploader’s preferred policy if the uploader is represented separately; each \(u_{\theta,a}\) is computed from the type-level allowed, extra, excluded, and excluded-extra viewer masses, and \(v_{\theta,a}\) is the paper’s value-promotion score. Return a maximizing policy and its score.

Owner and viewer societies are given by their supports: lists of positive-mass types with binary rational masses \(\mu_\theta\) and \(\nu_\phi\), each summing to \(1\). Write \(\tau=\tau_O+\tau_V\) for the total support size, not the number of possible types, and \(L\) for the total input bit length. The uploader is included among the owner types; owners cooperate and disclose complete data.
For every owner type \(\theta\) and preferred policy \(p\), input gives the viewer-type audience \(H_{\theta,p}\). Type \(\theta\) prefers policy \(p_\theta\), with individual audience \(P_\theta=H_{\theta,p_\theta}\); at least two positive-mass owner types have different individual audiences. Policy \(p\) has collective audience \(S_p=\bigcap_\theta H_{\theta,p}\).
The base candidates are the distinct preferred policies and a supplied compromise audience \(S_f\subseteq U=\bigcup_\theta P_\theta\), different from every preferred-policy collective audience. Let \(m\) be their number. Each base candidate has both an original-only and a modified-sharing action; the latter additionally gives modified content to \(U\setminus S_a\).
Input supplies rational appreciation \(r_\theta\in[-1,1]\), a nonnegative rational relationship kernel \(w_{\theta\phi}\), and rational modified-mode parameters \(0<\alpha_M,\beta_M<1\). Original-only actions use \((\alpha_a,\beta_a)=(1,0)\); modified actions use \((\alpha_M,\beta_M)\).
For owner \(\theta\) and action \(a\), define \(A=P_\theta\cap S_a\), \(B=S_a\setminus P_\theta\), \(C=P_\theta\setminus S_a\), and \(D=U\setminus(P_\theta\cup S_a)\). With \(W_\theta(E)=\sum_{\phi\in E}\nu_\phi w_{\theta\phi}\), set \(u_{\theta,a}=W_\theta(A)-\alpha_aW_\theta(C)+r_\theta\bigl(W_\theta(B)+\beta_aW_\theta(D)\bigr)\).
Each owner type has a strict order \(o_\theta\) on \(\mathcal V=\{SE,ST,CO,OTC\}\). Complete type data includes, for every action and value, a valuation label \(\operatorname{prom}_{\theta,a}(z)\in\{-1,0,1\}\), meaning demotion, neutrality, or promotion. Define \(v_{\theta,a}=\sum_{i=1}^{4}(5-i)\operatorname{prom}_{\theta,a}(o_{\theta,i})\).
Return an action maximizing \(F(a)=\sum_\theta\mu_\theta u_{\theta,a}v_{\theta,a}\) and its exact rational score; among score maximizers, maximize \(\sum_\theta\mu_\theta v_{\theta,a}\), with any remaining tie allowed.

Is this exact policy-selection problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite cooperative owners, ELVIRA's completeness result guarantees that an optimal recommendation is found when one exists; it asserts no polynomial-time bound ([ELVIRA](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p916.pdf)).
The fuller formulation specifies collective audiences and both sharing modes, but supplies no complexity classification for this rational-mass problem ([An explainable assistant for multiuser privacy](https://link.springer.com/article/10.1007/s10458-021-09543-5)). No verified result settling this exact continuous formulation was located.

Result

The stated exact policy-selection problem is solvable in deterministic polynomial time in \(m,\tau,L\), including the required tie-break and the exact rational score.

The proof uses the supplied support representation and the specified candidate set. Rational masses affect score evaluation; they do not introduce additional decision variables.

1. Constructing the candidate audiences

Let \(\Theta\) and \(\Phi\) be the owner and viewer supports, with \(n=|\Theta|=\tau_O\) and \(t=|\Phi|=\tau_V\). Thus \(n+t=\tau\). Represent every supplied audience by its membership vector on \(\Phi\). This requires only polynomial preprocessing of the explicit input.

Let \(\mathcal P=\{p_\theta:\theta\in\Theta\}\) be the set of distinct preferred policies. For every \(p\in\mathcal P\), compute its collective audience \(S_p=\bigcap_{\theta\in\Theta}H_{\theta,p}\) by intersecting the supplied membership vectors. Also compute \(P_\theta=H_{\theta,p_\theta}\) and \(U=\bigcup_{\theta\in\Theta}P_\theta\).

Every preferred-policy collective audience lies in \(U\). Indeed, because \(p\in\mathcal P\), some owner \(\theta_0\) satisfies \(p_{\theta_0}=p\). Consequently,
\(S_p\subseteq H_{\theta_0,p}=P_{\theta_0}\subseteq U\).
The compromise audience lies in \(U\) by hypothesis. Hence every candidate audience \(S_a\) lies in \(U\).

There are \(m=|\mathcal P|+1\) base candidates and exactly \(2m\) actions, one for each candidate and sharing mode. In particular, \(m\leq n+1\). Distinct policies with identical collective audiences can remain separate candidates: their supplied valuation labels may differ.

Audience construction takes \(O(mnt)\) Boolean operations after preprocessing.

2. Computing each action’s scores

For each owner \(\theta\) and action \(a\), compute the supplied value score
\(v_{\theta,a}=\sum_{i=1}^{4}(5-i)\operatorname{prom}_{\theta,a}(o_{\theta,i})\).
It is an integer satisfying
\(|v_{\theta,a}|\leq 4+3+2+1=10\).

Because \(P_\theta,S_a\subseteq U\), the sets \(A,B,C,D\) in the question form a disjoint partition of \(U\). For \(\phi\in U\), define

| Membership of \(\phi\) | \(c_{\theta,a,\phi}\) |
|---|---|
| \(\phi\in A\) | \(1\) |
| \(\phi\in B\) | \(r_\theta\) |
| \(\phi\in C\) | \(-\alpha_a\) |
| \(\phi\in D\) | \(r_\theta\beta_a\) |

Expanding the definition of \(W_\theta\) gives
\(u_{\theta,a}=\sum_{\phi\in U}\nu_\phi w_{\theta\phi}c_{\theta,a,\phi}\).
Therefore the primary score is exactly
\(F(a)=\sum_{\theta\in\Theta}\sum_{\phi\in U}\mu_\theta\nu_\phi w_{\theta\phi}v_{\theta,a}c_{\theta,a,\phi}\).

Also compute the secondary score
\(T(a)=\sum_{\theta\in\Theta}\mu_\theta v_{\theta,a}\).

For one action, these computations require \(O(nt+n)\) arithmetic operations. Over all actions, they require \(O(mnt+mn)\) arithmetic operations. It remains to verify that these are operations on integers of polynomial bit length.

3. Exact arithmetic has polynomial bit complexity

Write every supplied rational scalar as an integer numerator divided by a positive integer denominator. Let \(Q\) be the product of all these denominator occurrences. This includes the denominators of the masses, relationship weights, appreciation parameters, and modified-mode parameters.

Because the sum of their encoded lengths is at most \(L\), the binary length of \(Q\) is \(O(L)\). Every supplied rational scalar \(x\) can therefore be represented exactly as \(N_x/Q\), where
\(N_x=\operatorname{num}(x)\bigl(Q/\operatorname{den}(x)\bigr)\).
The division is exact. Each \(N_x\) has \(O(L)\) bits, since both the original numerator and \(Q\) have \(O(L)\) bits.

Each summand in the expanded formula for \(F(a)\) is an integer coefficient of absolute value at most \(10\), multiplied by at most five supplied rational scalars:

• The factors \(\mu_\theta,\nu_\phi,w_{\theta\phi}\) contribute three.
• The audience coefficient contributes at most two more, namely \(r_\theta\beta_M\).

The constants used by original-only actions contribute no additional input factors. Thus a summand containing \(k\leq 5\) rational factors can be represented over the common denominator \(Q^5\) with integer numerator
\(\varepsilon v_{\theta,a}Q^{5-k}\prod_{j=1}^{k}N_{x_j}\),
where \(\varepsilon\in\{-1,1\}\) accounts for its sign. Zero summands can be omitted.

Each such numerator has \(O(L)\) bits: it multiplies only a constant number of integers of \(O(L)\) bits. Summing at most \(nt\) of them produces an integer \(J_a\) of bit length \(O(L+\log(\tau+1))\), satisfying
\(F(a)=J_a/Q^5\).
The same bound applies to intermediate partial sums, because their absolute values are bounded by the sum of the absolute values of the summands.

Likewise, the secondary score has the exact representation
\(T(a)=K_a/Q\), where \(K_a=\sum_{\theta\in\Theta}N_{\mu_\theta}v_{\theta,a}\).
Its numerator also has \(O(L+\log(\tau+1))\) bits.

Constructing these representations requires polynomially many additions, multiplications, and exact divisions on polynomial-length integers. Elementary binary arithmetic performs each operation in polynomial time. Thus the arithmetic-operation count from Section 2 yields a polynomial bit-time bound, rather than merely a unit-cost arithmetic bound.

4. Selection, correctness, and output

Enumerate all \(2m\) actions and retain an action whose integer pair \((J_a,K_a)\) is lexicographically maximal: first maximize \(J_a\), and among equal values maximize \(K_a\). Any remaining tie may be resolved arbitrarily.

All primary scores share the positive denominator \(Q^5\), so comparing their numerators compares the primary scores exactly. All secondary scores share the positive denominator \(Q\), so the same holds for the tie-break.

For completeness, after processing any initial segment of the action list, the retained pair is lexicographically maximal among that segment. This follows by induction: retaining the larger of the previous maximum and the next pair preserves that property. After the final action, the retained action therefore satisfies both required optimization criteria.

Return that action and \(J_a/Q^5\). If a reduced fraction is desired, divide numerator and denominator by \(\gcd(|J_a|,Q^5)\), using the polynomial-time Euclidean algorithm. The output fraction has polynomial bit length.

The algorithm evaluates every allowed action, computes both scores exactly, and implements the specified tie-break. This completes the proof.

5. Relation to the cited results

The cooperative completeness statement in [ELVIRA, Section 4.3](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p916.pdf) concerns finding an optimal recommendation. The fuller paper defines collective audiences by intersection in [Definition 4](https://link.springer.com/article/10.1007/s10458-021-09543-5). Neither statement is needed as an algorithmic hypothesis here: the polynomial-time conclusion follows directly from the explicit input and the \(2m\) allowed actions.

The problem is therefore polynomial-time solvable. Under standard polynomial-time reductions, NP-hardness for its associated decision problem would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved. The prover establishes deterministic polynomial-time solvability of the stated problem, including exact rational output and the required tie-break. No major or minor mathematical issues were found.

The proof addresses the supplied finite support representation and the explicitly specified candidate set. It does not rely on a complexity claim from either cited paper.

1. Candidate construction

Verified.

The definitions \(n=|\Theta|=\tau_O\), \(t=|\Phi|=\tau_V\), and \(n+t=\tau\) correctly count supported types rather than all possible types.

Representing supplied viewer-type audiences by membership vectors on \(\Phi\) is consistent with the explicit input representation used in the task. Conversion and identification of distinct preferred policies require only polynomial preprocessing.

For every preferred policy \(p\), the input supplies \(H_{\theta,p}\) for every supported owner type, so the stated intersection is computable. The containment argument is valid: a preferred policy has an owner \(\theta_0\) preferring it, giving
\(S_p\subseteq H_{\theta_0,p}=P_{\theta_0}\subseteq U\).
The compromise containment follows directly from the input hypothesis.

There are exactly \(m=|\mathcal P|+1\) base candidates and \(2m\) actions. The bound \(m\leq n+1\) follows because each owner supplies one preferred policy. Retaining different policies with identical collective audiences is correct: their action-specific valuation labels can differ.

The stated \(O(mnt)\) Boolean-operation bound covers the required audience intersections and unions after preprocessing.

2. Score formulas and operation counts

Verified.

The valuation score is an integer with
\(|v_{\theta,a}|\leq 4+3+2+1=10\),
because each supplied label belongs to \(\{-1,0,1\}\).

Since both \(P_\theta\) and \(S_a\) lie in \(U\), the four specified sets form a disjoint partition of \(U\). The coefficient table assigns exactly the coefficients appearing in the utility definition:

• \(1\) on \(A\);
• \(r_\theta\) on \(B\);
• \(-\alpha_a\) on \(C\);
• \(r_\theta\beta_a\) on \(D\).

Consequently, the expanded utility and primary-score formulas agree exactly with the task. The secondary score also matches the prescribed tie-break.

Scanning at most \(t\) viewer types for each owner gives the claimed \(O(nt+n)\) arithmetic operations per action and \(O(mnt+mn)\) across all actions. No optimization over additional audiences or masses is introduced.

3. Exact arithmetic and bit complexity

Verified.

Every input denominator is positive. Their product \(Q\) is therefore positive, and its bit length is \(O(L)\): the logarithm of a product is the sum of the logarithms of its factors, bounded by their total encoded length.

Each denominator divides \(Q\), so the representation
\(x=N_x/Q\)
is exact. The numerator construction uses an exact integer division. Each resulting \(N_x\) has \(O(L)\) bits, including when an input numerator is negative or zero.

The maximum of five rational factors per primary-score summand is correct. The factors \(\mu_\theta,\nu_\phi,w_{\theta\phi}\) contribute three; the coefficient \(r_\theta\beta_M\) contributes two more. Other coefficient cases use fewer factors.

Thus the proposed denominator \(Q^5\) works for every summand. Its corresponding numerator formula preserves the value and sign exactly. A constant number of polynomial-length factors produces a polynomial-length numerator.

Summing at most \(nt\) terms adds only \(O(\log(\tau+1))\) bits to the bound. The same estimate covers partial sums, regardless of cancellation. The stated bound for \(K_a\) follows from summing at most \(n\) terms.

The proof therefore supplies a bit-complexity argument, not merely an arithmetic-operation count. Its use of elementary integer arithmetic is valid for the polynomial-length operands established above.

4. Selection and output

Verified.

Since \(Q^5\) and \(Q\) are positive common denominators, comparing \(J_a\) and \(K_a\) implements exact primary and secondary comparisons, including negative scores.

The stated induction correctly establishes that the retained pair is lexicographically maximal after every processed segment. Enumeration exhausts the allowed actions, so the final action satisfies both optimization requirements.

Returning \(J_a/Q^5\) supplies an exact rational score of polynomial bit length. Reduction is optional; when used, the Euclidean algorithm applies to the established polynomial-length integers.

5. Edge cases

Verified.

The argument handles zero relationship weights, zero appreciation, negative utilities or valuations, empty candidate audiences, duplicate collective audiences, and complete score ties. Zero primary scores remain valid rational outputs. Also, \(Q=1\) causes no difficulty.

The task’s positive masses and differing individual audiences impose no additional algorithmic obligation. The proof does not incorrectly depend on these conditions to justify enumeration or arithmetic.

6. Cited results and scope

Verified.

The description of cooperative completeness agrees with [ELVIRA, Section 4.3](https://www.ifaamas.org/Proceedings/aamas2021/pdfs/p916.pdf). The collective-audience intersection agrees with [Definition 4 of the fuller paper](https://link.springer.com/article/10.1007/s10458-021-09543-5). Neither result is invoked to establish the algorithm’s correctness or running time.

The final conditional statement about NP-hardness is correct under standard polynomial-time reductions to the associated rational-threshold decision problem. The proof establishes membership in polynomial time; it appropriately does not claim an unconditional separation from NP-hardness.

Required repair or clarification: none.

⟨structured verdict parsed — rendered above⟩