Explaining Rankings with Hidden Group Bonuses Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26), August 09–13, 2026, Jeju Island, Republic of Korea DOI: 10.1145/3770855.3818145 ISBN: 979-8-4007-2259-2/2026/08 CCS: Information systems Retrieval models and ranking CCS: Social and professional topics User characteristics CCS: Information systems Learning to rank
Alvin Hong Yao Yan, Suraj Shetiya, Sujoy Bhore, Priyanka Golia, Diptarka Chakraborty · 2026
Read Explaining Rankings with Hidden Group Bonuses Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26), August 09–13, 2026, Jeju Island, Republic of Korea DOI: 10.1145/3770855.3818145 ISBN: 979-8-4007-2259-2/2026/08 CCS: Information systems Retrieval models and ranking CCS: Social and professional topics User characteristics CCS: Information systems Learning to rank by Alvin Hong Yao Yan, Suraj Shetiya, Sujoy Bhore, Priyanka Golia, Diptarka Chakraborty (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29444.txt.
Introduction
Alvin Hong Yao Yan studies ranking with hidden group bonuses. Determining a linear utility function that correlates with rankings is foundational, and these models assume visibility into the feature sets. But scenarios involve attributes that are hidden or partly observed, yet influence outcomes through bonuses. They study a variant where features are unobserved but may influence rankings through boosts. They develop a framework that infers the parameters and group bonuses matching rankings. Determining it is NP-hard, but with constant feature dimension and group count, a fast solution exists.
Catalog record
| CREATOR | Alvin Hong Yao Yan, Suraj Shetiya, Sujoy Bhore, Priyanka Golia, Diptarka Chakraborty |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74483 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29444
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Explaining Rankings with Hidden Group Bonuses Conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 09–13, 2026; Jeju Island, Republic of Korea Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26), August 09–13, 2026, Jeju Island, Republic of Korea DOI: 10.1145/3770855.3818145 ISBN: 979-8-4007-2259-2/2026/08 CCS: Information systems Retrieval models and ranking CCS: Social and professional topics User characteristics CCS: Information systems Learning to rank Alvin Hong Yao Yan, Suraj Shetiya, Sujoy Bhore, Priyanka Golia, Diptarka Chakraborty Abstract . Determining a linear utility function that correlates with observed candidate rankings is a foundational problem with applications in domains such as admissions, hiring, and recommendation systems, e.g., [Storandt and Funke, AAAI’19, Zhang et al., KDD’23, Wang et al., ICDE’24 (best paper award), Chen and Wong, VLDB’24]. Traditionally, these models assume full visibility into the feature sets used to determine the utility score. However, real-world scenarios often involve sensitive attributes that are hidden or partially observed, yet may influence outcomes through additive bonuses designed to promote fairness, as in [Gale and Marian, ICDE’24]. Motivated by such practical concerns, we study a variant of the ranking explanation problem where sensitive features are unobserved but may influence candidate rankings through group-specific linear boosts. We present a formal framework for modeling this problem and develop an algorithmic solution that leverages constraint satisfaction and automated reasoning techniques to jointly infer the linear scoring parameters and latent group bonuses consistent with the observed rankings. We further show that determining a satisfying linear function with group-specific bonuses is NP -hard in general, but when the feature dimension and the number of groups are constant, the problem admits a polynomial-time solution. Our approach is the first to address this nuanced variant, which captures key real-world challenges in fair ranking and admission systems. We perform extensive experiments on both real-world and synthetic datasets, demonstrating that our method effectively recovers hidden bonus structures and provides faithful explanations of observed ranking outcomes. † † cc-license: by Resource Availability: The source code of this paper has been made publicly available at https://doi.org/10.5281/zenodo.20322450 . 1. Introduction Ranking algorithms are central to numerous AI applications, including web search, recommender systems, and information retrieval. However, despite their pervasive use, the decision-making processes behind these algorithms often remain opaque, which raises critical concerns around trust, fairness, and accountability. As a result, explainability in ranking has emerged as a pressing research challenge within the AI community. Several recent works have sought to adapt principles from interpretable machine learning to the ranking setting ( 12 ; 13 ; 26 ) , aiming to generate faithful, user-understandable explanations for ranked outputs. Some approaches focus on post-hoc explanations, while others design models that are easier to interpret from the start ( 50 ; 1 ) . There is also increasing attention to broader goals like fairness and trust in ranked results ( 16 ; 44 ) . Yet, many basic questions remain open: what does it mean for a ranking to be explainable? How do we measure the quality of an explanation when the output is an ordered list instead of a single label? Modeling user preferences is a central challenge in multi-criteria decision-making. A common and effective approach is to formalize these preferences with a utility function that assigns a numerical score/utility to each candidate, thereby inducing a natural ordering. Candidates are typically characterized by a set of features, which can be distinguished as scoring attributes – that directly contribute to utility, and sensitive attributes – used to enforce auxiliary goals such as fairness or diversity. Among various functional forms, linear utility models are arguably the most widely adopted. Their prevalence stems from a powerful combination of simplicity and practical efficacy. The straightforward structure of a weighted sum not only facilitates deployment in large-scale systems like web search and recommender engines ( 37 ; 24 ; 53 ) but also offers inherent transparency ( 47 ; 21 ) . This transparency, simplicity, and effectiveness make linear utility-based models a natural starting point for research into explainability and learning to rank ( 4 ; 10 ; 11 ) , interactive learning ( 38 ; 59 ; 61 ) , reverse regret ( 57 ) (best paper award at ICDE’24), and the integration of fairness and diversity mechanisms ( 31 ; 23 ; 58 ) . Despite their simplicity, linear utilities have demonstrated competitive performance, confirming their status as a robust and versatile modeling choice, e.g., ( 42 ; 52 ) . We refer the readers to Section 7 for a more elaborate discussion on related works. Several works have studied how to quantify the distance between a given ranking and one induced by a (linear) utility function. Common notions include the number of violated pairwise orders, the distance to a consistent utility vector, and the minimum perturbation needed to make the ranking “linearizable”. Exact computation is often intractable in the presence of conflicting preferences, motivating the study of approximation and structural relaxations (e.g., ( 17 ; 15 ) ). In many real-life scenarios, a small additive bonus is essential to ensure that a linear utility-based ranking model aligns with observed outcomes. Such a bonus is primarily calculated based on the sensitive attributes ( 49 ; 3 ; 58 ) – separate from the scoring attributes used to compute utility – associated with each candidate or item. This often arises when external goals, such as affirmative action, fairness constraints, or prior trust scores, must be incorporated uniformly across items of certain groups. The application of compensatory additive bonuses to linear utilities is an approach that has been explored for promoting fairness in ranking systems ( 22 ) . Without such a term, even simple adjustments to promote underrepresented groups may not be achievable within the linear feature space, making the additive bonus a minimal yet powerful mechanism for enforcing policy-driven interventions (see ( 34 ) ). We motivate our problem with the following running example of diversity in University admissions. Candidate Group Test SAT Rank Score Score c_{1} - 9.8 2.0 3 c_{2} - 8.1 7.8 1 c_{3} - 7.2 8.6 2 c_{4} - 6.9 4.2 7 c_{5} UP 6.0 3.2 4 c_{6} UP 3.7 7.1 5 c_{7} - 5.1 8.0 6 c_{8} UP 4.5 3.5 8 Table 1. Example dataset of eight university applicants. Example 1 (University admissions). Consider a public university conducting its annual admissions, where applicants are ranked using a linear utility-based model . Academic performance is assessed through multiple indicators, such as entrance test and SAT scores, which are normalized, weighted, and linearly aggregated to compute a base utility score. As a public institution committed to diversity, equity, and inclusion (DEI), the university augments this model with an additive incentive mechanism . Recognizing that applicants from underprivileged (UP) backgrounds may face structural disadvantages affecting academic performance, an expert committee assigns a group-specific bonus score. This bonus is added to the base utility score of each applicant in the corresponding group, yielding an adjusted utility score that determines the final ranking. For example, suppose eight applicants apply, as shown in Table 1 . The candidates are ranked c_{2} , c_{3} , c_{1} , c_{5} , c_{6} ,