New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Braess-like Paradoxes on a Bipartite Exchange Network: More Connections Are Not Always Better

SpeakerVitus Leung

Co-authorRandall A. LaViolette

We study a model of exchanges in which price is fixed and the amount transferred depends only on the supply, the demand, and the existence of a link between actors. The links induce a simply-connected bipartite graph. We prove that a trading session on the graph can reduce the demand to zero iff the graph consists of components each of which are complete bipartite and for each, the supply equals or exceeds the demand. Consequently, a Braess-like paradox can be generated for a minimally connected bipartite graph whose demand can be reduced to zero, because it may fail to do so as links are added.