Railway capacity auctions with dual prices

Please always quote using this URN: urn:nbn:de:0297-zib-11729
  • Railway scheduling is based on the principle of the construction of a conflict-free timetable. This leads to a strict definition of capacity: in contrast with road transportation, it can be said in advance whether a given railway infrastructure can accommodate - at least in theory - a certain set of train requests. Consequently, auctions for railway capacity are modeled as auctions of discrete goods -- the train slots. We present estimates for the efficiency gain that may be generated by slot auctioning in comparison with list price allocation. We introduce a new class of allocation and auction problems, the feasible assignment problem, that is a proper generalization of the well-known combinatorial auction problem. The feasible assignment class was designed to cover the needs for an auction mechanism for railway slot auctions, but is of interest in its own right. As a practical instance to state and solve the railway slot allocation problem, we present an integer programming formulation, briefly the ACP, which turns out to be an instance of the feasible assignment problem and whose dual problem yields prices that can be applied to define a useful activity rule for the linearized version of the Ausubel Milgrom Proxy auction. We perform a simulation aiming to measure the impact on efficiency and convergence rate.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Thomas Schlechte, Andreas Tanner
Document Type:ZIB-Report
Tag:Ausubel Milgrom Proxy Auction Mechanism; Combinatorial Auction Problem; Railway Track Allocation
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES / 91Bxx Mathematical economics (For econometrics, see 62P20) / 91B26 Market models (auctions, bargaining, bidding, selling, etc.)
Date of first Publication:2010/06/14
Series (Serial Number):ZIB-Report (10-10)