d4-conf-aaai-2021-1184

The strongest mirror I see is the paper’s committee-selection setting, made genuinely population based. Consider a large association choosing a committee of \(k\) candidates. Members have complete rankings of the candidates, and everyone with the same ranking is one type. Give each type \(t\) the same fixed positive candidate scores \(a_t(e)\), for example Borda scores. If the society has type masses \(\mu_t\), its per-person score for candidate \(e\) is

\[ w_\mu(e)=\sum_{t\in T}\mu_t a_t(e). \]

Choosing a committee \(B\) maximizes \(U_\mu(B)=\sum_{e\in B}w_\mu(e)\). The feasible committees form a uniform matroid. Here mass means the fraction of members with each ranking; it is the society being continuized, while the committee remains discrete.

To match the paper’s elicitation problem, suppose the true distribution \(\mu^\star\) is not yet known exactly, but lies in a supplied rational polytope \(\mathcal P\subseteq\Delta(T)\), reflecting incomplete polling or census data. The support has size \(\tau\), with \(N\) members and \(\tau\ll N\). A query asks for the society’s aggregate comparison of two candidates, \(e\) and \(f\). Its answer imposes a linear constraint such as \(\sum_t\mu_t(a_t(e)-a_t(f))\ge 0\), narrowing the possible populations. The paper’s uncertainty set \(W\) becomes \(\mathcal W_{\mathcal P}=\{w_\mu:\mu\in\mathcal P\}\).

My lead is Proposition 1, proved in this paper. It says that the Interactive Greedy Algorithm, for a matroid with unknown positive additive element weights consistent with the elicited comparisons, returns a base \(B\) whose maximum regret over all still-admissible weight functions is at most \(\delta\). The algorithm constructs a base greedily, asking comparisons among remaining elements until their minimax regret is at most \(\delta/r(M)\), then adding an element whose maximum regret against those elements meets that threshold when independent. Its guarantee is proved here by induction using the matroid axioms. The paper also says the algorithm asks only polynomially many queries, since there are only polynomially many element comparisons to make.

The corresponding continuous problem is Continuous-Population Greedy Matroid Choice: given a matroid, type-specific candidate scores \(a_t(e)\), and the possible society distributions \(\mathcal P\), elicit aggregate candidate comparisons and return a base satisfying

\[ \max_{\mu\in\mathcal P_{\!P}} \left[\max_{B'\in\mathcal B}U_\mu(B')-U_\mu(B)\right]\le\delta, \]

where \(\mathcal P_{\!P}\) is the set of distributions still consistent with the answers. The base is the decision; regret is measured as per-person score loss. This is a direct substitution of the possible aggregate population weights \(w_\mu\) for the paper’s possible weights \(w\). The proof needs additivity and matroid exchange, not that there is literally one decision maker, so the guarantee carries over when aggregate comparisons are truthful and the uncertainty set contains the true population.

I expect this lead problem to be Class A for an explicitly represented rational polytope \(\mathcal P\) and a polynomially queryable matroid. The aggregate scores and query constraints are linear in the \(\tau\) masses; the relevant candidate comparisons and regrets can be computed with linear programs. The resulting parameters are the number of candidates \(m\), support size \(\tau\), and encoding length \(L\), rather than the headcount \(N\). The paper does not prove a general polynomial running-time bound for every regret calculation, so that is a prediction for this specified model, not a result I attribute to Proposition 1. It also raises the question of whether richer matroid families preserve the same efficient regret computations.

A second anchor is Proposition 2, also proved here. It says the Interactive Local Search Algorithm returns a base with maximum regret at most \(\delta\). Starting from a base, it considers bases obtained by exchanging one element, elicits until the neighborhood’s minimax regret is at most \(\delta/r(M)\), and either stops when the current base meets the threshold or moves to a neighbor selected by minimum maximum regret. Its proof uses the matroid multiple-exchange theorem of Greene and Magnanti (1975) to relate any base to the current base’s one-exchange neighborhood. The article also states that the additive-weight version asks polynomially many queries.

That gives Continuous-Population Exchange Elicitation: use the same \(\mathcal P\), social comparisons, welfare, and regret criterion, but require the output policy to search through single-element exchanges. I also expect this version to be tractable for committee selection: the neighborhood has polynomial size and each swap’s regret is a linear optimization over \(\mathcal P_{\!P}\). The paper’s proposition guarantees the quality of the answer; by itself it does not establish a polynomial bound on the total number of exchange iterations. Proving such a bound, or finding a regime where the exchange process takes too long, is a further question.

These are performance-guarantee anchors, not numbered hardness or complexity-class theorems; the paper contains no comparable named hardness result. The mirror covers its interactive matroid optimization and committee application, not its experimental findings or proposed extension to submodular utilities.

The weak point is that the paper studies one decision maker’s uncertain utility, whereas this mirror needs an aggregate welfare model and a society-level comparison oracle. The Borda scores make rankings cardinal and comparable across types, and an association choosing a committee by a declared aggregate scoring rule is a plausible setting. Still, that is an added social-choice assumption: an ordinary electorate’s pairwise votes do not automatically reveal utilitarian score comparisons. The mirror stands if the authors accept this committee setting as their problem with a continuous population behind its aggregate weights; it would be a poor mirror if they require the original single-DM query model to remain untouched.