Probabilistic Permutation Graph Search: Black-Box Optimization for Fairness in Ranking

Ali Vardasbi, Fatemeh Sarvi, Maarten de Rijke

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


There are several measures for fairness in ranking, based on different underlying assumptions and perspectives. textbackslashacPL optimization with the REINFORCE algorithm can be used for optimizing black-box objective functions over permutations. In particular, it can be used for optimizing fairness measures. However, though effective for queries with a moderate number of repeating sessions, textbackslashacPL optimization has room for improvement for queries with a small number of repeating sessions. In this paper, we present a novel way of representing permutation distributions, based on the notion of permutation graphs. Similar totextasciitildetextbackslashacPL, our distribution representation, calledtextasciitildetextbackslashacPPG, can be used for black-box optimization of fairness. Different fromtextasciitildetextbackslashacPL, where pointwise logits are used as the distribution parameters, intextasciitildetextbackslashacPPG pairwise inversion probabilities together with a reference permutation construct the distribution. As such, the reference permutation can be set to the best sampled permutation regarding the objective function, makingtextasciitildetextbackslashacPPG suitable for both deterministic and stochastic rankings. Our experiments show thattextasciitildetextbackslashacPPG, while comparable totextasciitildetextbackslashacPL for larger session repetitions (i.e., stochastic ranking), improves overtextasciitildetextbackslashacPL for optimizing fairness metrics for queries with one session (i.e., deterministic ranking). Additionally, when accurate utility estimations are available, e.g., in tabular models, the performance of textbackslashacPPG in fairness optimization is significantly boosted compared to lower quality utility estimations from a learning to rank model, leading to a large performance gap with PL. Finally, the pairwise probabilities make it possible to impose pairwise constraints such as "item d1 should always be ranked higher than item d2.'' Such constraints can be used to simultaneously optimize the fairness metric and control another objective such as ranking performance.
Original languageEnglish
Title of host publicationProceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Print)978-1-4503-8732-3
StatePublished - Jul 1 2022
Externally publishedYes

Publication series

NameSIGIR '22
PublisherAssociation for Computing Machinery


  • fairness in ranking
  • permutation distribution
  • permutation graph
  • plackett-luce


Dive into the research topics of 'Probabilistic Permutation Graph Search: Black-Box Optimization for Fairness in Ranking'. Together they form a unique fingerprint.
  • DL: ICAI Discovery Lab

    van Harmelen, F., De Rijke, M., Siebert, M., Hoekstra, R., Tsatsaronis, G., Groth, P., Cochez, M., Pernisch, R., Alivanistos, D., Mansoury, M., van Hoof, H., Pal, V., Pijnenburg, T., Mitra, P., Bey, T. & de Waard, A.


    Project: Research

Cite this