The Flow Game: Leximin and Leximax Core Imputations
CoRR(2024)
摘要
Recently [Vaz24] gave mechanisms for finding leximin and leximax core
imputations for the assignment game and remarked, "Within the area of algorithm
design, the "right" technique for solving several types of algorithmic
questions was first discovered in the context of matching and later these
insights were applied to other problems. We expect a similar phenomenon here."
One of the games explicitly mentioned in this context was the flow game of
Kalai and Zemel [KZ82]. In this paper, we give strongly polynomial time
mechanisms for computing the leximin and leximax core imputations for the flow
game, among the set of core imputations that are captured as optimal solutions
to the dual LP. We address two versions: 1. The imputations are leximin and
leximax with respect to the distance labels of edges. 2. The imputations are
leximin and leximax with respect to the product of capacities of edges and
their distance labels.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要