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)
    JournalEuropean Journal of Operational Research
    StateAccepted/In press - 2022


    • Game theory
    • Queuing
    • Search games
    • Sequential testing

    ASJC Scopus subject areas

    • Computer Science(all)
    • 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