Crowdsourcing queue data causes infinite inefficiency? New mechanism limits it to 2x

A new paper from Hongbo Li, Lingjie Duan, and Ness Shroff (accepted by IEEE Transactions on Networking) tackles a fundamental tension in crowdsourced queueing systems. In services like restaurants, theme parks, or road networks, customers rely on real-time congestion reports to choose which queue to join. But because those reports become stale, efficient operation requires continued exploration of servers with uncertain states. Selfish customers avoid such exploration because it reduces their immediate utility, even though their observations would benefit future users. The researchers show this myopic behavior can cause an infinite price of anarchy (PoA) – meaning decentralized decision-making leads to arbitrarily large efficiency losses.

The authors prove that existing non-monetary mechanisms (like providing information without payments) fail because customers' choices actively reshape queue states, perpetuating the cycle. To solve this, they design a dynamic side-payment mechanism that periodically charges some customers and rewards others, discouraging excessive exploration while maintaining ex-post budget balance. This mechanism coordinates congestion management and information acquisition across heterogeneous servers, guaranteeing PoA below 2 – essentially at most double the optimal efficiency. Beyond worst-case guarantees, experiments using real datasets (e.g., from Yelp or traffic apps) show strong average-case performance, making the approach practical for deployment in crowdsourcing platforms and service systems.