2026-09-26T20:39:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25621 2026-09-23T23:45:06Z ddc:004 open_access

The Importance of Parameters in Ranking Functions Standke, Christoph Tziavelis, Nikolaos Gatterbauer, Wolfgang Kimelfeld, Benny Ranking Explanation Shapley value SHAP scores How important is the weight of a given column in determining the ranking of tuples in a table? To address such an explanation question about a ranking function, we investigate the computation of SHAP scores for column weights, adopting a recent framework by Grohe et al. [ICDT'24]. The exact definition of this score depends on three key components: (1) the ranking function in use, (2) an effect function that quantifies the impact of using alternative weights on the ranking, and (3) an underlying weight distribution. We analyze the computational complexity of different instantiations of this framework for a range of fundamental ranking and effect functions, focusing on probabilistically independent finite distributions for individual columns. For the ranking functions, we examine lexicographic orders and score-based orders defined by the summation, minimum, and maximum functions. For the effect functions, we consider global, top-k, and local perspectives: global measures quantify the divergence between the perturbed and original rankings, top-k measures inspect the change in the set of top-k answers, and local measures capture the impact on an individual tuple of interest. Although all cases admit an additive fully polynomial-time randomized approximation scheme (FPRAS), we establish the complexity of exact computation, identifying which cases are solvable in polynomial time and which are #P-hard. We further show that all complexity results, lower bounds and upper bounds, extend to a related task of computing the Shapley value of whole columns (regardless of their weight). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christoph Standke and Nikolaos Tziavelis and Wolfgang Gatterbauer and Benny Kimelfeld 2026 Is Part Of LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2026.7 urn:nbn:de:0030-drops-256217 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode