A Mirage of Market Allocation
  Can noncooperative behaviour of merchants lead to a market split that prima facie seems anticompetitive? We introduce a model in which service providers, with ISPs being the main example, aim at optimizing the number of customers using their services, while customers aim at choosing service providers with low customer load (high bandwidth per subscriber, for ISPs). Each service provider chooses between a variety of levels of service (latencies, for ISPs), and as long as it does not lose customers, aims at minimizing its level of service; the minimum level of service required to satisfy a customer varies across customers. We consider a two-stage competition: in the first stage, service providers select their levels of service; in the second stage, customers choose between service providers. In the two-stage game, we show that the competition among service providers possesses a unique Nash equilibrium, which is moreover super-strong; we also show that sequential better-response dynamics of service providers reach this equilibrium, with best-response dynamics doing so surprisingly fast. If service providers choose their levels of service according to this equilibrium, then the unique Nash equilibrium among customers in the second phase is a split of the market between the service providers, based on the customers' minimum acceptable quality of service; moreover, each service provider's chosen level of service is the lowest acceptable by the entirety of its market slice, seemingly making no attempt to attract other customers. Our results show that this prima facie market allocation (collusive split of the market) arises as the unique and highly robust outcome of noncooperative, even myopic, service-provider behaviour. These results are applicable to a wide variety of scenarios, from explaining phenomena observable in food markets, to shedding a surprising light on aspects of location theory. 
Yannai A. Gonczarowski and Moshe Tennenholtz
cs.GT