d4-conf-ijcai-2018-0729

My strongest mirror is a population version of Approval. A type is a propositional goal \(\gamma_t\), understood by the set of configurations it accepts; \(\mu_t\) is the fraction of people with that goal. People with the same goal are indistinguishable for this rule. For a Boolean configuration \(v\), define its support by
\[ A_\mu(v)=\sum_{t:\,v\models\gamma_t}\mu_t. \]
The selected configurations are those in the union of the supported types’ goal models that maximize \(A_\mu(v)\). Thus the chosen configuration stays Boolean; it is the population that becomes a distribution.

A concrete regime is a product platform or public planning process with many users, binary choices of features or services, and a relatively small collection of recurring goal templates. For example, millions of users might have goals such as “include either feature \(a\) or feature \(b\),” or “include \(a\) and avoid \(c\).” If there are \(N\) users and \(\tau\) distinct goal types, the relevant input is the \(\tau\) formulas and their rational population shares, with \(N\) potentially much larger than \(\tau\). This is close to the paper’s product-configuration motivation. The type here is the user’s complete goal for the decision, as the paper models it.

The anchor is Theorem 3: \(\mathrm{WINDET}^{\star}(\mathrm{Approval})\) is \(\Theta_2^p\)-complete. Its input is a goal profile \(\Gamma\), a set of issues \(S\), and a partial assignment \(\rho:S\to\{0,1\}\); it asks whether some interpretation in \(\mathrm{Approval}(\Gamma)\) agrees with \(\rho\). The paper proves hardness here by reducing from MAX-MODEL. It obtains membership by invoking Proposition 4 of Lang (2004). In the reduction, given a satisfiable formula \(\phi\) over \(m\) variables, the profile has \(m+1\) agents with goal \(\phi\) and one agent with goal \(p_i\) for each variable \(p_i\). The Approval winners are precisely the models of \(\phi\) maximizing the number of variables set to true.

Here is the corresponding continuous question, Continuous Approval Winner Membership. Its input is a finite support of consistent goals \((\gamma_t,\mu_t)\), with binary-rational \(\mu_t\geq 0\) summing to \(1\), together with \(S\) and \(\rho\). It asks whether there is a configuration \(v\) maximizing \(A_\mu(v)\) among the supported goals’ models and satisfying \(v|_S=\rho\). A solution is yes or no. This is exactly the population analogue of the paper’s winner-membership question, including its tie handling.

The reduction itself gives a continuous hard instance: assign \(\phi\) mass \((m+1)/(2m+1)\), and each goal \(p_i\) mass \(1/(2m+1)\). Every model of \(\phi\) has more support than any configuration outside \(\phi\), and among models of \(\phi\), support increases with the number of true variables. Asking whether a winner sets a designated \(p_i\) to true recovers MAX-MODEL. More generally, every finite profile becomes a continuous society by setting \(\mu_t=n_t/n\), and the winner sets are unchanged. So I expect hardness to transfer to this mirror; I do not claim the arbitrary rational-mass version is \(\Theta_2^p\)-complete without an upper-bound proof. Useful next questions include its exact complexity with binary-encoded masses, tractability under restrictions on goal formulas, and whether approximation or parameterization by \(m\) and \(\tau\) helps.

A second, narrower mirror comes from Theorem 5. The theorem states that \(\mathrm{WINDET}(2sMaj)\), \(\mathrm{WINDET}(\mathrm{EMaj})\), and \(\mathrm{WINDET}(\mathrm{TrueMaj}^r)\) are PP-hard; the paper gives the reduction for \(2sMaj\) and says the other proofs are analogous. Membership is left open. I use the \(2sMaj\) claim as this anchor. The paper’s detailed reduction starts from MAJ-SAT-\(p\) and uses a single agent whose goal is \(\phi\); the rule accepts issue \(p\) exactly when more models of \(\phi\) set \(p\) to \(1\) than to \(0\).

Call the mirror Continuous Two-Stage Goal-Majority Winner Determination. Its input is a rational distribution over goal types and an issue \(j\). Each type first casts a bit \(b_t(j)=1\) exactly when a strict majority of the models of \(\gamma_t\) set \(j\) to \(1\). The population outcome sets \(j\) to \(1\) exactly when \(\sum_t\mu_t b_t(j)>1/2\); a tie sets it to \(0\). The question is whether the outcome sets \(j\) to \(1\). This is the rule’s direct population version, and an empirical distribution recovers the discrete outer majority exactly. I expect hardness to transfer: with one type of mass \(1\), the question already contains the paper’s PP-hard model-majority problem. Here the difficulty is in the succinct formula and its exponentially many models, not in population multiplicity. Further questions are whether membership is in PP for this version, and which formula representations or structural restrictions make the per-type majority computable.

The scope is deliberately limited to these winner-determination results. I am not continuizing the outcome space: configurations remain integral Boolean assignments. Nor am I claiming a continuous mirror for the paper’s axiomatic characterization.

The weakest point is that these mirrors give a natural high-multiplicity formulation, but they do not show that replacing individual agents by mass makes either anchored problem easier. In fact, Theorem 5 shows that model-counting hardness can persist with a single goal type. The Approval reduction’s support grows with the number of issues, although duplicating every type preserves its masses and allows arbitrarily many agents per type. The positive case is therefore that these are meaningful population-level computational questions—one exactly matching the paper’s Approval objective—not that their hardness disappears.