Stackelberg thresholds in network routing games or the value of altruism

It is well known that the Nash equilibrium in network routing games can have strictly higher cost than the optimum cost. In Stackelberg routing games, where a fraction of flow is centrally-controlled, a natural problem is to route the centrally-controlled flow such that the overall cost of the resulting equilibrium is minimized.We consider the scenario where the network administrator wants to know the minimum amount of centrally-controlled flow such that the cost of the resulting equilibrium solution is strictly less than the cost of the Nash equilibrium. We call this threshold the Stackelberg threshold and prove that for networks of parallel links with linear latency functions, it is equal to the minimum of the Nash flows on links carrying more optimum flow than Nash flow.Our approach also provides a simpler proof of characterization of the minimum fraction that must be centrally controlled to induce the optimum solution.     

The price of anarchy of serial, average and incremental cost sharing

We compute the price of anarchy (PoA) of three familiar demand games, i.e., the smallest ratio of the equilibrium to efficient surplus, over all convex preferences quasi-linear in money. For any convex cost, the PoA is at least in the average and serial games, where n is the number of users. It is zero in the incremental game for piecewise linear cost functions. With quadratic costs, the PoA of the serial game is , and for the average and incremental games. This generalizes if the marginal cost is convex or concave, and its elasticity is bounded.      

A geometric approach to the price of anarchy in nonatomic congestion games

We present a short, geometric proof for the price-of-anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks and on nonatomic congestion games. This novel proof also facilitates two new types of theoretical results: On the one hand, we give pseudo-approximation results that depend on the class of allowable cost functions. On the other hand, we derive stronger bounds on the inefficiency of equilibria for situations in which the equilibrium costs are within reasonable limits of the fixed costs. These tighter bounds help to explain empirical observations in vehicular traffic networks. Our analysis holds in the more general context of nonatomic congestion games, which provide the framework in which we describe this work.     

Strong equilibrium in cost sharing connection games

We study network games in which each player wishes to connect his source and sink, and the cost of each edge is shared among its users either equally (in Fair Connection Games—FCG's) or arbitrarily (in General Connection Games—GCG's). We study the existence and quality of strong equilibria (SE)—strategy profiles from which no coalition can improve the cost of each of its members—in these settings. We show that SE always exist in the following games: (1) Single source and sink FCG's and GCG's. (2) Single source multiple sinks FCG's and GCG's on series parallel graphs. (3) Multi source and sink FCG's on extension parallel graphs. As for the quality of the SE, in any FCG with n players, the cost of any SE is bounded by H(n) (i.e., the harmonic sum), contrasted with the Θ(n) price of anarchy. For any GCG, any SE is optimal.     

The political economy of organized crime: providing protection when the state does not

Organized crime emerges out of the power vaccuum that is created by the absence of state enforcement, and which can have many sources: geographic, social, and ethnic distance, prohibition, or simply collapse of state institutions. Mafias and gangs are hierarchically organized and can be thought of as providing primitive state functions, with economic costs that are typically much higher than those associated with modern governance. Though organized crime cannot be completely eradicated, its control is necessary, since it can easily corrupt existing institutions of governance. Some thoughts on what can be done to control organized crime are offered.     

Conflict,Cooperation and Competition in Anarchy

Caplan and Stringham (2002) attempt to rebut the paradox of cooperation (Cowen and Sutter 1999) as it applies to libertarian anarchy. The paradox in the context of anarchy implies that if private defense agencies can cooperate to avoid conflict they can also collude to reestablish coercion. Caplan and Stringham argue that arbitration is self-enforcing while collusion requires solution of a prisoners dilemma. We agree that collusion requires more cooperative efficacy than arbitration, but maintain that arbitration requires considerably more organization than a simple coordination game. If a network of protection agencies can organize sufficiently to arbitrate disputes, they can also create a barrier to entry by refusing to arbitrate with entrants.     

对无政府状态下自由市场经济的挑战——试析1929年大萧条及其现实意义

伴随着1929年10月24日美国纽约股票市场股票价格狂跌,一场横扫资本主义世界各国的全球性经济危机爆发了,这给以英美为代表的资本主义国家的经济、工农业等领域造成了不可估量的损失。这次大萧条是对于无政府状态下的自由市场经济的挑战和否定。反观2007年的全球经济,次贷危机、层出不穷的不确定性因素对于经济发展造成的动荡,使得中国经济的高速发展面临严峻的挑战。正如温家宝总理在连任后的首场记者招待会上所言,2008年中国进入"经济最困难的一年"。因此,对于新一届的政府,在规范和依靠市场体制的前提下,如何促进政府宏观调控与市场自我调解机制之间的良性互动,如何保持经济发展和抑制通胀之间的平衡,是关系到中国经济发展模式转变的核心问题。     

The price of anarchy in competitive reverse supply chains with quality-dependent price-only contracts

To quantify the efficiency of decentralized competitive reverse supply chains (RSCs) with quality-dependent price-only contracts, we characterize the worst-case efficiency loss with the price of anarchy (PoA). Several scenarios with unilateral or bilateral horizontal competition under push or pull configurations of RSCs are discussed. Given the uncertainty in the returns of used products, we consider different consumers’ return behaviors and investigate the effect of the quality levels of used products. We clarify the effect of horizontal competition for each scenario and find distinctive features of RSCs that differentiate them from traditional forward activities. Additional managerial insights are provided for discussion.     

How bad is forming your own opinion?

The question of how people form their opinion has fascinated economists and sociologists for long time. In many of the models, a group of people in a social network, each holding a numerical opinion, arrive at a shared opinion through repeated averaging with their neighbors in the network. Motivated by the observation that in reality consensus is rarely reached, we study a related sociological model in which individuals' intrinsic beliefs counterbalance the averaging process and yield a diversity of opinions.We interpret the repeated averaging process as best-response dynamics in an underlying game with natural payoffs and its limit as an equilibrium. This allows us to study the cost of disagreement by comparing between the cost at equilibrium and the social optimum. We also consider a natural network design problem in this setting: which links can we add to the underlying network to reduce the cost at equilibrium?