Next: Project 4: Soldier, Soldier, Up: W4444 Programming and Problem Previous: Project 2: Make Hay
The government of Rectangularia has decided to privatize its railways. Towards this end, it has created a system by which the various pieces of the national railway infrastructure will be auctioned off. To maximize revenue, a special auction system will be utilized, detailed below.
Rectangularia is a rectangular country, 1024km wide, and 768km high when looked at on a map (or a computer screen). Towns are scattered across the country. The locations are supplied in a geography file that is available to the simulator and to auction participants. Another transit file summarizes, for each pair of different towns A and B, how many people travel between A and B in a year. We'll assume that travel is symmteric, i.e., that the volume of travel from A to B is the same as the volume from B to A.
The endpoints of all rail links are towns, and for the purposes of this project, rail links can be assumed to be straight line segments between the two endpoints. The entire collection of rail links that is up for auction is supplied in a infrastructure file that is also known in advance. Note that it is possible (but probably not common) for there to be multiple links between a pair of towns.
Each group represents one of the private rail companies that is looking to do business in Rectangularia. Your program will decide which links to bid on, and how much to bid. Before getting into the bidding system, it will help to know the value of a particular set of routes in this simulation.
At the end of the auction, each rail company will control a particular set of links. Customers have a strong expectation that they will pay exactly one Rectangulira (or lira for short) for each kilometer of distance between the two endpoints according to the shortest rail path (ignoring ownership of the constituent links) between the two towns. However, that does not necessarily mean they will travel on this shortest path.
Travelers prefer to travel with as few switches between rail companies as possible. Because schedules across companies are not coordinated etc., there is an implicit time penalty equivalent to 200km in switching between rail companies. For example, suppose that there are six towns as follows: A(0,0), B(100,0), C(200,0), D(0,50), E(200,50), F(300,0). Suppose there are six links each controlled by one of three companies X, Y, Z: X controls A-B, Y controls B-C and C-F, and Z controls A-D, D-E, and C-E. A customer traveling from A to C will pay 200 lira no matter what route is taken, because the shortest path is 200km. However, traveling A-B-C involves a change of companies at B, making the whole trip feel like a 400km trip. Instead, traveling A-D-E-C is only 300km, and so customers will choose that route, and company Z would receive the entire 200 lira as revenue.
On the other hand, a customer traveling from A to F will be choosing between A-D-E-C-F and A-B-C-F, both of which involve one change of companies. In that case, the customer will select A-B-C-F because it is shorter. Revenue from a customer is divided among the companies in proportion to the length of the links controlled by the company on the customer's path. For the A-B-C-F route, the customer pays 300 lira, of which company X receives 100 lira, and company Y receives 200 lira.
In the event that multiple paths have exactly the same distance even after the switching penalty is taken into account, then those paths share the revenue equally. Such revenue sharing might happen quite often in cases where a pair of towns is connected by more than one link.
Once the auction is complete, all rail ownership is settled, and the total revenue per year for each company can be calculated. The strategy is in bidding for links that will maximize this revenue. You plan to pay off the cost of the links over ten years, so your net profit P will be equal to ten times the annual revenue (according to the formula given above) less the total amount you spent at the auction. Players will be ranked based on P at the end of the game.
So how does the auction work? Players may submit bids on any link or any pair of connecting links. A connecting pair would be something like A-B-C, and not A-B-A in the case where there are two links between A and B. All bids are recorded by the simulator, and made public to all participants. Bidding proceeds in order from group to group, with groups either making one bid or deciding not to bid. A bid must be an advance on the previous state of the auction, which means that either (a) it is a bid on an available link or link-pair that does not currently have any bids, and the bid meets the mandated minimum (see below), or (b) it advances the highest bid amount on a previous link or link-pair by at least 10000 lira. The auction pauses when all groups decide not to submit any new bids on a round. At this point, the link or link-pair with the highest bid price per total length is awarded to the group that placed this bid. (In case multiple different items have this same price to length ratio, the simulator chooses one at random.)
At this point, the auction restarts from scratch, but with fewer links now available. Eventually, all links are awarded and the outcome can be calculated. If a player holds a link between A and B, that player is prevented from bidding on other links between A and B, or on link pairs including such a link.
The government of Rectangularia has set a mandated minimum bid for each link as follows. If the link joins towns A and B, use the transit information to calculate the ten-year revenue RAB just for travellers commuting between A and B, i.e., ignoring longer paths that might happen to use this link. If there are k such links between A and B, then the minimum bid for the link is RAB/k. The reasoning behind this minimum is that this amount guarantees that the bidder will not make a loss on the link. For link-pairs, the minimum bids for each link considered alone are added.
The government also wants to create a competitive environment without a monopoly arising simply because of economies of scale. For this reason, the government calculates in advance the entire 10-year revenue R for the whole railway system according to the transit information, and gives each group a maximum budget of 2R/g where there are g participating groups. In this way, no group should be able to acquire more than double the average coverage among all companies. Groups are not obligated to spend their entire budget, and probably won't come close most of the time: if everybody spent that much they'd be losing a lot of money.
In this game, the geography, transit and infrastructure information can be arbitrary, and during the course of the project, groups will be asked to supply combinations of such files that they find interesting. At the end of the class we'll run a collection of tournaments for a selection of such configurations. To make the tournaments feasible, we will probably impose a CPU time limit for bids, such as 1 CPU second per bid.
Some things to think about:
This game is loosely based on the game Ticket to Ride. To see how algorithmic aspects might interact with auctions, find out about the auction mechanism recently used for reallocating access to bands of the electromagnetic spectrum.
Ken Ross 2018-09-12