算法的なゲーム理論

最近目を通している論文はスタンフォード大学のラッフガーデン教授が書いた物です。　
The objective of Algorithmic Game Theory seems to be the application of theoretical computer science concepts like quantitative computational models and proven complexity bounds to traditional economic game theory concepts like utility, Nash equilibria, and competitive agents. The first ten pages of the paper cover two topics:
1. implementable algorithms to optimize an auction outcome. An implementable mechanism for allocation (winner selection) is one which, when combined with the correct payment mechanism, results in a simple mechanism. A mechanism is simple if truthful bidding maximizes the expected utility for each player.
The paper indicates that algorithms must be monotone in order to be implementable, i.e. a greater value causes a greater allocation. The paper is particularly interested in implementable polynomial time algorithms. Two auction types are single-parameter mechanisms and multi-parameter mechanisms. In single parameter mechanisms, the objective function for each player is t=v*w, where v is the unit valuation and w is the quantity allocated. A Vickrey auction would then seek to maximize SIGMA(i)ti. In a multi-parameter mechanism, there are multiple commodities, each with a separate value.
2. The second section discusses routing problems. Agents select paths in a network graph to send packets between source and target nodes. One point is that congestion in the network causes users to make choices which are not globally optimal (i.e. the total cost of all paths is not minimized). The metric of "Price of Anarchy" (POA) is introduced. This is the ratio of the costs of an equilibrium and an optimal flow. In a network of two nodes (Pigou), this increases with the degree of non-linearity of the traffic dependent cost function. In network cost-allocation games, the cost of each link is not traffic dependent, and a way to divide the cost among users is determined. Two such methods are the Shapley (divide cost evenly among link users) and ordered (first user pays entire cost) methods. The paper states that ordered cost sharing is exponentially better than Shapley cost sharing in an undirected network. I could verify this by connecting sets of parallel links, where each set of parallel links had an equilibrium with cost k for Shapley and cost 1 for ordered. However, the paper also states that ordered cost sharing is no better than Shapley cost sharing for directed networks. I do not understand how the directed case differs from the undirected vis-a-vis worst case total cost or POA. Another aspect I did not understand was the assertion that all cost-sharing methods guaranteed to induce at least one Nash equilibrium in every network are concatenations of Shapley values. The paper states that this shows that some methods outperform ordered cost sharing by a constant factor, but I cannot envision any network allocation game where the Nash equilibrium has a total cost lower than that obtained by ordered cost sharing.