A game theoretic approach to a problem in polymatroid maximization
A game theoretic approach to a problem in polymatroid maximization
复制标题
解决多类阵最大化问题的博弈论方法
DOI：
10.1016/j.ejor.2022.06.018
复制
发表时间：
2023
影响因子：
6.4
通讯作者：
Lidbetter, Thomas
中科院分区：
文献类型：
--
作者：
Hellerstein, Lisa;Lidbetter, Thomas
我们考虑在多拟阵上最大化向量所有分量的最小（加权）值的问题。这是 Fujishige 提出并解决的词典最优基问题的一个特例。我们给出了问题的另一种表述，即混合策略集是多拟阵基础的最大化玩家和混合策略集是单纯形的最小化玩家之间的零和博弈。我们证明这个游戏及其三个变体统一了搜索、顺序测试和排队中的几个问题。我们为双方玩家提供了一个新的、简短的最佳策略推导，并表达了游戏的价值。此外，我们给出了最小化玩家的最优策略集的特征，并且我们考虑了可以特别容易地找到最优策略的特殊情况。
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.
登录
查看更多内容
在并行机器上对不可靠的作业进行排序
影响因子：
2
作者：
A. Agnetis;P. Detti;M. Pranzo;M. Sodhi
通讯作者：
M. Sodhi
使用最佳响应预言机和搜索游戏的应用程序解决零和游戏
影响因子：
2.7
作者：
L. Hellerstein;T. Lidbetter;Daniel Pirutinsky
通讯作者：
Daniel Pirutinsky
DOI：
10.1287/moor.2013.0634
发表时间：
2014
期刊：
Math. Oper. Res.
影响因子：
--
作者：
S. Alpern;T. Lidbetter
通讯作者：
T. Lidbetter
顺序测试的吞吐量
DOI：
--
发表时间：
2001
期刊：
Conference on Integer Programming and Combinatorial Optimization
影响因子：
--
作者：
M. Kodialam
通讯作者：
M. Kodialam
DOI：
10.1287/moor.22.4.803
发表时间：
1997
期刊：
Math. Oper. Res.
影响因子：
--
作者：
S. Iwata;K. Murota;Maiko Shigeno
通讯作者：
Maiko Shigeno