Online incentive-compatible mechanisms for traffic intersection auctions

David Rey, Michael W. Levin, Vinayak V. Dixit

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


We present novel online mechanisms for traffic intersection auctions in which users bid for priority service. We assume that users at the front of their lane are requested to declare their delay cost, i.e. value of time, and that users are serviced in decreasing order of declared delay cost. Since users are expected to arrive dynamically at traffic intersections, static pricing approaches may fail to estimate user expected waiting time accurately, and lead to non-strategyproof payments. To address this gap, we propose two Markov chain models to determine the expected waiting time of participants in the auction. Both models take into account the probability of future arrivals at the intersection. In a first model, we assume that the probability of future arrivals is uniform across lanes of the intersection. This queue-based model only tracks the number of lower- and higher-bidding users on access lanes, and the number of empty lanes. The uniformness assumption is relaxed in a second, lane-based model which accounts for lane-specific user arrival probabilities at the expense of an extended state space. We then design a mechanism to determine incentive-compatible payments in the dynamic sense. The resulting online mechanisms maximize social welfare in the long run. Numerical experiments on a four-lane traffic intersection are reported and compared to a static incentive-compatible mechanism. Our findings show that static incentive-compatible mechanisms may lead users to misreport their delay costs. In turn, the proposed online mechanisms are shown to be incentive-compatible in the dynamic sense.

Original languageEnglish (US)
Pages (from-to)229-247
Number of pages19
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - Aug 16 2021

Bibliographical note

Funding Information:
This research was funded by the Australian Government through the Australian Research Council’s Discovery Projects funding scheme (project DP190102873). This research was also partially supported by funding from the UNSW Digital Grid Futures Institute, UNSW, Sydney, under a cross disciplinary fund scheme.

Publisher Copyright:
© 2020 Elsevier B.V.


  • Auctions/bidding
  • Incentive-compatibility
  • Markov chain
  • Online mechanism design
  • Traffic intersection


Dive into the research topics of 'Online incentive-compatible mechanisms for traffic intersection auctions'. Together they form a unique fingerprint.

Cite this