Merkato Auction Mechanism: The Progressive Second Price Auction

The patent-pending Progressive Second Price (PSP) auction mechanism creates the rules by which the Merkato marketplace operates. PSP features include:

·        The ability to divide resources among many bidders¾not just establish one winner

·        The ability to react quickly to changes in buyer’s valuation of the resource for sale

·        The ability to support any number of bidders who may enter or leave the bidding at will

·        Establishment of market mechanisms that create a fair market price for bandwidth, benefiting both buyers and sellers

·        Creation of market rules that encourage bidders to be maximally truthful about their desires and willingness to pay, allowing auctions to converge quickly

The InvisibleHand Merkato implementation of PSP provides the following additional features:

·        Lightweight protocol between bidders and resource agent that does not contribute significantly to bandwidth utilization

·        Support for multiple buyers and one seller, as well as multiple sellers and one buyer

·        Support for broker agents that can buy bandwidth from one source and resell it to many buyers

·        Ability of customers to create automated bidding decisions based on mix-and-match combinations of valuation, budget, and strategy

·        Inclusion of sellers as bidders, allowing them to take bandwidth off the market if they do not feel the price is sufficiently high

To understand the Progressive Second Price auction mechanism, it helps to consider the rules and motivations behind a non-progressive simple second price auction.

In a simple auction, where the highest bidder pays the price bid, bidders raise their bids incrementally in successive bidding rounds. Each bidder’s goal is to obtain the item at the lowest price, which is the price just above what the second-place bidder is willing to pay.

In an auction where many buyers are bidding for a single item, a second price mechanism is a way to quickly decide the highest bidder without the normal incremental bidding process.

The second price rule does away with the incremental bidding¾but achieves the same result¾by asking each bidder for a single highest bid. The highest bidder wins the item, but pays the amount offered by the second highest bidder. The highest bidder is guaranteed not to overpay for the item by revealing the maximum he or she is willing to pay. The seller gets essentially the same price for the item had the bidding price been raised incrementally until the second place buyer dropped out.

Applying this principle to a divisible resource such as bandwidth explains where the progressive part of progressive second price auction. In a progressive second price auction, each bid consists of a unit price and the quantity desired at that price. The bidders are ranked by unit price and then are tentatively awarded the amount they requested until the supply is exhausted. Unsuccessful bidders may re-bid in order to replace successful bidders in the ranking (hence the term “progressive”). The price every successful bidder pays is the price offered by the lowest successful bidder. (In a strict interpretation of second price rules, it would be the highest unsuccessful bidder(s) who sets the price. However, the “progressive” nature of the bidding tends to turn all bidders into winners, which would leave no basis from which to set the price.)

Eventually, all bidders will have been awarded a share of the bandwidth or dropped out of the bidding because the “market price” is higher than they wish to pay for any amount of bandwidth.

Example:

Assume that the seller has 10 Mbps to sell and 6 bidders are interested. Bids indicate the amount of bandwidth desired, as well as the unit price they are willing to pay. Let’s assume that the initial bids are these:

Bidder A: 3 Mbps desired at $100 unit price ($300 total)

Bidder B: 5 Mbps desired at $80 unit price ($400 total)

Bidder C: 3 Mbps desired at $50 unit price ($150 total)

Bidder D: 4 Mbps desired at $30 unit price ($120 total)

Bidder E: 6 Mbps desired at $20 unit price ($120 total)

Bidder F: 3 Mbps desired at $10 unit price ($30 total)

Bidders would be ranked according to their offers as shown in the following chart:

Figure 1. Stacked Bids Received for Portions of 10 Mbps of Bandwidth Offered by Seller

The shaded area represents the amount of money the seller is being offered (unit price times quantity). The green shaded area at the left represents the amount offered by successful bidders.

It might be instructive to determine what the seller would receive had he had simply taken the highest initial offers. As you can see, with 10 Mbps for sale, the highest two bidders (“A” and “B”) would receive what they want, and the third highest (“C”) would receive two of the three Mbps he desired. If the seller simply accepted the offers, they would receive $300 + $400 + $100 = $800 for the bandwidth offered from the successful bidders. This represents $80 per Mbps average price for the 10 Mbps offered.

Now lets look at how the bandwidth would be sold in a Merkato Progressive Second Price auction. To recap, the rules of the second price auction are as follows:

The bid and re-bid cycle repeats until all bidders are satisfied with the amount of bandwidth received, and their price, or have dropped out of the bidding.

Let’s assume that the initial offers from all bidders are as before. All bidders are informed that the current market price is $50 and the successful and unsuccessful bidders are informed of their status and allocation (if any). If the second price auction stopped here, the seller would receive $50 for each unit of bandwidth, or a total of $500 for the 10 Mbps of bandwidth, which is $300 less than he would have received by simply accepting the initial offers. Fortunately for the seller, the process does not end here!

The unsuccessful bidders will bid again, if they can afford to. Bidders “stay in the game” by increasing the unit price offered for bandwidth, above that of the lowest successful bidder.

How can bidders afford to do this if they revealed what they are willing to pay in their first bid? Well, assume that the bidder’s initial offer was determined by a total cost limit as opposed to a desired unit price. In this case, the bidder would desire to re-bid as long as a consistent total cost was maintained¾by lowering the requested amount of bandwidth proportionally to any increase in offered unit price. (In Merkato, this price-verses-quantity information is carried by the valuation settings.) Let’s assume, for simplicity, that all the bidders follow this same strategy and that their initial bids represent their total budget for bandwidth.

Bidder “D” was the highest unsuccessful bidder, offering a unit price of $30 for 4 units of bandwidth. This represents a budget of $120. Bidder “D” sees he can become a successful bidder this round by bidding above a unit price of $50. His next offer could be 60-unit price for 2 Mbps of bandwidth and stay within his budget limits. Each bidder can do this in turn if they find themselves pushed out of the successful bidder’s column. Although all the examples so far have involved increments of 1 Mbps of bandwidth, bidders are under no such restriction. Even bidder “F,” with a $30 budget, may become a successful bidder by asking for a fractional amount of bandwidth.

In a simulation shows that when the bidding ends, the final bids would look like this:

Bidder A: 2.7 Mbps desired at $112 unit price ($300 total)

Bidder B: 3.6 Mbps desired at $112 unit price ($400 total)

Bidder C: 1.3 Mbps desired at $112 unit price ($150 total)

Bidder D: 1.1 Mbps desired at $112 unit price ($120 total)

Bidder E: 1.1 Mbps desired at $112 unit price ($120 total)

Bidder F: 0.2 Mbps desired at $112 unit price ($30 total)

The chart below shows the bids graphically, as before:

Figure 2 Auction Results Under Progressive Second Price Mechanism

The market price of $112.00 represents the amount all bidders would have to offer in order that all are awarded bandwidth, but stay within their initial budget. The seller would receive $1120.00 for the 10 items.

All bidders are “winners” and receive an amount of bandwidth proportional to their willingness to pay and consistent with the bidding policies they established for their Merkato agents.

 

 

Return to Index