d4-conf-aaai-2021-0920

The strongest mirror is a large electorate inside a fixed set of districts. Keep the paper’s finite states, two candidates, voter incentives, and district aggregation; replace the named voters in each district with a distribution over complete voter types. A type \(t\) in district \(d\) has a utility difference \(u_{dt}(\theta)=u_{dt}(\theta,c_0)-u_{dt}(\theta,c_1)\) for every state \(\theta\), and mass \(\mu_{dt}\), with \(\sum_t\mu_{dt}=1\). District membership belongs in the type because it determines which local signal a voter receives and how their vote is counted. A plausible regime is a few hundred districts, each with a large electorate and a modest number of recurring utility profiles: \(N\) voters can be very large while the total number of supported district-type pairs \(\tau\) stays moderate. The final election remains binary; fractional quantities describe shares of voters.

My lead anchor is Theorem 3, proved in this paper. It states that for \(\epsilon>0\), \(\delta\in(0,1)\), and \(\eta\in(0,1]\), there is an algorithm running in \(\operatorname{poly}(|R||\Theta|^{\log(1/(\eta\delta))/\epsilon^2})\) time that outputs an \(\epsilon\)-persuasive semi-public signaling scheme \(\phi^\epsilon\) with
\[ W_\delta(\phi^\epsilon)\ge (1-\eta)\max_{\phi\in\Phi}W(\phi), \]
where \(\Phi\) is the set of persuasive schemes. Here \(W_\delta\) relaxes the number of districts needed for \(c_0\) to win; the vote threshold inside each district is unchanged.

The corresponding continuous question is Continuous Semi-public District Persuasion. An instance gives a finite state set \(\Theta\), rational prior \(\pi\), districts \(d=1,\ldots,D\), rational type masses \(\mu_{dt}\), and rational utility vectors \(u_{dt}(\cdot)\). A scheme specifies, conditional on each state, a distribution over tuples of district signals. Every voter in district \(d\) sees the same component of that tuple. Given a district signal, let \(p\) be its posterior over states. A type with \(\sum_\theta p_\theta u_{dt}(\theta)>\epsilon\) votes for \(c_0\); one with value below \(-\epsilon\) votes for \(c_1\); and a type inside that band may split its mass between the two actions. Thus the \(c_0\) vote share in district \(d\) is \(v_d=\sum_t\mu_{dt}z_{dt}\), where \(z_{dt}\in[0,1]\) is that type’s share voting for \(c_0\).

Write \(K_D=\lceil D/2\rceil\). The exact election utility is \(W(v)=1\) when at least \(K_D\) districts have \(v_d\ge 1/2\), and zero otherwise. The relaxed utility \(W_\delta(v)\) uses the paper’s threshold \(\lceil(1-\delta)K_D\rceil\), keeping each local threshold at \(1/2\). The problem is to output an \(\epsilon\)-persuasive scheme whose expected \(W_\delta\) is at least \(1-\eta\) times the best expected \(W\) over exactly persuasive continuous schemes. This specifies the instance, the signal structure, the objective, and what counts as a solution. I expect a Class A result for fixed \(\epsilon,\delta,\eta\), with complexity polynomial in \(D,\tau,|\Theta|\), and the input bit length, and with dependence on the tolerances resembling the paper’s bound. The paper’s posterior discretization and LP ideas give a credible route, though the type-mass version still needs proving.

A second, independent anchor is Theorem 1, also proved here: LP (1) computes an optimal solution to PRIVATE-DBE in polynomial time. Its continuous counterpart is Continuous Private District Persuasion on the same mass-and-type instance. A private scheme can be represented by, for each state \(\theta\), a probability law \(\Lambda_\theta\) over arrays \(x=(x_{dt})\in[0,1]^\tau\), where \(x_{dt}\) is the fraction of type \(t\)’s mass in district \(d\) receiving a \(c_0\) recommendation in that realized recommendation profile. Set \(q_{dt\theta}=\mathbb E_{\Lambda_\theta}[x_{dt}]\). Persuasiveness requires, for each type,
\[ \sum_\theta\pi_\theta q_{dt\theta}u_{dt}(\theta)\ge 0,\qquad \sum_\theta\pi_\theta(1-q_{dt\theta})u_{dt}(\theta)\le 0. \]
For each realized array, district \(d\)’s \(c_0\) vote share is \(\sum_t\mu_{dt}x_{dt}\); the objective is to maximize the expected probability that \(c_0\) wins the exact nested-majority election. The output is an optimal private signaling plan, including its randomization over mass allocations. I would also expect Class A, via a finite-dimensional LP and threshold pricing over type masses, but Theorem 1 by itself does not establish that bit-complexity bound: its runtime is polynomial in the number of named voters.

These are computational mirrors of the paper’s problems, not continuized outcomes or states. They retain the paper’s information advantage, receiver incentives, channel restrictions, and election rule. The public or district-level broadcast settings are especially plausible at high multiplicity: mass by utility type is the natural representation of a large electorate reached through shared communication.

The weakness is that the paper’s most directly relevant named results are algorithmic. It has no numbered hardness theorem to anchor a claim that discrete hardness dissolves in the continuum. Its public-hardness discussion invokes a result from Castiglioni, Celli, and Gatti (2020a) in prose; I would not present that as a numbered anchor from this paper. It does suggest a useful next question: does exact public-signaling hardness survive when the electorate is given by rational masses over a moderate number of complete utility types? The other main limitation is that Theorem 3’s guarantee deliberately relaxes the outer majority and allows \(\epsilon\)-persuasiveness. Whether the same high-multiplicity regime admits an exact result, or whether hardness remains because of the state and district structure, is open in this mirror.