d4-conf-ijcai-2020-0672 (d4-conf-ijcai-2020-0672)

Given finite support \(T\) with rational masses \(\mu_t>0\), summing to one, binary observations \(x_t\), rational refund coefficient \(c\), and rational posteriors \(p_t(z)\) for a random peer's observation \(z\in\{0,1\}\), assume both report values have positive mass. Define \(R_\mu(y)=\sum_{t:x_t=y}\mu_t\), \(q_\mu=R_\mu(0)\), and \(\rho_t(y)=\sum_{z\in\{0,1\}}p_t(z)\left(\frac{\mathbf{1}[y=z]}{R_\mu(y)}-1\right)\). For each type \(t\), let \(D_t(\alpha)=\alpha(\rho_t(x_t)-\rho_t(1-x_t))+c q_\mu(\mathbf{1}[x_t=0]-\mathbf{1}[1-x_t=0])\). Compute \(\alpha^*=\inf\{\alpha\ge 0:D_t(\alpha)>0\text{ for every }t\in T\}\), characterize the scales satisfying all strict inequalities, and return \(+\infty\) if none exist.

A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. The report alphabet has size \(m=2\); let \(L\) be the total input bit length.
Each type has an observation \(x_t\in\{0,1\}\) and rational posterior probabilities \(p_t(z)\geq0\), with \(p_t(0)+p_t(1)=1\), for a truthful random peer's observation. The refund coefficient is a rational \(c>0\).
Set \(R_\mu(y)=\sum_{t:x_t=y}\mu_t\) and \(q_\mu=R_\mu(0)\), and require \(R_\mu(0),R_\mu(1)>0\). Take these frequencies as the reference prior and assume positive belief correlation: \(p_t(x_t)/R_\mu(x_t)>p_t(1-x_t)/R_\mu(1-x_t)\) for every type.
Agents are nonatomic: an individual deviation changes neither frequency nor outcome. With everyone else truthful, reporting \(y\) yields expected utility \(\alpha\rho_t(y)+c q_\mu\mathbf{1}[y=0]\), where \(\rho_t(y)=\sum_{z\in\{0,1\}}p_t(z)(\mathbf{1}[y=z]/R_\mu(y)-1)\); negative peer payments are permitted.
Define \(D_t(\alpha)=\alpha(\rho_t(x_t)-\rho_t(1-x_t))+c q_\mu(\mathbf{1}[x_t=0]-\mathbf{1}[1-x_t=0])\) and \(S=\{\alpha\geq0:D_t(\alpha)>0\text{ for every }t\in T\}\). The computational problem is to determine \(S\), including endpoint inclusion, and compute \(\alpha^*=\inf S\), with \(\inf\varnothing=+\infty\).
Is this exact computation solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite agents with fully mixed priors and positive belief correlation, sufficiently large PTSC reward scaling guarantees a strict truthful subjective equilibrium despite refunds restricted to reports of zero. [Verified source](https://arxiv.org/html/1908.10258)
That existence result does not classify exact minimum-scale computation; the checked sources provide no classification of the continuous problem defined here.

Result

The exact computation is polynomial-time solvable for the stated model with \(m=2\). The feasible set is an open ray whose endpoint is an explicitly computable positive rational number.

This conclusion follows directly from the specified nonatomic utilities; it does not require the finite-agent existence result in the [cited paper](https://arxiv.org/html/1908.10258).

Exact threshold and endpoint

Write \(q=q_\mu\). The frequency assumptions imply \(0<q<1\). Since the posterior probabilities sum to one, the expected peer payment simplifies to

\(\displaystyle \rho_t(y)=\frac{p_t(y)}{R_\mu(y)}-1.\)

Define the truthful peer-payment advantage by

\(\displaystyle a_t=\rho_t(x_t)-\rho_t(1-x_t)=\frac{p_t(x_t)}{R_\mu(x_t)}-\frac{p_t(1-x_t)}{R_\mu(1-x_t)}.\)

Positive belief correlation gives \(a_t>0\) for every type. There are two cases.

• If \(x_t=0\), then \(D_t(\alpha)=\alpha a_t+cq>0\) for every \(\alpha\geq0\), because \(cq>0\).
• If \(x_t=1\), then \(D_t(\alpha)=\alpha a_t-cq\). Since \(a_t>0\), strict truthfulness is equivalent to \(\alpha>cq/a_t\).

Let \(T_1=\{t\in T:x_t=1\}\). This set is nonempty: otherwise \(R_\mu(1)=0\), contrary to the assumptions. Define

\(\displaystyle A=\max_{t\in T_1}\frac{cq}{a_t}.\)

The maximum exists because the support is finite. Each quantity being maximized is finite and positive, so \(0<A<+\infty\). Combining the two cases proves

\(\displaystyle S=(A,+\infty),\qquad \alpha^*=A.\)

In particular, the infimum is excluded. Indeed, a maximizing type \(t\in T_1\) satisfies \(D_t(A)=0\), violating the required strict inequality. Every \(\alpha>A\) satisfies all inequalities.

An equivalent formula using only the zero-observation posterior is useful for computation. For \(t\in T_1\),

\(\displaystyle a_t=\frac{1-p_t(0)}{1-q}-\frac{p_t(0)}q=\frac{q-p_t(0)}{q(1-q)}.\)

Thus positive belief correlation implies \(p_t(0)<q\), and

\(\displaystyle \boxed{\alpha^*=\max_{t:x_t=1}\frac{cq^2(1-q)}{q-p_t(0)}}.\)

All denominators in this expression are strictly positive.

Polynomial bit complexity

An exact algorithm proceeds as follows:

• Compute \(q=\sum_{t:x_t=0}\mu_t\) using rational arithmetic.
• For every \(t\in T_1\), compute the rational threshold \(cq^2(1-q)/(q-p_t(0))\).
• Compare these thresholds exactly and return their maximum, together with the interval description \(S=(\alpha^*,+\infty)\).

To justify polynomial time, represent rationals by binary integer numerators and positive denominators. A common denominator for the sum defining \(q\) is the product of the input mass denominators. Its bit length is at most the sum of their bit lengths, hence \(O(L)\). Because the masses are positive and sum to one, every partial sum lies in \([0,1]\); its numerator over this product denominator also has \(O(L)\) bits.

Each threshold requires a fixed number of rational additions, multiplications, and divisions involving \(q\), \(c\), and one posterior. Consequently, its numerator and denominator have \(O(L)\) bits. Two thresholds \(u/v\) and \(r/s\), with positive denominators, can be compared exactly by comparing the integers \(us\) and \(rv\). These products also have \(O(L)\) bits.

There are \(O(\tau)\) rational operations and comparisons, each executable in polynomial time in \(L\). The output rational has polynomial bit length and can be reduced using the polynomial-time integer gcd algorithm. Therefore the complete computation, including endpoint exclusion, takes polynomial time in \(\tau,L\), and hence in \(m,\tau,L\) for the stipulated \(m=2\).

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved. The prover correctly determines the entire feasible set, its excluded endpoint, and its infimum, and establishes polynomial bit complexity for the stipulated binary report alphabet. No mathematical gaps or false statements were found.

1. Simplification of expected peer payments

For either report \(y\), the indicator term contributes \(p_t(y)/R_\mu(y)\), while the remaining terms sum to \(-1\) because the posterior probabilities sum to one. Thus
\[ \rho_t(y)=\frac{p_t(y)}{R_\mu(y)}-1 \]
is correct. Both denominators are strictly positive by the task assumptions.

Subtracting the two expected peer payments cancels the constant terms and gives exactly the stated \(a_t\). The assumed positive belief correlation implies \(a_t>0\) for every supported type.

2. Truthfulness inequalities

The two cases correctly evaluate the refund difference:

• For \(x_t=0\), \(D_t(\alpha)=\alpha a_t+cq\). Since \(a_t>0\), \(c>0\), and \(q>0\), this is strictly positive throughout \(\alpha\geq0\), including \(\alpha=0\).
• For \(x_t=1\), \(D_t(\alpha)=\alpha a_t-cq\). Division by the strictly positive \(a_t\) correctly gives the equivalent condition \(\alpha>cq/a_t\).

These cases exhaust the support.

3. Feasible set and endpoint inclusion

The frequency assumption \(R_\mu(1)>0\) ensures \(T_1\neq\varnothing\). Its finiteness ensures the maximum defining \(A\) is attained. Every threshold is finite and strictly positive.

Consequently, the simultaneous inequalities are exactly \(\alpha>A\), giving \(S=(A,+\infty)\) and \(\alpha^*=A\). A maximizing type has \(D_t(A)=0\), so the endpoint is excluded. The argument also establishes that \(S\) is nonempty and that the empty-set convention does not arise on admissible inputs.

4. Alternative threshold formula

For \(t\in T_1\), the algebra
\[ \frac{1-p_t(0)}{1-q}-\frac{p_t(0)}q =\frac{q-p_t(0)}{q(1-q)} \]
is correct. Since \(q(1-q)>0\), positivity of \(a_t\) implies \(q-p_t(0)>0\).

Substitution into \(cq/a_t\) correctly produces
\[ \frac{cq^2(1-q)}{q-p_t(0)}. \]
Thus the displayed formula has no zero or negative denominators.

5. Exact computation and bit complexity

The proposed algorithm computes exactly the thresholds already proved sufficient and necessary, then returns their maximum and the correct interval description.

The bit bounds are valid:

• The product of the input mass denominators has bit length \(O(L)\).
• A partial mass sum expressed over that denominator has numerator between zero and the denominator, hence \(O(L)\) bits.
• Each threshold uses a fixed number of rational operations on quantities with \(O(L)\)-bit representations, so its numerator and denominator retain \(O(L)\) bits.
• Cross multiplication compares thresholds exactly using integers of \(O(L)\) bits.
• The number of rational operations and comparisons is \(O(\tau)\); integer arithmetic and final gcd reduction take polynomial time.

A very small positive value of \(q-p_t(0)\) does not invalidate this analysis: its exact rational representation, and therefore the threshold representation, still has polynomial bit length.

The conclusion is correctly restricted to the specified \(m=2\) model. The proof neither requires nor invokes the linked finite-agent existence theorem.

Required clarification

None.

⟨structured verdict parsed — rendered above⟩