A game theoretic approach to a problem in polymatroid maximization

Lisa Hellerstein, Thomas Lidbetter

    Research output: Contribution to journalArticlepeer-review

    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.

    Original languageEnglish (US)
    JournalEuropean Journal of Operational Research
    DOIs
    StateAccepted/In press - 2022

    Keywords

    • 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

    Fingerprint

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

    Cite this