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.
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) |
ISSN: | 1438-0064 |
ZIB-Reportnumber: | 10-10 |