A differentially private and truthful incentive mechanism for traffic offload to public transportation. (English) Zbl 1521.91135
Bushnell, Linda (ed.) et al., Decision and game theory for security. 9th international conference, GameSec 2018, Seattle, WA, USA, October 29–31, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11199, 366-385 (2018).
Summary: Encouraging passengers to take public transportation reduces cost and enhances sustainability of urban ecosystems. However, the passengers incur some inconvenience cost due to potential delays and discomfort when switching from private to public transit service. In this paper, we propose a reverse auction-based mechanism so that the government can incentivize the passengers to take public transit system instead of private transit services. The proposed mechanism achieves individual rationality, truthfulness and near optimal social welfare. However, revealing passengers’ truthful inconvenience cost raises privacy concerns. Hence, a truthful and privacy preserving auction mechanism is investigated in this paper. The mechanism design is formulated as a mixed integer program, which makes the VCG-like payment scheme computationally intractable. To mitigate the computation complexity, a heuristic algorithm is proposed as an approximation. We show that truthfulness, near optimal social welfare, individual rationality and differential privacy are preserved by the heuristic algorithm. The proposed approach is demonstrated using numerical case study.
For the entire collection see [Zbl 1398.68017].
For the entire collection see [Zbl 1398.68017].
MSC:
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
| 91B03 | Mechanism design theory |
| 91B18 | Public goods |
| 68P27 | Privacy of data |
References:
| [1] | Agarwal, Y., Balaji, B., Gupta, R., Lyles, J., Wei, M., Weng, T.: Occupancy-driven energy management for smart building automation. In: Proceedings of the Workshop on Embedded Sensing Systems for Energy-Efficiency in Building, pp. 1-6. ACM (2010) |
| [2] | Agrawal, R., Srikant, R.: Privacy-preserving data mining. In: SIGMOD Record, vol. 29, pp. 439-450. ACM (2000) |
| [3] | Archer, A., Tardos, É.: Truthful mechanisms for one-parameter agents. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 482-491. IEEE (2001) |
| [4] | Ben-Akiva, M.; Cyna, M.; De Palma, A., Dynamic model of peak period congestion, Transp. Res. Part B: Methodol., 18, 4, 339-355, 1984 · doi:10.1016/0191-2615(84)90016-X |
| [5] | Brown, M.: Report: Seattle one of the worst U.S. cities for traffic congestion, tied with NYC. http://www.geekwire.com/2015/report-finds-seattle-is-one-of-the-worst-u-s-cities-for-traffic-congestion-tied-with-new-york/ |
| [6] | Como, G.; Savla, K.; Acemoglu, D.; Dahleh, MA; Frazzoli, E., Robust distributed routing in dynamical networks-part II: strong resilience, equilibrium selection and cascaded failures, Trans. Autom. Control, 58, 2, 333-348, 2013 · Zbl 1369.93281 · doi:10.1109/TAC.2012.2209975 |
| [7] | Como, G.; Savla, K.; Acemoglu, D.; Dahleh, MA; Frazzoli, E., Robust distributed routing in dynamical networks-part I: locally responsive policies and weak resilience, Trans. Autom. Control, 58, 2, 317-332, 2013 · Zbl 1369.93280 · doi:10.1109/TAC.2012.2209951 |
| [8] | Dwork, C.; Agrawal, M.; Du, D.; Duan, Z.; Li, A., Differential privacy: a survey of results, Theory and Applications of Models of Computation, 1-19, 2008, Heidelberg: Springer, Heidelberg · Zbl 1139.68339 · doi:10.1007/978-3-540-79228-4_1 |
| [9] | Dwork, C.; McSherry, F.; Nissim, K.; Smith, A.; Halevi, S.; Rabin, T., Calibrating noise to sensitivity in private data analysis, Theory of Cryptography, 265-284, 2006, Heidelberg: Springer, Heidelberg · Zbl 1112.94027 · doi:10.1007/11681878_14 |
| [10] | Fiez, T., Ratliff, L.J., Dowling, C., Zhang, B.: Data-driven spatio-temporal modeling of parking demand (2018) |
| [11] | Geng, Y.; Cassandras, CG, New “smart parking” system based on resource allocation and reservations, Trans. Intell. Transp. Syst., 14, 3, 1129-1139, 2013 · doi:10.1109/TITS.2013.2252428 |
| [12] | Gupta, A., Ligett, K., McSherry, F., Roth, A., Talwar, K.: Differentially private combinatorial optimization. In: Proceedings of the Symposium on Discrete Algorithms, pp. 1106-1125. SIAM (2010) · Zbl 1288.94087 |
| [13] | Han, S.; Pappas, GJ, Privacy in control and dynamical systems, Annu. Rev. Control Robot. Autonom. Syst., 1, 309-332, 2018 · doi:10.1146/annurev-control-060117-105018 |
| [14] | Hoh, B.; Gruteser, M.; Xiong, H.; Alrabady, A., Enhancing security and privacy in traffic-monitoring systems, Pervasive Comput., 5, 4, 38-46, 2006 · doi:10.1109/MPRV.2006.69 |
| [15] | Huang, Z., Kannan, S.: The exponential mechanism for social welfare: private, truthful, and nearly optimal. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 140-149. IEEE (2012) |
| [16] | ISO New England Inc.: Five minute system demand. https://www.iso-ne.com/isoexpress/web/reports/load-and-demand |
| [17] | Kleiner, A., Nebel, B., Ziparo, V.: A mechanism for dynamic ride sharing based on parallel auctions (2011) |
| [18] | Krishna, V., Auction Theory, 2009, Cambridge: Academic Press, Cambridge |
| [19] | Lam, K., Krichene, W., Bayen, A.: On learning how players learn: estimation of learning dynamics in the routing game. In: Proceedings of the International Conference on Cyber-Physical Systems, pp. 1-10. IEEE (2016) |
| [20] | Ma, S., Zheng, Y., Wolfson, O.: T-share: a large-scale dynamic taxi ridesharing service. In: International Conference on Data Engineering, pp. 410-421. IEEE (2013) |
| [21] | Machanavajjhala, A., Gehrke, J., Kifer, D., Venkitasubramaniam, M.: L-diversity: privacy beyond k-anonymity. In: Proceedings of the International Conference on Data Engineering, p. 24. IEEE (2006) |
| [22] | McDaniel, P.; McLaughlin, S., Security and privacy challenges in the smart grid, Secur. Priv., 7, 3, 75-77, 2009 · doi:10.1109/MSP.2009.76 |
| [23] | McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: Symposium on Foundations of Computer Science, pp. 94-103. IEEE (2007) |
| [24] | Miao, F., Han, S., Hendawi, A.M., Khalefa, M.E., Stankovic, J.A., Pappas, G.J.: Data-driven distributionally robust vehicle balancing using dynamic region partitions. In: Proceedings of the International Conference on Cyber-Physical Systems, pp. 261-271. ACM (2017) |
| [25] | Miao, F., Taxi dispatch with real-time sensing data in metropolitan areas: a receding horizon control approach, Trans. Autom. Sci. Eng., 13, 2, 463-478, 2016 · doi:10.1109/TASE.2016.2529580 |
| [26] | Moulin, P.; O’Sullivan, JA, Information-theoretic analysis of information hiding, Trans. Inf. Theory, 49, 3, 563-593, 2003 · Zbl 1063.94018 · doi:10.1109/TIT.2002.808134 |
| [27] | Naphade, M.; Banavar, G.; Harrison, C.; Paraszczak, J.; Morris, R., Smarter cities and their innovation challenges, Computer, 44, 6, 32-39, 2011 · doi:10.1109/MC.2011.187 |
| [28] | Nisan, N.; Roughgarden, T.; Tardos, E.; Vazirani, VV, Algorithmic Game Theory, 2007, Cambridge: Cambridge University Press, Cambridge · Zbl 1130.91005 · doi:10.1017/CBO9780511800481 |
| [29] | Pavone, M.; Smith, SL; Frazzoli, E.; Rus, D., Robotic load balancing for mobility-on-demand systems, Int. J. Robot. Res., 31, 7, 839-854, 2012 · doi:10.1177/0278364912444766 |
| [30] | Schuijbroek, J.; Hampshire, RC; Van Hoeve, WJ, Inventory rebalancing and vehicle routing in bike sharing systems, Eur. J. Oper. Res., 257, 3, 992-1004, 2017 · Zbl 1394.90046 · doi:10.1016/j.ejor.2016.08.029 |
| [31] | Sweeney, L., k-anonymity: a model for protecting privacy, Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 10, 5, 557-570, 2002 · Zbl 1085.68589 · doi:10.1142/S0218488502001648 |
| [32] | Tumova, J., Karaman, S., Belta, C., Rus, D.: Least-violating planning in road networks from temporal logic specifications. In: Proceedings of the International Conference on Cyber-Physical Systems, p. 17. IEEE Press (2016) |
| [33] | Vickrey, W., Counterspeculation, auctions, and competitive sealed tenders, J. Financ., 16, 1, 8-37, 1961 · doi:10.1111/j.1540-6261.1961.tb02789.x |
| [34] | Zhang, R., Rossi, F., Pavone, M.: Model predictive control of autonomous mobility-on-demand systems. In: Proceedings of the International Conference on Robotics and Automation, pp. 1382-1389. IEEE (2016) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
