d4-conf-aaai-2015-0521

The strongest mirror is high-multiplicity preference optimization over repeated service decisions. Imagine a city assigning service packages to a very large population. Residents fall into \(\tau\) types, where each type captures everything relevant to feasibility, resource use, and preference weights. The population has rational type masses \(\mu_t\), with \(\sum_t\mu_t=1\), and \(N\gg\tau\). For type \(t\), a local ASP program \(P_t\) describes the feasible integral packages \(\mathcal S_t\) for one resident.

The decision variable is \(x_{t,S}\ge 0\): the mass of type \(t\) residents assigned package \(S\in\mathcal S_t\). It must satisfy \(\sum_{S\in\mathcal S_t}x_{t,S}=\mu_t\), along with rational per-capita resource constraints such as \(\sum_{t,S}x_{t,S}h_{t,S}\le b\). Each resident receives an integral package; the type-level allocation can be fractional. For a weighted preference criterion with per-resident score \(u_t(S)\), the population score is
\[ U(x)=\sum_{t\in T}\sum_{S\in\mathcal S_t}x_{t,S}u_t(S). \]
This lifts asprin’s weighted preference comparison to average satisfaction across the population.

My lead anchor is Theorem 1, proved in this paper. It states that, given a program \(P\) and preference statement \(s\), Algorithm 1 computes a \(\succ_s\)-preferred stable model of \(P\) if \(P\) is satisfiable, and returns \(\bot\) otherwise. Its continuous question is One Preferred Cohort Allocation\(_\infty\): given the type programs, masses, resource constraints, and a weighted preference criterion, find a feasible \(x\) minimizing \(U(x)\), or report infeasibility. A solution can be given as a finite list of nonzero \((t,S,x_{t,S})\) entries.

The second anchor is Theorem 2, also proved here. It states that, given \(P\) and \(s\), Algorithm 2 computes all \(\succ_s\)-preferred stable models; the paper’s setup for this result restricts preferences to comparisons decidable in polynomial time, represented by stratified preference programs. Its mirror is All Preferred Cohort Allocations\(_\infty\) on the same instance family: return the vertices of the optimal face \(F^*=\arg\min_x U(x)\). Their convex hull describes every preferred population allocation. This gives a finite output even when the continuum has infinitely many optimal allocations.

I expect the unrestricted one-allocation problem to be Class B: hardness in the local ASP choice structure survives the continuous population. With one type and no aggregate coupling, feasible population states form the convex hull of the incidence vectors of stable models. A linear preference optimum occurs at a stable-model vertex, so this case retains the original preferred-answer-set optimization problem. There should also be Class A subfamilies: when pricing over feasible local packages is polynomial, the aggregate problem is an LP amenable to column generation. For the all-allocation problem, the optimal face may have many vertices, so output size is a separate cost.

The mirror covers preference optimization over feasible answer sets, particularly weighted preferences and their population averages. It does not claim to cover every user-defined preference type or every use of asprin. Natural follow-up questions include which local ASP languages admit polynomial pricing, how large the optimal-face description can be, and how the continuous optimum compares with allocations restricted to multiples of \(1/N\).

The weakest point is the interpretation of an answer set as a resident’s feasible package. In the paper, a stable model can describe a global logical world with no agent-level decomposition. The mirror is persuasive for applications where an ASP program describes repeated local decisions and the preference criterion aggregates across residents. Extending it to arbitrary global programs would need a separate modeling argument. Also, Theorems 1 and 2 establish algorithmic correctness, not polynomial running time; the complexity expectations above belong to the proposed mirrors, not to claims made by those theorems.