Min-Max Submodular Ranking for Multiple Agents

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings of the 37th AAAI Conference on Artificial Intelligence
EditorsBrian Williams, Yiling Chen, Jennifer Neville
Place of PublicationWashington, DC
PublisherAAAI press
Pages7061-7068
Volume37
ISBN (electronic)978-1-57735-880-0 (set)
Publication statusPublished - 2023

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
Number6
Volume37
ISSN (Print)2159-5399
ISSN (electronic)2374-3468

Conference

Title37th Association for the Advancement of Artificial Intelligence Conference on Artificial Intelligence (AAAI-23)
LocationWalter E. Washington Convention Center
PlaceUnited States
CityWashington
Period7 - 14 February 2023

Abstract

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. Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Citation Format(s)

Min-Max Submodular Ranking for Multiple Agents. / Chen, Qingyun; Im, Sungjin; Moseley, Benjamin et al.
Proceedings of the 37th AAAI Conference on Artificial Intelligence. ed. / Brian Williams; Yiling Chen; Jennifer Neville. Vol. 37 Washington, DC: AAAI press, 2023. p. 7061-7068 (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 37, No. 6).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review