Cheap labor can be expensive

Abstract

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 and based on these prices, consumers hire the cheapest available team capable of doing the job they need done. We define the labor cost in such a market as the ratio of the Nash equilibrium of the original market and the 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 labor cost for a variety of markets including s-t path markets, matroid markets and perfect bipartite matching markets. The differences in 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.