IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v60y2013icp94-112.html
   My bibliography  Save this article

A hybrid implementation mechanism of tradable network permits system which obviates path enumeration: An auction mechanism with day-to-day capacity control

Author

Listed:
  • Wada, Kentaro
  • Akamatsu, Takashi

Abstract

Akamatsu (2007a,b) proposed a new dynamic traffic congestion control scheme called tradable network permits, and demonstrated its efficiency properties for general road networks. To implement tradable permit markets, this paper proposes a novel auction mechanism with capacity control. This mechanism employs an evolutionary approach to achieve a dynamic system optimal allocation of network permits in a computationally efficient manner. We prove that the proposed mechanism has the following desirable properties: (i) truthful bidding is a dominant strategy for each user on each day and (ii) the permit allocation pattern under the mechanism converges to a dynamic system optimal allocation pattern.

Suggested Citation

  • Wada, Kentaro & Akamatsu, Takashi, 2013. "A hybrid implementation mechanism of tradable network permits system which obviates path enumeration: An auction mechanism with day-to-day capacity control," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 94-112.
    • Handle: RePEc:eee:transe:v:60:y:2013:i:c:p:94-112
    DOI: 10.1016/j.tre.2013.05.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S136655451300121X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2013.05.008?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Montgomery, W. David, 1972. "Markets in licenses and efficient pollution control programs," Journal of Economic Theory, Elsevier, vol. 5(3), pages 395-418, December.
    2. Iryo, Takamasa, 2011. "Multiple equilibria in a dynamic traffic network," Transportation Research Part B: Methodological, Elsevier, vol. 45(6), pages 867-879, July.
    3. Nisan, Noam & Ronen, Amir, 2001. "Algorithmic Mechanism Design," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 166-196, April.
    4. William H. Sandholm, 2002. "Evolutionary Implementation and Congestion Pricing," Review of Economic Studies, Oxford University Press, vol. 69(3), pages 667-689.
    5. Thomas H. Tietenberg, 1980. "Transferable Discharge Permits and the Control of Stationary Source Air Pollution: A Survey and Synthesis," Land Economics, University of Wisconsin Press, vol. 56(4), pages 391-416.
    6. Athanasios K. Ziliaskopoulos, 2000. "A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem," Transportation Science, INFORMS, vol. 34(1), pages 37-49, February.
    7. Yang, Hai & Meng, Qiang & Lee, Der-Horng, 2004. "Trial-and-error implementation of marginal-cost pricing on networks in the absence of demand functions," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 477-493, July.
    8. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    9. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    10. Arnott, Richard & de Palma, Andre & Lindsey, Robin, 1993. "A Structural Model of Peak-Period Congestion: A Traffic Bottleneck with Elastic Demand," American Economic Review, American Economic Association, vol. 83(1), pages 161-179, March.
    11. Kuwahara, Masao, 2007. "A theory and implications on dynamic marginal cost," Transportation Research Part A: Policy and Practice, Elsevier, vol. 41(7), pages 627-643, August.
    12. Dušan Teodorović & Konstantinos Triantis & Praveen Edara & Yueqin Zhao & Snežana Mladenović, 2008. "Auction-Based Congestion Pricing," Transportation Planning and Technology, Taylor & Francis Journals, vol. 31(4), pages 399-416, March.
    13. Viegas, José M., 2001. "Making urban road pricing acceptable and effective: searching for quality and equity in urban mobility," Transport Policy, Elsevier, vol. 8(4), pages 289-294, October.
    14. T. L. Magnanti & R. T. Wong, 1981. "Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria," Operations Research, INFORMS, vol. 29(3), pages 464-484, June.
    15. Demange, Gabrielle & Gale, David & Sotomayor, Marilda, 1986. "Multi-Item Auctions," Journal of Political Economy, University of Chicago Press, vol. 94(4), pages 863-872, August.
    16. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    17. Vickrey, William S, 1969. "Congestion Theory and Transport Investment," American Economic Review, American Economic Association, vol. 59(2), pages 251-260, May.
    18. Yang, Hai & Meng, Qiang, 1998. "Departure time, route choice and congestion toll in a queuing network with elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 32(4), pages 247-260, May.
    19. Michael J. Smith, 1984. "The Stability of a Dynamic Model of Traffic Assignment---An Application of a Method of Lyapunov," Transportation Science, INFORMS, vol. 18(3), pages 245-252, August.
    20. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2000. "A Benders Decomposition Approach for the Locomotive and Car Assignment Problem," Transportation Science, INFORMS, vol. 34(2), pages 133-149, May.
    21. Smith, M. J., 1993. "A new dynamic traffic model and the existence and calculation of dynamic user equilibria on congested capacity-constrained road networks," Transportation Research Part B: Methodological, Elsevier, vol. 27(1), pages 49-63, February.
    22. Bikhchandani, Sushil & Mamer, John W., 1997. "Competitive Equilibrium in an Exchange Economy with Indivisibilities," Journal of Economic Theory, Elsevier, vol. 74(2), pages 385-413, June.
    23. Arnott, Richard & de Palma, Andre & Lindsey, Robin, 1990. "Economics of a bottleneck," Journal of Urban Economics, Elsevier, vol. 27(1), pages 111-130, January.
    24. Carlos F. Daganzo, 1985. "The Uniqueness of a Time-dependent Equilibrium Distribution of Arrivals at a Single Bottleneck," Transportation Science, INFORMS, vol. 19(1), pages 29-37, February.
    25. Han, Deren & Yang, Hai, 2009. "Congestion pricing in the absence of demand functions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(1), pages 159-171, January.
    26. Peter Cramton & Yoav Shoham & Richard Steinberg (ed.), 2006. "Combinatorial Auctions," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262033429, December.
    27. S.J. Rassenti & V.L. Smith & R.L. Bulfin, 1982. "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," Bell Journal of Economics, The RAND Corporation, vol. 13(2), pages 402-417, Autumn.
    28. Takashi Akamatsu, 2001. "An Efficient Algorithm for Dynamic Traffic Equilibrium Assignment with Queues," Transportation Science, INFORMS, vol. 35(4), pages 389-404, November.
    29. Leonard, Herman B, 1983. "Elicitation of Honest Preferences for the Assignment of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 91(3), pages 461-479, June.
    30. Dale McDaniel & Mike Devine, 1977. "A Modified Benders' Partitioning Algorithm for Mixed Integer Programming," Management Science, INFORMS, vol. 24(3), pages 312-319, November.
    31. Jean Jacques Laffont, 1977. "More on Prices vs. Quantities," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 44(1), pages 177-182.
    32. Martin L. Weitzman, 1974. "Prices vs. Quantities," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 41(4), pages 477-491.
    33. Michael J. Smith, 1984. "The Existence of a Time-Dependent Equilibrium Distribution of Arrivals at a Single Bottleneck," Transportation Science, INFORMS, vol. 18(4), pages 385-394, November.
    34. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    35. Sandholm, William H., 2007. "Pigouvian pricing and stochastic evolutionary implementation," Journal of Economic Theory, Elsevier, vol. 132(1), pages 367-382, January.
    36. E Verhoef & P Nijkamp & P Rietveld, 1997. "Tradeable Permits: Their Potential in the Regulation of Road Transport Externalities," Environment and Planning B, , vol. 24(4), pages 527-548, August.
    37. Gordon F. Newell, 1987. "The Morning Commute for Nonidentical Travelers," Transportation Science, INFORMS, vol. 21(2), pages 74-88, May.
    38. Milgrom,Paul, 2004. "Putting Auction Theory to Work," Cambridge Books, Cambridge University Press, number 9780521536721.
    39. Nie, Yu (Marco), 2011. "A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 329-342, February.
    40. Han, Sangjin, 2003. "Dynamic traffic modelling and dynamic stochastic user equilibrium assignment for general road networks," Transportation Research Part B: Methodological, Elsevier, vol. 37(3), pages 225-249, March.
    41. Doan, Kien & Ukkusuri, Satish & Han, Lanshan, 2011. "On the existence of pricing strategies in the discrete time heterogeneous single bottleneck model," Transportation Research Part B: Methodological, Elsevier, vol. 45(9), pages 1483-1500.
    42. Yang, Hai & Wang, Xiaolei, 2011. "Managing network mobility with tradable credits," Transportation Research Part B: Methodological, Elsevier, vol. 45(3), pages 580-594, March.
    43. Theodore Tsekeris & Stefan Voß, 2009. "Design and evaluation of road pricing: state-of-the-art and methodological advances," Netnomics, Springer, vol. 10(1), pages 5-52, April.
    44. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhang, Fang & Lu, Jian & Hu, Xiaojian, 2021. "Tradable credit scheme design with transaction cost and equity constraint," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    2. Michael W. Levin, 2019. "A Combinatorial Dynamic Network Trajectory Reservation Algorithm for Connected Autonomous Vehicles," Networks and Spatial Economics, Springer, vol. 19(1), pages 27-55, March.
    3. Takayama, Yuki & Kuwahara, Masao, 2017. "Bottleneck congestion and residential location of heterogeneous commuters," Journal of Urban Economics, Elsevier, vol. 100(C), pages 65-79.
    4. Takayama, Yuki, 2015. "Bottleneck congestion and distribution of work start times: The economics of staggered work hours revisited," Transportation Research Part B: Methodological, Elsevier, vol. 81(P3), pages 830-847.
    5. Hara, Yusuke & Hato, Eiji, 2018. "A car sharing auction with temporal-spatial OD connection conditions," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 723-739.
    6. Lamotte, Raphaël & de Palma, André & Geroliminis, Nikolas, 2017. "On the use of reservation-based autonomous vehicles for demand management," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 205-227.
    7. Yang, Kaidi & Roca-Riu, Mireia & Menéndez, Mónica, 2019. "An auction-based approach for prebooked urban logistics facilities," Omega, Elsevier, vol. 89(C), pages 193-211.
    8. Osawa, Minoru & Fu, Haoran & Akamatsu, Takashi, 2018. "First-best dynamic assignment of commuters with endogenous heterogeneities in a corridor network," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 811-831.
    9. Wang, Hua & Zhang, Xiaoning, 2016. "Joint implementation of tradable credit and road pricing in public-private partnership networks considering mixed equilibrium behaviors," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 158-170.
    10. Bao, Yue & Xiao, Feng & Gao, Zaihan & Gao, Ziyou, 2017. "Investigation of the traffic congestion during public holiday and the impact of the toll-exemption policy," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 58-81.
    11. Liu, Wei & Zhang, Fangni & Yang, Hai, 2017. "Modeling and managing morning commute with both household and individual travels," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 227-247.
    12. Provoost, Jesper & Cats, Oded & Hoogendoorn, Serge, 2023. "Design and classification of tradable mobility credit schemes," Transport Policy, Elsevier, vol. 136(C), pages 59-69.
    13. Aalami, Soheila & Kattan, Lina, 2022. "Proportionally fair flow markets for transportation networks," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 24-41.
    14. Hara, Yusuke, 2018. "Behavioral mechanism design for transportation services: Laboratory experiments and preference elicitation cost," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 231-245.
    15. Zhu, Zheng & Li, Xinwei & Liu, Wei & Yang, Hai, 2019. "Day-to-day evolution of departure time choice in stochastic capacity bottleneck models with bounded rationality and various information perceptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 168-192.
    16. Wang, Pengfei & Guan, Hongzhi & Liu, Peng, 2020. "Modeling and solving the optimal allocation-pricing of public parking resources problem in urban-scale network," Transportation Research Part B: Methodological, Elsevier, vol. 137(C), pages 74-98.
    17. Li, Xinwei & Yang, Hai & Ke, Jintao, 2023. "Booking cum rationing strategy for equitable travel demand management in road networks," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 261-274.
    18. Wang, Jing-Peng & Liu, Tian-Liang & Huang, Hai-Jun, 2018. "Tradable OD-based travel permits for bi-modal traffic management with heterogeneous users," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 589-605.
    19. Lessan, Javad & Fu, Liping & Bachmann, Chris, 2020. "Towards user-centric, market-driven mobility management of road traffic using permit-based schemes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    20. Takayama, Yuki & Kuwahara, Masao, 2016. "Scheduling preferences, parking competition, and bottleneck congestion: A model of trip timing and parking location choices by heterogeneous commuters," MPRA Paper 68938, University Library of Munich, Germany.
    21. Yusuke Hara & Eiji Hato, 2019. "Analysis of dynamic decision-making in a bicycle-sharing auction using a dynamic discrete choice model," Transportation, Springer, vol. 46(1), pages 147-173, February.
    22. Takayama, Yuki, 2020. "Who gains and who loses from congestion pricing in a monocentric city with a bottleneck?," Economics of Transportation, Elsevier, vol. 24(C).
    23. Gupta, Varun & Perera, Sandun, 2021. "Managing surges in online demand using bandwidth throttling: An optimal strategy amid the COVID-19 pandemic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 151(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Nie, Yu (Marco) & Yin, Yafeng, 2013. "Managing rush hour travel choices with tradable credit scheme," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 1-19.
    2. Yu Nie, 2015. "A New Tradable Credit Scheme for the Morning Commute Problem," Networks and Spatial Economics, Springer, vol. 15(3), pages 719-741, September.
    3. Ren-Yong Guo & Hai Yang & Hai-Jun Huang & Zhijia Tan, 2016. "Day-to-Day Flow Dynamics and Congestion Control," Transportation Science, INFORMS, vol. 50(3), pages 982-997, August.
    4. Takayama, Yuki, 2015. "Bottleneck congestion and distribution of work start times: The economics of staggered work hours revisited," Transportation Research Part B: Methodological, Elsevier, vol. 81(P3), pages 830-847.
    5. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    6. Wang, Pengfei & Guan, Hongzhi & Liu, Peng, 2020. "Modeling and solving the optimal allocation-pricing of public parking resources problem in urban-scale network," Transportation Research Part B: Methodological, Elsevier, vol. 137(C), pages 74-98.
    7. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    8. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    9. Ren-Yong Guo & Hai-Jun Huang & Hai Yang, 2019. "Tradable Credit Scheme for Control of Evolutionary Traffic Flows to System Optimum: Model and its Convergence," Networks and Spatial Economics, Springer, vol. 19(3), pages 833-868, September.
    10. Li, Zhi-Chun & Huang, Hai-Jun & Yang, Hai, 2020. "Fifty years of the bottleneck model: A bibliometric review and future research directions," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 311-342.
    11. William H. Sandholm, 2005. "Negative Externalities and Evolutionary Implementation," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 72(3), pages 885-915.
    12. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    13. Xiao, Feng & Qian, Zhen (Sean) & Zhang, H. Michael, 2013. "Managing bottleneck congestion with tradable credits," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 1-14.
    14. Guo, Ren-Yong & Yang, Hai & Huang, Hai-Jun & Li, Xinwei, 2018. "Day-to-day departure time choice under bounded rationality in the bottleneck model," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 832-849.
    15. Sun, Jian & Wu, Jiyan & Xiao, Feng & Tian, Ye & Xu, Xiangdong, 2020. "Managing bottleneck congestion with incentives," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 143-166.
    16. Tian, Li-Jun & Yang, Hai & Huang, Hai-Jun, 2013. "Tradable credit schemes for managing bottleneck congestion and modal split with heterogeneous users," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 54(C), pages 1-13.
    17. Hara, Yusuke & Hato, Eiji, 2018. "A car sharing auction with temporal-spatial OD connection conditions," Transportation Research Part B: Methodological, Elsevier, vol. 117(PB), pages 723-739.
    18. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press, vol. 33(4), pages 541-571.
    19. Kenneth Small, 2015. "The Bottleneck Model: An Assessment and Interpretation," Working Papers 141506, University of California-Irvine, Department of Economics.
    20. Lawrence M. Ausubel & Peter Cramton & Paul Milgrom, 2012. "System and Method for a Hybrid Clock and Proxy Auction," Papers of Peter Cramton 12acmhc, University of Maryland, Department of Economics - Peter Cramton, revised 2012.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:60:y:2013:i:c:p:94-112. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.