d4-conf-aaai-2022-1399

My lead is a continuous version of the paper’s probabilistic envy audit, anchored on Theorem 2 (proved in this paper). It is the strongest fit because it already measures fairness by fractions of users and policies. The paper has no NP-hardness or polynomial-time classification result; its computational result is about sample efficiency.

The mirror is a recommender population with finite type support \(T\), \(|T|=\tau\), and rational masses \(\mu_t\) summing to one. A type \(t\) is the complete tuple of quantities relevant to the audit: its context distribution \(q_t\), reward law \(\nu_t\), and current recommendation policy \(\pi_t\). Thus two users share a type only if they are indistinguishable in all three. Mass \(\mu_t\) is their fraction of the population. For a target of type \(t\), write \(U_t(s)\) for its expected reward when shown source type \(s\)’s policy \(\pi_s\), using \(t\)’s own contexts and reward law.

This gives a direct mass version of the paper’s relaxed criterion. Type \(t\) is \((\epsilon,\gamma)\)-envious if
\[ \sum_{s\in T}\mu_s\,\mathbf{1}\!\left[U_t(s)>U_t(t)+\epsilon\right]>\gamma. \]
The population is \((\epsilon,\gamma,\lambda)\)-envy-free if the total mass of such target types is at most \(\lambda\). The paper’s finite uniform draws of users become draws from \(\mu\); excluding the particular target individual has no effect in the continuum.

Call the problem Mass-AUDIT. Its input is this finite-support population, interaction access to rewards in \([0,1]\), and parameters \(\epsilon,\gamma,\lambda,\alpha,\delta\). It adaptively chooses which target types to audit and, for each target, whether to show that target its own policy or a policy sampled from a source type. The decision variable each round is the source policy shown. The goal is to produce an envy certificate or an alert while minimizing audit duration and utility loss. For each audited target type, the conservative constraint is that at every horizon \(r\), the average expected reward from the policies shown is at least \((1-\alpha)U_t(t)\). Because members of a type have identical response laws, an audit of that type applies to its whole mass.

In a plausible regime, millions of users belong to a much smaller set of stable recommendation cells: users with the same context and reward distributions, served by the same policy template. Repeated cohorts in a platform with fixed preference profiles and policy variants are a reasonable example. Crucially, a type must include the reward response and current policy, not just a demographic label. The mirror would be a poor fit if nearly every user has a distinct response model or policy, making \(\tau\) close to the population size.

Theorem 2 sets
\[ \widetilde M=\left\lceil\frac{\log(3/\delta)}{\lambda}\right\rceil, \qquad K=\left\lceil\frac{\log(3\widetilde M/\delta)} {\log(1/(1-\gamma))}\right\rceil. \]
It samples \(\widetilde M\) target users and \(K\) other users’ policies per target, then runs OCEF with confidence parameter \(\delta/(3\widetilde M)\). With probability at least \(1-\delta\), AUDIT is correct, satisfies the conservative constraint for all sampled targets, and the duration and cost bounds from Theorem 1 hold simultaneously for those targets. In Mass-AUDIT, the corresponding draws are from \(\mu\), so the sample counts do not depend on the total population size.

For completeness, the per-target bounds inherited from Theorem 1 use \(\mu_0=U_t(t)\), \(\mu_k=U_t(s_k)\),
\[ \eta_k=\max\{\mu_k-\mu_0,\ \mu_0+\epsilon-\mu_k\}, \qquad h_k=\max\{1,1/\eta_k\}, \]
where \(s_k\) is the \(k\)-th sampled source type. With \(\delta'=\delta/(3\widetilde M)\), the duration is
\[ O\!\left( \sum_{k=1}^{K} \frac{h_k}{\min\{\alpha\mu_0,\eta_k\}} \log\!\left( \frac{K\log(Kh_k/(\delta'\eta_k))}{\delta'} \right)\right), \]
and the cost is
\[ O\!\left( \sum_{k:\mu_k<\mu_0} \frac{(\mu_0-\mu_k)h_k}{\eta_k} \log\!\left( \frac{K\log(Kh_k/(\delta'\eta_k))}{\delta'} \right)\right). \]
These are sampling and interaction bounds, not a claim that the audit is an exact LP or has a polynomial-time worst-case complexity bound.

I expect this mirror to be tractable in the paper’s statistical sense: the paper’s sampling method transfers naturally to type draws, and the number of users disappears from the probabilistic audit’s sample counts. The authors should recognize it as their problem: it preserves the target user’s preferences, tests policies from other users, and protects recommendation performance during exploration. It covers the auditing results, especially Theorem 2 and its OCEF guarantees; it does not mirror the paper’s separate analysis of envy-free policy design or item-side fairness.

Several follow-up questions matter: how the audit’s resources depend on explicit support size \(\tau\) and the bit lengths of \(\mu_t\); how finite high-multiplicity cohorts approximate the mass-sampling model when some types have few representatives; and how robust the results are when users are clustered approximately rather than having identical reward laws. The exact envy criterion would also require checking every positive-mass source type, whereas Theorem 2 addresses the probabilistic relaxation.

The weakest point is that the paper already gets its main population-size benefit without continuization: its probabilistic audit is independent of \(M\). The continuous mirror is therefore a clean high-multiplicity formulation and a useful test of type aggregation, but it does not presently reveal a new computational tractability gain. It also sits outside the programme’s usual LP and separation-problem pattern. Its case rests on the model being a sensible population-level audit problem, not on claiming that the continuum unlocks a known optimization technique.