Sequential Submodular Maximization and Applications to Ranking an Assortment of Products
研究了一类新的排列空间组合优化问题“顺序子模最大化”，为在线购物平台提供算法，在最大化用户参与度的同时兼顾不同人群的公平性，给出了最优近似算法。
The advents of online retailing and advertising have created new opportunities for online platforms to incorporate algorithmic techniques to improve shoppers’ experience and drive user engagement, which, in return, can help with the long-term growth of these platforms, and also to help with having socially aware operations that consider fairness across different demographic groups. Motivated by the product-ranking problem in online shopping, this paper introduces and studies a new class of combinatorial optimization problems over the space of permutations, which is referred to as “sequential submodular maximization.” Using this class of problems, it provides algorithmic solutions for maximizing users’ engagement and also for balancing the users’ engagement across different demographic groups of shoppers to obtain fairness. In particular, they propose an optimal (1 − 1/e)-approximation algorithms for maximizing users’ engagement and a bicriteria ((1 − 1/e) 2 , (1 − 1/e) 2 ) for maximizing users’ engagement subject to group fairness constraints.