ICS Theory Group

CompSci 269S, Spring 2007: Theory Seminar

May 11, 2007, in Bren Hall 1423

Cheap Labor Can Be Expensive

Ning Chen and Anna Karlin; appeared in SODA 2007

Presented by Matt Nguyen


We study markets in which consumers are trying to hire a team of agents to perform a complex task. Each agent in the market prices their labor, and based on these prices, consumers hire the cheapest available team capable of doing the job they need done. We define the cheap labor cost in such a market as the ratio of the best Nash equilibrium of the original market and the best possible Nash equilibrium of any of its submarkets, where "best" is defined with respect to consumers, i.e., we are looking at Nash equilibria in which the consumer pays the least. This definition is motivated by a "Braess-style" paradox: in certain kinds of marketplaces, competition, in the form of the availability of "cheap labor", can actually cause the prices paid by consumers to go up.

We present tight bounds on the cheap labor cost for a variety of markets including s-t path markets, matroid markets and perfect bipartite matching markets. The differences in cheap labor cost across markets demonstrate the complex relationship between the combinatorial structure of the marketplace and the advantages or more precisely, disadvantages to consumers due to competition.