Leximin budget allocation across heterogeneous budgeted Markov decision processes

We study how to allocate a common budget across agents facing heterogeneous finite-horizon budgeted Markov decision processes so as to optimize the resulting value vector according to the leximin criterion. Boutilier and Lu (2016) show that, under deterministic policies, each agent’s attainable value is represented by finitely many budget-value pairs. Using this finite representation, we establish an exact two-stage decomposition of the leximin allocation problem. First, the leximin criterion requires maximizing the number of agents attaining positive value. Second, conditional on this maximum number, the planner must jointly decide which agents receive positive budgets and which budget levels are assigned to them. This second-stage finite problem can be formulated as a leximin multiple-choice knapsack problem with a cardinality constraint and solved exactly by dynamic programming.