A game theoretic approach to a problem in polymatroid maximization

Lisa Hellerstein, Thomas Lidbetter

    Research output: Contribution to journalArticlepeer-review


    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


    • Game theory
    • Queuing
    • Search games
    • Sequential testing

    ASJC Scopus subject areas

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


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

    Cite this