d4-journals-jair-2007-0022

The strongest case I see is to lift the paper’s preferred-answer-set query to a population of repeated logic-program decisions. I would anchor it on Theorem 1, proved in this paper. It says that, for a prioritized program \(\langle P,\Phi\rangle\) and ground atom \(G\), deciding whether \(G\) is true in *some* preferred stable model is \(\Sigma^p_3\)-complete, while deciding whether it is true in *all* preferred stable models is \(\Pi^p_3\)-complete. The paper proves the hardness by reducing from the cited \(\Sigma^p_3\)-complete problem of finding an \(A\)-minimal abductive explanation. These are the two query variants my mirror covers.

Call the mirror the Population PAS Query. Its instance has a finite set of complete case types \(T\), rational masses \(\mu_t>0\) summing to one, a finite logic-program schema, and type-specific facts and preferences. A type includes everything the program uses about a person: eligibility facts, conditional priorities, and any relevant parameters. Thus a million cases sharing the same program-relevant information count as one type. Each person still receives an integral local interpretation—a set of true atoms. What may be fractional is the mass assigned to each interpretation within a type.

Formally, let \((\Omega,\nu)\) be a population partitioned into measurable sets \(\Omega_t\) with \(\nu(\Omega_t)=\mu_t\). A population interpretation assigns each person \(z\in\Omega_t\) a local truth assignment \(M(z)\), while shared policy atoms remain common to the society. It must satisfy the lifted generating rules and any aggregate feasibility constraints, such as per-capita resource limits. Stability is defined by the reduct and minimality condition, with interpretations identified up to sets of measure zero. Equivalently, for each type \(t\) and local state \(S\), a variable \(x_{t,S}\geq 0\) records the mass assigned state \(S\), with \(\sum_S x_{t,S}=\mu_t\). Aggregate constraints can then refer to these masses.

To lift PAS, use the paper’s dependency structure, strata, and conflict comparisons on the finite schema. A preference rule counts as a witness between two population interpretations when it applies on a set of positive measure; changes on a null set do not decide a comparison. This is the substantive continuization choice: it makes positive population mass, rather than the existence of one exceptional individual, the unit of relevance.

For a target predicate \(G\), define
\[ q_G(M)=\nu\bigl(\{z\in\Omega:G\in M(z)\}\bigr). \]
The credulous Population PAS Query asks whether there exists a preferred population interpretation \(M\) with \(q_G(M)>0\). The skeptical version asks whether every preferred population interpretation has \(q_G(M)=1\). A yes answer to the first has a concrete witness: a preferred population interpretation assigning positive mass to \(G\). The second asks whether every preferred population interpretation assigns \(G\) to the whole society. This is a query problem, not a welfare objective; \(q_G\) is the population statistic being queried. The population mass variables are the decision variables.

A plausible regime is a large public-service allocation system: one logic-program policy processes many cases, and each person’s case belongs to one of a small number of complete types. There may be millions of people but only a modest \(\tau=|T|\). The program’s stable models describe feasible decisions, its preference rules express conditional priorities, and aggregate constraints capture capacities that scale with the population. Type averages can be fractional even though every individual receives an integral decision. This is a population model, rather than merely a lottery over outcomes.

I think the authors could recognize the mirror as an extension of their problem: their paper treats stable models as solutions and preference rules as conditional comparisons among choices. The lifted model retains those ingredients and asks about the prevalence of an atom among preferred solutions. The exact scope is Theorem 1’s credulous and skeptical query complexity; it does not continuize the paper’s comparison of PAS with PSM and ASO.

I expect hardness to transfer. The population problem contains a uniform-policy subcase in which the original program’s atoms are shared policy atoms and \(G\) applies to everyone. With one type of mass one, the old query is recovered: \(q_G\) is one exactly when the shared atom is true, and zero otherwise. Thus the paper’s \(\Sigma^p_3\)- and \(\Pi^p_3\)-hardness carries over. That embedding also warns against claiming that high multiplicity itself removes the hard part: the theorem’s hardness lies in the logic and preference structure, not in the number of people. Further questions include whether rational finite populations and the mass model have an exact two-way correspondence, how complexity depends on \(\tau\) and the local program size, and whether configuration LP or column-generation methods can help with the aggregate cases.

My weakest point is that the paper studies the semantics of a program, not a society, and its PAS comparison can turn on a single ground witness. Replacing that with a positive-measure witness is natural for a continuum, but it is a new semantic choice; an author might regard the cohort query as an application of PAS rather than a continuous form of the paper’s own problem. The case survives insofar as the lifted version preserves the paper’s feasible interpretations, conditional preferences, and stratum comparisons, while making the population itself the object whose query is being computed.