Abstract
This paper, originally presented at AAAI-20, introduces a formal mathematical framework for addressing homophily bias in committee-based decision-making. Homophily—the tendency of individuals to favor those similar to themselves—often skews the selection process in academic hiring, corporate promotions, and peer review. By representing candidates and experts as points in a metric space, the authors demonstrate that strategic committee composition and a novel "minimal regret" voting rule can effectively mitigate these biases. The research distinguishes between universal committees, designed for any potential candidate pool, and ad-hoc committees, tailored to specific candidates, revealing a significant efficiency advantage for the latter in high-dimensional spaces.
Introduction
In many professional and social contexts, we rely on committees of experts to identify the highest-quality candidates. However, experts are rarely perfectly objective. They are prone to homophily, overvaluing candidates who share their research interests, background, or values. Traditional social choice theory typically focuses on preference aggregation (maximizing collective satisfaction) or information aggregation (reducing noise). This paper pivots to a different challenge: bias mitigation. The goal is to design a committee and a voting mechanism that can extract the "true" quality of candidates despite the inherent spatial biases of the experts involved.
Modeling Bias in Metric Spaces
The authors model the selection process by placing candidates and experts within a metric space, such as a 1D line representing a spectrum of research methodologies or a $d$-dimensional hypercube representing multiple attributes.
In this model, each candidate $j$ possesses an objective quality $q_j$. An expert $i$ does not perceive this quality directly. Instead, they observe a "grade" $g_i(j)$ that is discounted by the distance $d(e_i, c_j)$ between the expert's position $e_i$ and the candidate's position $c_j$: $$g_i(j) = q_j - d(e_i, c_j)$$ The expert then votes for the candidate who yields the highest perceived grade. This simple formulation captures the essence of homophily: a nearby candidate of moderate quality may appear superior to a distant candidate of high quality.
As shown in Figure 1, the placement of experts relative to candidates is crucial. In scenario (b), an expert placed at 0 might vote for a lower-quality candidate at 0 ($q=0.1$) over a higher-quality candidate at -1 ($q=0.2$) simply because the former is closer.
The Minimal Regret Voting Rule
Standard voting rules, such as plurality or majority vote, are often inadequate for bias mitigation. If a majority of experts are clustered in one region of the metric space, they will consistently favor local candidates, potentially ignoring a vastly superior candidate from a different region.
To solve this, the authors propose a Minimal Regret Voting Rule. Rather than simply counting votes, this rule treats each expert's vote as a linear constraint on the possible "true" qualities of the candidates. If expert $i$ votes for candidate $j$ over candidate $k$, it implies: $$q_j - d(e_i, c_j) \geq q_k - d(e_i, c_k)$$ By modeling these constraints as a directed graph where edge weights represent distance-based biases, the decision-maker (the "dean") can use shortest-path algorithms to identify the candidate that minimizes the maximum possible "regret"—the difference between the chosen candidate's quality and that of the objectively best candidate.
Universal vs. Ad-hoc Committees
A key contribution of the paper is the analysis of committee types:
- Universal Committees: These are formed before the candidates are known. To guarantee low regret, these committees must "cover" the entire metric space. In high dimensions, the number of experts required grows exponentially ($O(1/\epsilon^d)$), a manifestation of the "curse of dimensionality."
- Ad-hoc Committees: These are formed after the candidates' positions in the metric space are known. The authors prove that ad-hoc committees are significantly more efficient. Regardless of the number of dimensions, an ad-hoc committee only requires $O(m^2/\epsilon)$ experts, where $m$ is the number of candidates.
Key Results and Computational Efficiency
The theoretical analysis yields several important findings:
- Efficient Computation: The minimal regret candidate can be identified in $O(mk + m^3)$ time, making the approach computationally feasible for real-world committee sizes.
- Tight Bounds in 1D: For a single-dimension interval, a committee of size $O(m/\epsilon)$ is both necessary and sufficient to ensure a regret of at most $\epsilon$.
- Hardness in General Spaces: While the problem is tractable in Euclidean spaces, finding the smallest "perfect" committee in general discrete metric spaces is NP-hard to approximate.
Limitations and Future Work
While the framework provides a robust mathematical foundation for bias mitigation, several avenues for future research remain. The current model assumes experts vote truthfully based on their biased perceptions; however, strategic voting—where experts manipulate their votes to achieve a specific outcome—could complicate the results. Additionally, the model assumes the decision-maker knows the exact coordinates of all participants in the metric space, which is often difficult to determine in practice. Future work could explore more complex signals, such as ranked preferences, which might further reduce the required committee size and improve the robustness of the selection process.
Summary updated