An On-line Truthful and Individually Rational Pricing Mechanism for Ride-sharing

ABSTRACT

Ride-sharing has the potential of addressing many socioeconomic challenges related to transportation. The rising popularity of ride-sharing platforms (e.g., Uber, Lyft, DiDi) in addition to the emergence of new applications like food delivery and grocery shopping which use a similar platform, calls for an in-depth and detailed evaluation of various aspects of this problem.

Auction frameworks and mechanism design, have been widely used for modeling ride-sharing platforms. A key challenge in these approaches is preventing the involving parties from manipulating the platform for their personal gain which in turn, can result in a less satisfactory experience for other parties and/or loss of profit for the platform provider. We introduce a latent space transition model for ride-sharing platforms which drivers can exploit and predict the future supply of the drivers (i.e., available drivers) to their own advantage. Following, we propose a pricing model for ride-sharing platforms which is both truthful and individually rational based on Vickery auctions and show how we can manage the loss of revenue in this approach. We compare our predicting model and pricing model with competing approaches through experiments on New York City's taxi dataset. Our results show that our model can accurately learn the transition patterns of people's ride requests. Furthermore, our pricing mechanism forces drivers to be truthful and takes away any unfair advantage the drivers can achieve by bidding untruthfully. More importantly, our pricing model forces truthfulness without sacrificing much profit unlike what is typical with second-price auction schemes.

References

1. It's a beautiful (pool) day in the neighborhood, https://www.uber.com/blog/los-angeles/its-a-beautiful-pool-day-in-the-neighborhood/. Accessed: 2017-03-30.
2. Nyc taxi trips. http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml. Accessed: 2017-03-30.
3. Asghari, M., Deng, D., Shahabi, C., Demiryurek, U., and Li, Y. Price-aware real-time ride-sharing at scale: An auction-based approach. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (New York, NY, USA, 2016), GIS '16, ACM, pp. 3:1--3:10.
4. Blei, D. M., Ng, A. Y., and Jordan, M. I. Latent dirichlet allocation. J. Mach. Learn. Res. 3 (Mar. 2003), 993--1022.
5. Cheng, S.-F., Nguyen, D. T., and Lau, H. C. Mechanisms for arranging ride sharing and fare splitting for last-mile travel demands. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems (Richland, SC, 2014), AAMAS '14, International Foundation for Autonomous Agents and Multiagent Systems, pp. 1505--1506.
6. Chiang, M.-F., Hoang, T.-A., and Lim, E.-P. Where are the passengers?: A grid-based gaussian mixture model for taxi bookings. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems (New York, NY, USA, 2015), SIGSPATIAL '15, ACM, pp. 32:1--32:10.
7. Cho, R., Myers, S. A., and Leskovec, J. Friendship and mobility: User movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2011), KDD '11, pp. 1082--1090.
8. Cici, B., Markopoulou, A., and Laoutaris, N. Designing an on-line ride-sharing system. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems (2015), GIS '15, pp. 60:1--60:4.
9. Huang, Y., Bastani, F., Jin, R., and Wang, X.S. Large scale real-time ridesharing with service guarantee on road networks. Proceedings of the VLDB Endowment 7, 14 (2014), 2017--2028.
10. Kamar, R., and Horvitz, R. Collaboration and shared plans in the open world: Studies of ridesharing. In Proceedings of the 21st International Jont Conference on Artifical Intelligence (San Francisco, CA, USA, 2009), IJCAT09, Morgan Kaufmann Publishers Inc., pp. 187--194.
11. Kleiner, A., Nebel, B., and Ziparo, V. A. A mechanism for dynamic ride sharing based on parallel auctions. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume One (2011), IJCAI'11, AAAI Press, pp. 266--272.
12. Kullback, S., and Leibler, R. A. On information and sufficiency. Ann. Math. Statist. 22, 1 (03 1951), 79--86.
13. Lagoudakis, M., Berhault, M., Koenig, S., Keskinocak, P., and Kleywegt, A. Simple auctions with performance guarantees for multi-robot task allocation. In Intelligent Robots and Systems, 2004. (IROS 2004). Proceedings. 2004 IEEE/RSJ International Conference on (Sept 2004), vol. 1, pp. 698--705 vol.1.
14. Lichman, M., and Smyth, P. Modeling human location data with mixtures of kernel densities. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2014), KDD '14, pp. 35--44.
15. Ma, S., Zheng, Y., and Wolfson, O. Real-time city-scale taxi ridesharing. IEEE Transactions on Knowledge and Data Engineering 27, 7 (2015), 1782--1795.
16. Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. Adwords and generalized on-line matching. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on (Oct 2005), pp. 264--273.
17. Noulas, A., Scellato, S., Lathia, N., and Mascolo, C. Mining user mobility features for next place prediction in location-based services. In Proceedings of the 2012 IEEE 12th International Conference on Data Mining (2012), ICDM '12, pp. 1038--1043.
18. Rubner, Y., Tomasi, C., and Guibas, L.J. A metric for distributions with applications to image databases. In Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271) (Jan 1998), pp. 59--66.
19. Shen, W., Lopes, C. V., and Crandall, J. W. An online mechanism for ridesharing in autonomous mobility-on-demand systems. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (2016), IJCAI'16, AAAI Press, pp. 475--481.
20. Wang, W., Yin, PL, Sadiq, S., Chen, L., Xie, M., and Zhou, X. Spore: A sequential personalized spatial item recommender system. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE) (May 2016), pp. 954--965.
21. Yin, PL, Sun, Y., Cui, B., Hu, Z., and Chen, L. Lcars: A location-content-aware recommender system. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2013), KDD '13, pp. 221--229.
22. Yuan, Q., Cong, G., Ma, Z., Sun, A., and Thalmann, N. M. Time-aware point-of-interest recommendation. In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval (2013), SIGIR '13, pp. 363--372.
23. Zhang, J.-D., Chow, C.-Y., and Li, Y. Lore: Exploiting sequential influence for location recommendations. In Proceedings of the 22Nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (2014), SIGSPATIAL '14, pp. 103--112.
24. Zhao, D., Ramchurn, S. D., and Jennings, N. R. Incentive design for ridesharing with uncertainty. In arXiv preprint arXiv: 1505.01617 (2015).

Index Terms

• Information systems

  • World Wide Web

    • Online advertising

    • Web applications

      • Electronic commerce