A Test Score-Based Approach to Stochastic Submodular Optimization

Shreyas Sekar (), Milan Vojnovic () and Se-Young Yun ()
Additional contact information
Shreyas Sekar: Harvard Business School, Harvard University, Boston, Massachusetts 02163
Milan Vojnovic: Department of Statistics, London School of Economics (LSE), London WC2A 2AE, United Kingdom
Se-Young Yun: Graduate School of Artificial Intelligence, Korea Advanced Institute of Science and Technology (KAIST), Daejeon 34141, Republic of Korea

Management Science, 2021, vol. 67, issue 2, 1075-1092

Abstract: We study the canonical problem of maximizing a stochastic submodular function subject to a cardinality constraint, where the goal is to select a subset from a ground set of items with uncertain individual performances to maximize their expected group value. Although near-optimal algorithms have been proposed for this problem, practical concerns regarding scalability, compatibility with distributed implementation, and expensive oracle queries persist in large-scale applications. Motivated by online platforms that rely on individual item scores for content recommendation and team selection, we study a special class of algorithms that select items based solely on individual performance measures known as test scores . The central contribution of this work is a novel and systematic framework for designing test score–based algorithms for a broad class of naturally occurring utility functions. We introduce a new scoring mechanism that we refer to as replication test scores and prove that as long as the objective function satisfies a diminishing-returns condition, one can leverage these scores to compute solutions that are within a constant factor of the optimum. We then extend these scoring mechanisms to the more general stochastic submodular welfare-maximization problem, where the goal is to partition items into groups to maximize the sum of the expected group values. For this more difficult problem, we show that replication test scores can be used to develop an algorithm that approximates the optimal solution up to a logarithmic factor. The techniques presented in this work bridge the gap between the rigorous theoretical work on submodular optimization and simple, scalable heuristics that are useful in certain domains. In particular, our results establish that in many applications involving the selection and assignment of items, one can design algorithms that are intuitive and practically relevant with only a small loss in performance compared with the state-of-the-art approaches. This paper was accepted by Chung Piaw Teo, optimization.

Keywords: stochastic combinatorial optimization; submodular functions; welfare maximization; test scores (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/mnsc.2020.3585 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:67:y:2021:i:2:p:1075-1092

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().