A real-world path auction (sort of)

Path auctions have received quite a lot of attention in the Algorithmic Game Theory community. The general scenario envisages a single buyer who wants to procure a path through a network, and has to buy a set of links that contains an acceptable path. The links are available for sale from multiple agents; a common special case of interest has each link belonging to a single agent. It’s a line of work that has led to some interesting results and techniques; for example I like the “cheap labor can be expensive” paradox of this paper by Chen and Karlin, which says that sometimes, if additional (and cheap) links/sellers are added to the network, it may actually drive up the cost for the buyer.

Now the standard “practical” motivation for path auctions that is given in the AGT literature, usually refers to a requirement to route network traffic (either data over a computer network, or alternatively, road traffic). However I have not seen any concrete examples of such path auctions actually taking place. But here’s an auction that actually takes place, in a context that is very similar conceptually to a path auction. Adapting Auctions for the Provision of Ecosystem Services at the Landscape Scale considers payments for Ecosystems Services (ES) in which landowners in Australia are paid to promote conservation goals on their land. Quoting the paper:

Most ES auctions adopt a sealed bid, discriminatory price mechanism, in which successful landholders are paid their bid price (e.g. Stoneham et al., 2003; Windle et al., 2009). A rational landholder will request at least the opportunity cost of providing the ES; they can ask for more, but the higher their price the less likely they are to have their bid accepted.

Now, the environmental gain for ES is greater if parcels of land are adjacent, since the protected land then provides wildlife corridors, and the like. The greater value of certain combinations of land parcels has influenced the mechanism used to set the prices. The mechanism in use seems to use a number of iterations, in which bids are received, a set of winners is announced, and based on that (provisional) outcome, sellers get the opportunity to change their bids. Another quote:

A critical problem in corridor formation is individuals not participating, or holding out for excessively high prices. In this form of iterated auction there will be greater opportunity for participants to identify and work around such hold-outs. Where there are different ways of forming a corridor across a landscape, corridors can evolve over multiple rounds according to the bidding behaviour of individual landholders.

The paper reports on lab-based experiments aimed at optimizing parameters of the kind of mechanism in use, in particular the number of rounds of an iterated auction. Another paper I found that may be of interest is An Experimental Study of Iterative Auctions for Ecosystem Services Delivery, which experiments with an iterative descending-price mechanism.