Bruno Tuffin

Xinbo Shi, Yijie Peng, Bruno Tuffin

This paper addresses the challenge of improving finite sample performance in Ranking and Selection by developing a Bahadur-Rao type expansion for the Probability of Correct Selection (PCS). While traditional large deviations approximations captures PCS behavior in the asymptotic regime, they can lack precision in finite sample settings. Our approach enhances PCS approximation under limited simulation budgets, providing more accurate characterization of optimal sampling ratios and optimality conditions dependent of budgets. Algorithmically, we propose a novel finite budget allocation (FCBA) policy, which sequentially estimates the optimality conditions and accordingly balances the sampling ratios. We illustrate numerically on toy examples that our FCBA policy achieves superior PCS performance compared to tested traditional methods. As an extension, we note that the non-monotonic PCS behavior described in the literature for low-confidence scenarios can be attributed to the negligence of simultaneous incorrect binary comparisons in PCS approximations. We provide a refined expansion and a tailored allocation strategy to handle low-confidence scenarios, addressing the non-monotonicity issue.

Ahmed Kamoun, Patrick Maillé, Bruno Tuffin

Different search engines provide different outputs for the same keyword. This may be due to different definitions of relevance, and/or to different knowledge/anticipation of users' preferences, but rankings are also suspected to be biased towards own content, which may prejudicial to other content providers. In this paper, we make some initial steps toward a rigorous comparison and analysis of search engines, by proposing a definition for a consensual relevance of a page with respect to a keyword, from a set of search engines. More specifically, we look at the results of several search engines for a sample of keywords, and define for each keyword the visibility of a page based on its ranking over all search engines. This allows to define a score of the search engine for a keyword, and then its average score over all keywords. Based on the pages visibility, we can also define the consensus search engine as the one showing the most visible results for each keyword. We have implemented this model and present an analysis of the results.