论文标题
多种代理的最小最大次数排名
Min-max Submodular Ranking for Multiple Agents
论文作者
论文摘要
在子模块排名（SR）问题中，输入由一组在地面元素集合中定义的函数组成。目标是订购元素，以使所有功能的值尽快在平均值，假设我们每次选择一个元素。这个问题足够灵活，可以捕获机器学习中的各种应用，包括决策树。 本文考虑了SR的Min-Max版本，其中多个实例共享地面集。在每个实例与代理相关联的视图中，最小最大问题是订购共同的元素，以最大程度地减少所有代理的最大目标 - 因此，为所有代理找到一个公平的解决方案。我们为此问题提供了近似算法，并证明了它们在为多种代理找到决策树的应用中的有效性。
In the submodular ranking (SR) problem, the input consists of a set of submodular functions defined on a ground set of elements. The goal is to order elements for all the functions to have value above a certain threshold as soon on average as possible, assuming we choose one element per time. The problem is flexible enough to capture various applications in machine learning, including decision trees. This paper considers the min-max version of SR where multiple instances share the ground set. With the view of each instance being associated with an agent, the min-max problem is to order the common elements to minimize the maximum objective of all agents -- thus, finding a fair solution for all agents. We give approximation algorithms for this problem and demonstrate their effectiveness in the application of finding a decision tree for multiple agents.
