Auctions

Auctions have been long used to sell and buy various goods all around the world.

Classical auction types

There is number of different types of auctions, however, four of them are the most typical:

The second-price auction may seem a bit weird. Why would a seller want to use this type of auction, when they get less money than in the first-price one? It actually turns out that people very often bid a bit higher in the second-price auction and therefore this effect is quite reduced. The second-price auction is also interesting as the final price is the same as in the English auction. Why? Imagine that we have a number of bidders, each of these put a different value to the object that is being sold. In the English auction, the bidders remain in the auction as long as the current price is lower than their internal value of the object (dropping earlier does not make sense as in case they buy the object they will have a profit, dropping later also does not make sense as even if the bidder buys the object, they will suffer a loss). Therefore, once the price is higher than the second-highest one, only one bidder remains and wins the auction with the current price (which is just a bit higher than the second highest one). It can actually also be shown that for the second-price sealed-bid auction the dominant strategy for each bidder is to bid the bidder’s internal value.

The first-price sealed-bid auction is similar to the Dutch auction, as in both of them the highest bidder wins and pays the value of their bid. However, in both the cases, the bidder does not have to bid its internal value. The bid that actually maximizes the profit for the bidder is a bit lower and depends on the number of other bidders and how much their internal values may differ (keep in mind that these are unknown to the other bidders).

Other types of auctions

There are also other types of auctions used. Some of them are generalizations of the second-bid auctions to cases where more identical objects are available. For example, if we are selling $n$ identical objects, we can use the $n$-th price sealed-bid auction. In such a case each bidder submits their bid in an envelope and once the envelopes are opened, the $n$ objects are sold to the $n$ highest bidders. Each of these bidders pays the $n$-th highest price. Similar auctions are also used for example to sell U.S. Treasury bills.

Amazon Web Services also uses a similar type of auction when renting their spot instances (basically virtual computers). In this case, every user specifies the maximum price their are willing to pay for using a specific instance. If $n$ instances are available, all users pay the $n$-th highest price and they can use the instance. The interesting bit here is that the number of available instances can change at any time as well as the number of users interested in using them. This means that such an auction is actually continuous in the sense that any bidder can come at any time and place their bid. As a result of that the $n$-th price may increase, which in turn means that some of the instances are terminated and assigned to new users. Obviously, in case some users lower their bid, or stop using the instances, the $n$-th price may decrease, which in turn means that some users may start using an instance for this lower price.

Stock exchanges also use a continuous type of auction. In this specific type buyers specify the maximum price they are willing to pay per share and the number of shares they want to buy and sellers specify the minimum price they want per share and the number of shares they want to sell. If there is at any point a buyer that wants to buy for higher price than a seller is willing to sell, the trade is immediately made.

Moreover, stock exchanges in some phases of trading (typically at open and close and during volatility breaks) use a different type of auction. In this type, the buyers and sellers again specify their prices and amounts of shares they are willing to trade. All these offers are stored in an order book and when the trades should happen (at a specified time) the price that will lead to most shares being traded is used and the trades are executed.

Assignment

The assignment for this lesson is to prepare a strategy for trading in auctions. You actually need to prepare two strategies - one for ascending-bid auction and one for descending-bit auction. For simple auctions of single objects the strategies would be simple, therefore the situation is more complicated for the assignment. We will simulate auctioning a number of different objects (for different prices). For each of these objects, you will be given your internal value and your goal is to maximize the final value of objects you own, computed as $M + V$, where $M$ is the remaining amount of money and $V$ is the value of the objects you bought. The amount of money $M$ cannot be negative. To complicate the matter further, you are given limited budget for the trading (initial amount of money).

Use the prepared source codes for the implementation. You can find an example strategy implemented in strategies/example.py. This strategy is interested in any object as long as its price is lower that the value of the object and the strategy has enough money to buy it. In order to implement your own strategy, I recommend making a new copy of this file (with a new and unique name) and implementing your own class. There are comments for the methods in the class that explain what the method does and when it is called. Most importantly, you need to implement the interested method, that returns if the strategy is interested in the object being sold for the given price.

In the file, you also need to implement two functions - strategy_ascending and strategy_descending that return your strategy for the English and Dutch versions of the auctions respectively. Both the methods have only one parameter - the number of other strategies in the tournament. You can have one strategy for both versions of the tournament, however, I recommend having two different strategies (i.e. implement two different classes).

Deadline: May 15, 2024 at 4 p.m. (I will run the tournament after that time)

Points:

References

A nice description of auctions and strategies is available in the book Networks, Crowds, and Markets: Reasoning about a Highly Connected World - Chapter 9. The preprint of the whole book is available online (link in the chapter linked above).

Mgr. Martin Pilát, Ph.D.
Malostranské náměstí 25
118 00 Prague, Czech Republic
Martin.Pilat@mff.cuni.cz