A game theoretic approach to a problem in polymatroid maximization

Lisa Hellerstein, Thomas Lidbetter

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)979-988
Number of pages10
JournalEuropean Journal of Operational Research
Issue number2
StatePublished - Mar 1 2023

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management
  • Industrial and Manufacturing Engineering


  • Game theory
  • Queuing
  • Search games
  • Sequential testing


Dive into the research topics of 'A game theoretic approach to a problem in polymatroid maximization'. Together they form a unique fingerprint.

Cite this