To Rectify Routing Games for Social Information Sharing

Crowdsourcing services, such as Waze and Google Maps, leverage a mass of mobile users to learn massive point-of-interest (PoI) information while traveling and share it as a public good. Given that crowdsourced users mind their travel costs and possess various preferences over the PoI information along different paths, we formulate the problem as a novel non-atomic multi-path routing game with positive network externalities among users in social information sharing, which distinguishes itself from the routing game literature. In the absence of any incentive design, our price of anarchy (PoA) analysis shows that users' selfish routing on the path with the lowest cost will limit information diversity and lead to an arbitrarily large efficiency loss from the social optimum. This motivates us to design effective incentive mechanisms to remedy while upholding desirable properties such as individual rationality, incentive compatibility, and budget balance for practical feasibility. Moreover, our mechanisms are designed with incomplete information, as they do not rely on individual user's path preferences, thereby ensuring user privacy. To start with, we present a non-monetary mechanism called Adaptive Information Restriction (AIR) that imposes fractions on users' access to the public good as an indirect penalty. By adapting penalty fractions to the actual user flows along different paths, our AIR achieves the first PoA of $\frac{1}{4}$ for the problem. Then, we delve into a monetary mechanism called Adaptive Side-Payment (ASP) that charges or rewards side payments over users choosing certain paths. With those side payments well-tailored, ASP significantly improves the PoA to $\frac{1}{2}$.