d4-conf-ecai-2023-0301

My strongest case is a population version of the paper’s path-independent enforcement result, using the paper’s own “possibly optimal” choice functions.

Take a large public consultation or recommendation service with a fixed finite catalog \(\Omega\). A user’s type is their complete preference-elicitation state: for example, the same reported comparisons and the same feasible set \(Y_t\) of utility weights. Given a menu \(B\subseteq\Omega\), type \(t\) regards \(\alpha\in B\) as possibly optimal when some \(w\in Y_t\) makes \(\alpha\) at least as good as every \(\beta\in B\). Thus each type has the choice function \(\mathrm{PO}_t(B)\) described in Section 2.3. Users with identical model-relevant information are one type; if \(N_t\) of \(N\) users have that type, its mass is \(\mu_t=N_t/N\). The relevant regime is a very large population with a moderate number \(\tau\) of distinct elicitation types—for instance, many respondents reusing the same elicitation templates.

For a fixed quorum \(q\in(0,1]\), define the population’s raw choice function by
\[ F_\mu^q(B)=\left\{\alpha\in B:\sum_{t:\,\alpha\in\mathrm{PO}_t(B)}\mu_t\ge q\right\}. \]
It returns the alternatives that at least a \(q\)-fraction of the population regard as possibly optimal. Since each \(\mathrm{PO}_t\) satisfies Heritage, \(F_\mu^q\) does too: if an alternative meets the quorum in \(B\), it meets it in every smaller menu containing it. The society is the continuous object here; the catalog and the returned choice set remain finite.

Lead mirror: Mass-Quorum PI Enforcement. An instance consists of \(\Omega\); a finite support \(T\) with binary-rational masses \(\mu_t\) summing to \(1\); compact preference inputs defining each \(\mathrm{PO}_t\); a rational quorum \(q\); and a query menu \(A\subseteq\Omega\). Compute the exact set \(F_\mu^q{}^{(\pi)}(A)\), the path-independent enforcement of the quorum choice function at \(A\). This is a choice-set computation, not an optimization over allocations: a solution is the resulting subset of \(A\), which may be empty, just as the paper allows inconsistent choice functions.

The anchor is Theorem 3, proved in this paper (with proofs also collected in the cited longer version [24]). In full, for any choice function \(\mathrm{Op}\) satisfying Heritage and any \(A\subseteq\Omega\), start with \(B_0=\Omega\) and iterate
\[ B_i=A\cup\bigl(B_{i-1}\setminus\mathrm{Op}(B_{i-1})\bigr). \]
The sequence reaches a fixed point \(B_k\) after at most \(|\Omega|-|A|\) strict decreases; at that point \(\mathrm{Op}(B_k)\subseteq A\), and the theorem gives \(\mathrm{Op}^{(\pi)}(A)=\mathrm{Op}(B_k)\). Applying it to \(F_\mu^q\) yields the requested answer. The theorem’s stated bound is on evaluations of the input choice function. With the type inputs above, each evaluation can be computed by testing possible optimality for each type and summing masses. Those tests are linear-feasibility checks in the paper’s linear-utility model, so the resulting algorithm is polynomial in \(m=|\Omega|\), \(\tau\), the preference-input size and the bit lengths of \(\mu\) and \(q\); it does not depend on \(N\) except through the encoded masses. This is a Class A expectation, conditional on polynomially evaluable type inputs.

The connection to the paper is unusually direct for an extension: it studies combining agents’ choice functions, shows that natural combinations can lose Outcast, and develops ways to restore path independence. Its conclusion explicitly points to social choice functions generated by voting under uncertainty as future work. A quorum over possible-optimal sets is a concrete population aggregation of that kind, and Theorem 3 applies because the quorum aggregate satisfies its Heritage premise. For a discrete electorate, the same quorum can be expressed as a count threshold; when \(\mu_t=N_t/N\), it agrees exactly with the mass definition. The continuous formulation makes the population fractions and support size explicit.

The scope is this enforcement result, not the paper’s consistency-restoration methods or every proposed way of combining preferences. The paper has no comparable named hardness result to anchor a hardness-transfer question, so this case is about an algorithmic result.

The weak point is that the paper analyzes pairwise combination operations, not this quorum aggregator. The authors would have to accept the population quorum as a sensible extension of their choice-function combination problem. I think they plausibly would, particularly given their stated future-work direction, but this mirror is less secure than one built on a population model the paper already studies.