Efficiency of equilibria in uniform matroid congestion games

摘要: Network routing games, and more generally congestion games play a central role in algorithmic game theory, comparable to the of traveling salesman problem combinatorial optimization. It is known that price anarchy independent network topology for non-atomic games. In other words, it structure strategy spaces players, affine cost functions equals 4/3. this paper, we show dependence on considerably intricate atomic More specifically, consider with where players are symmetric equal set bases k-uniform matroid. setting, strictly larger than singleton latter As our main result can be bounded from above by 28/13. This constitutes substantial improvement over bound 5/2, which tight arbitrary functions.