d4-conf-aaai-2008-0190

My lead mirror is a large group choosing one shared alternative, such as a trip plan or product configuration. Each type \(\theta\) is a complete GAI utility model, including its utility tables and Tchebycheff weight; everyone of that type has the same preferences for every alternative. A society is a distribution \(\mu\) over the \(\tau\) supported types, with \(\mu_\theta\) the fraction of users of each type. The input gives those rational masses, the common product domain \(X\), and the type utilities. The regime is credible when many users repeat a relatively small set of elicited preference models, so the population size \(N\) is much larger than \(\tau\).

The named anchor is Proposition 1, proved in this paper. It says: if \(x_1,\ldots,x_k\) are the first \(k\) alternatives ranked by decreasing \(u_w\), and \(x^*\) is the one among them minimizing \(f_w\), then \(x^*\) is globally optimal for \(f_w\) whenever \(u_w(x_k)\le U-f_w(x^*)\). In other words, the paper’s stopping test certifies that no alternative later in the aggregate-utility ranking can improve the best compromise found so far.

The continuous problem is Continuous GAI Tchebycheff Compromise Search. Each type \(\theta\) has utility \(u_\theta(x)\), positive weight \(w_\theta\), and ideal benchmark \(r_\theta>\max_{x\in X}u_\theta(x)\). Choose a single \(x\in X\) minimizing the population’s worst weighted shortfall,
\[ F_\mu(x)=\operatorname*{ess\,sup}_{\theta\sim\mu} w_\theta\bigl(r_\theta-u_\theta(x)\bigr). \]
A solution is a minimizing alternative and its value \(F_\mu(x)\). Define
\[ A_\mu(x)=\int w_\theta u_\theta(x)\,d\mu(\theta), \qquad B_\mu=\int w_\theta r_\theta\,d\mu(\theta). \]
Rank alternatives by decreasing \(A_\mu\). For the best-so-far alternative \(x^*\), the continuous stopping test is \(A_\mu(x_k)\le B_\mu-F_\mu(x^*)\). Since \(B_\mu-A_\mu(x)\le F_\mu(x)\), every alternative ranked after \(x_k\) has shortfall at least \(F_\mu(x^*)\). This is Proposition 1’s certificate with finite averages replaced by population integrals. With a shared GAI structure, the aggregate utility remains GAI; differing structures can be combined using the paper’s triangulation approach.

The paper also states in prose that minimizing \(f_w\) is NP-hard for at least three attributes and two agents when each agent’s GAI utility contains a factor of size at least three, via a reduction from 3-SAT. That claim is not a numbered result, so it is not a second anchor. It does indicate the expected direction for the continuous optimization problem: hardness transfers when \(\tau\) is allowed to grow, since a finite instance embeds as a distribution assigning mass \(1/q\) to each of its \(q\) agents. The continuous stopping certificate remains valid, but it does not make exact optimization easy in the worst case. Natural follow-up questions are whether bounded \(\tau\), bounded GAI treewidth, or approximation yields efficient algorithms.

The authors would plausibly recognize this as their group compromise problem: it retains their common alternative, GAI utilities, and worst-case Tchebycheff objective. The mirror covers the compromise-search result and its stopping guarantee, not the paper’s individual choice and ranking procedures or every compromise criterion.

The main weakness is that \(F_\mu\) depends on which types have positive mass, but not on their relative shares: changing a type from \(1\%\) to \(40\%\) does not change the worst-case objective if the support stays fixed. The population masses do affect the aggregate ranking and thus the stopping certificate, but this remains a thinner role for mass than in objectives based on population welfare. Replacing the maximum with an average would make shares decisive, but would change the paper’s aggregation rule. The case is strongest where the actual goal is to protect the worst-served preference type, and where repeated full utility models make \(\tau\ll N\).