A Game Theoretic Approach to a Problem in Polymatroid Maximization

DOI10.1016/J.EJOR.2022.06.018MaRDI QIDQ6365771arXivFDO

Authors Lisa Hellerstein, Thomas Lidbetter

Publication date 20 April 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.EJOR.2022.06.018

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

arXiv classification

math.OC cs.GT cs.DM

Abstract: We consider the problem of maximizing the minimum (weighted) value of all components of a vector over a polymatroid. This is a special case of the lexicographically optimal base problem introduced and solved by Fujishige. We give an alternative formulation of the problem as a zero-sum game between a maximizing player whose mixed strategy set is the base of the polymatroid and a minimizing player whose mixed strategy set is a simplex. We show that this game and three variations of it unify several problems in search, sequential testing and queuing. We give a new, short derivation of optimal strategies for both players and an expression for the value of the game. Furthermore, we give a characterization of the set of optimal strategies for the minimizing player and we consider special cases for which optimal strategies can be found particularly easily.

This page was built for publication: A Game Theoretic Approach to a Problem in Polymatroid Maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6365771)