Double auction

Last updated

A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. [1] Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included. A common example of a double auction is stock exchange.

Contents

As well as their direct interest, double auctions are reminiscent of Walrasian auction and have been used as a tool to study the determination of prices in ordinary markets. A double auction is also possible without any exchange of currency in barter trade. A barter double auction is an auction where every participant has a demand and an offer consisting of multiple attributes and no money is involved. [2] For the mathematical modelling of satisfaction level Euclidean distance is used, where the offer and demand are treated as vectors.

A simple example of a double auction is a bilateral trade scenario, in which there is a single seller who values his product as S (e.g. the cost of producing the product), and a single buyer who values that product as B.

Economic analysis

From an economist's perspective, the interesting problem is to find a competitive equilibrium - a situation in which the supply equals the demand.

In the simple bilateral trade scenario, if BS then any price in the range [S,B] is an equilibrium price, since both the supply and the demand equal 1. Any price below S is not an equilibrium price since there is an excess demand, and any price above B is not an equilibrium price since there is an excess supply. When B<S, any price in the range (B,S) is an equilibrium price, since both the supply and the demand equal 0 (the price is too high for the buyer and too low for the seller).

In a more general double auction, in which there are many sellers each of whom holds a single unit and many buyers each of whom wants a single unit, an equilibrium price can be found using the natural ordering of the buyers and sellers:

Natural ordering

Every price in the range [max(sk,bk+1),min(bk,sk+1)] is an equilibrium price, since both demand and supply are k. It is easier to see this by considering the range of equilibrium prices in each of the 4 possible cases (note that by definition of k, bk+1 < sk+1):

sk+1 > bksk+1bk
bk+1 < sk[sk,bk][sk,sk+1]
bk+1sk[bk+1,bk][bk+1,sk+1]

Game-theoretic analysis

A double auction can be analyzed as a game. Players are buyers and sellers. Their strategies are bids for buyers and ask prices for sellers (that depend on the valuations of buyers and sellers). Payoffs depend on the price of the transaction (determined by the auctioneer) and the valuation of a player. The interesting problem is to find a Nash equilibrium - a situation in which no trader has an incentive to unilaterally change their bid/ask price.

Consider the bilateral trade scenario, in which the buyer submits a bid of b and the seller submits s.

Suppose an auctioneer sets the price in the following way:

The utility of the buyer is:

The utility of the seller is:

In a complete information case when the valuations are common knowledge to both parties, it can be shown that the continuum of pure strategy efficient Nash equilibriums exists with This means that, if B>S, there will be no equilibrium in which both players declare their true values: either the buyer will be able to gain by declaring a lower value, or the seller will be able to gain by declaring a higher value.

In an incomplete information (asymmetric information) case a buyer and a seller know only their own valuations. Suppose that these valuations are uniformly distributed over the same interval. Then it can be shown that such a game has a Bayesian Nash equilibrium with linear strategies. That is, there is an equilibrium when both players' bids are some linear functions of their valuations. It is also brings higher expected gains for the players than any other Bayesian Nash equilibrium (see Myerson–Satterthwaite theorem).

Mechanism design

How should the auctioneer determine the trading price? An ideal mechanism would satisfy the following properties:

1. Individual Rationality (IR): no person should lose from joining the auction. In particular, for every trading buyer: p ≤ B, and for every trading seller: p ≥ S.

2. Balanced Budget (BB) comes in two flavors:

3. Incentive compatibility (IC) also alled truthfulness or strategy-proofness: also comes in two flavors (when unqualified IC generally means the stronger version):

4. Economic efficiency (EE): the total social welfare (the sum of the values of all players) should be the best possible. In particular, this means that, after all trading has completed, the items should be in the hands of those that value them the most.

Unfortunately, it is not possible to achieve all these requirements in the same mechanism (see Myerson–Satterthwaite theorem). But there are mechanisms that satisfy some of them.

Average mechanism

The mechanism described in the previous section can be generalized to n players in the following way.

  • Order the buyers and sellers in the Natural ordering and find the breakeven index k.
  • Set the price at the average of the kth values: p=(bk+sk)/2.
  • Let the first k sellers sell the good to the first k buyers.

This mechanism is:

  • IR - because by the ordering, the first k players value each item as at least p and the first k sellers value each item as at most p.
  • SBB - because all monetary transfers are between buyers and sellers.
  • EE - because the n items are held by the n players who value them the most.
  • Not IC - because buyer k has an incentive to report a lower value and seller k has an incentive to report a higher value.

VCG mechanism

A VCG mechanism is a generic mechanism which optimizes the social welfare while achieving truthfulness. It does so by making each agent pay for the "damage" that his desires cause to society.

In the simple bilateral trade setting, this translates to the following mechanism:

  • If bs then no trade is done and the product remains with the seller;
  • If b>s then the product goes to the buyer, the buyer pays s and the seller receives b.

This mechanism is:

  • IR, since the buyer pays less than his value and the seller receives more than his value.
  • IC, since the price paid by the buyer is determined by the seller and vice versa. Any attempt to misreport will make the utility of the misreporter either zero or negative.
  • EE, because the product goes to the one who values it the most.
  • Not SBB nor even WBB, because the auctioneer has to pay b-s. The auctioneer actually has to subsidize the trade.

In the general double auction setting, the mechanism orders the buyers and sellers in the Natural ordering and finds the breakeven index k. Then the first k sellers give the item to the first k buyers. Each buyer pays the lowest equilibrium price max(sk,bk+1), and each seller receives the highest equilibrium price min(bk,sk+1), as in the following table:

sk+1 > bksk+1bk
bk+1 < skEach buyer pays sk and each seller gets bkEach buyer pays sk and each seller gets sk+1
bk+1skEach buyer pays bk+1 and each seller gets bkEach buyer pays bk+1 and each seller gets sk+1

Similar to the bilateral trade scenario, the mechanism is IR, IC and EE (optimizes the social welfare), but it is not BB - the auctioneer subsidizes the trade.

The uniqueness-of-prices theorem [3] implies that this subsidy problem is inevitable - any truthful mechanism that optimizes the social welfare will have the same prices (up to a function independent of the ask/bid prices of each trader). If we want to keep the mechanism truthful while not having to subsidize the trade, we must compromise on efficiency and implement a less-than-optimal social welfare function.

Trade reduction mechanism

The following mechanism gives up a single deal in order to maintain truthfulness: [4]

  • Order the buyers and sellers in the Natural ordering and find the breakeven index k.
  • The first k-1 sellers give the item and receive sk from the auctioneer;
  • The first k-1 buyers receive the item and pay bk to the auctioneer.

This mechanism is:

  • IR, as before.
  • IC: the first k-1 buyers and sellers have no incentive to change their declaration since this will have no effect on their price; the kth buyer and seller have no incentive to change since they don't trade anyway, and if they do enter the trading (e.g. bk increases his declaration above bk-1), their profit from trading will be negative.
  • Not SBB, because the auctioneer is left with a surplus of (k-1)(bk-sk). But it is WBB, since the auctioneer at least doesn't have to subsidize the trade.
  • Not EE, because bk and sk don't trade, although buyer k values the item more than seller k.

If we tried to make this mechanism efficient by letting the kth buyer and seller trade, this would make it untruthful because then they will have an incentive to change their prices.

Although the social welfare is not optimal, it is near-optimal, since the forbidden deal is the least favorable deal. Hence the gain-from-trade is at least of the optimum.

Note that in the bilateral trade setting, k=1 and we give up the only efficient deal, so there is no trade at all and the gain-from-trade is 0. This is in accordance with the Myerson-Satterthwaite theorem.

Babaioff, Nisan and Pavlov [5] generalised the trade reduction mechanism to a market that is spatially-distributed, i.e. the buyers and sellers are in several different locations, and some units of the good may have to be transported between these locations. The cost of transport is thus added to the cost of production of the sellers.

McAfee's mechanism

Mcafee [4] presented the following variation on the trade-reduction mechanism:

  • Order the buyers and sellers in the Natural ordering and find the breakeven index k.
  • Calculate: p=(bk+1+sk+1)/2.
  • If bkpsk, then the first k buyers and sellers trade the good in price p.
  • Otherwise, the first k-1 sellers trade for sk and the first k-1 buyers trade for bk as in the trade-reduction mechanism.

Similarly to the trade-reduction mechanism, this mechanism is IR, IC, WBB but not SBB (in the second case) and not EE (in the second case). Assuming that the values of the buyers and sellers are all bounded above zero, McAfee proves that the loss of trade efficiency is bounded by 1/min(num-of-buyers,num-of-sellers). [4]

Probabilistic reduction mechanisms

Given a p∈[0,1], after the bids are submitted, use the Trade reduction mechanism with probability p and the VCG mechanism with probability 1-p. [6] This mechanism inherits all the properties of its parents, i.e. it is IR and IC. The parameter p controls the tradeoff between EE and BB:

  • The loss of gain-from-trade is either 0 (achieved by VCG) or 1/k (achieved by trade-reduction); hence the expected loss in gain-from-trade is at most: p/k.
  • The auctioneer surplus is either negative (in case of VCG) or positive (in case of trade-reduction); hence the expected surplus is p*(surplus-in-trade-reduction)-(1-p)*(deficit-in-VCG). If the values of the traders come from known distribution, p can be selected such that the expected surplus will be 0, i.e. the mechanism is SBB ex-ante.

In a variant of this mechanism, [6] after the bids are submitted, the k-1 cheap sellers trade with the k-1 expensive buyers; each of them receives/pays the expected payment of the original mechanism, i.e. each buyer pays and each seller receives . Then, with probability p, buyer k pays and buys the good from seller k who receives . Like the first variant, this variant is IR and has the same expected efficiency and surplus. Its advantage is that it "hides" its randomized character from almost all traders. The downside is that now the mechanism is truthful only ex-ante; i.e., a risk-neutral trader cannot gain in expectation by misreporting his value, but after he knows the results of the lot, he might feel regret for not reporting otherwise.

SBBA mechanism

Segal-Halevi, Hassidim and Aumann [7] present a trade-reduction mechanism that is SBB, in addition to being IR and IC and attains (1-1/k) of the optimal GFT.

Comparison

Babaioff and Nisan [6] :Chap.4 provide both a theoretic comparison and an empirical comparison of the various mechanisms.

Modular approach

Dütting, Roughgarden and Talgam-Cohen [8] proposed a modular approach to the design of double auctions. Their framework views double auctions as being composed of ranking algorithms for each side of the market and a composition rule, and can be applied to complex markets. An immediate consequence of this framework is that classic double auction mechanisms such as the trade reduction mechanism are not only strategyproof but also weakly group-strategyproof (meaning that no group of buyers and sellers can benefit by a joint misreport of their preferences).

Beyond two categories

The basic double auction model involves two categories of traders: buyers and sellers. Babaioff and Nisan [6] extended it to handle a supply chain - a chain of markets, in which the buyers in one market become sellers in the next market. E.g., farmers sell fruits in the fruit market; juice makers buy fruits in the fruit market, make juice and sell it in the juice market to consumers. Babaioff and Walsh [9] extended it to handle markets in an arbitrary directed acyclic graph.

Gilor, Gonen and Segal-Halevi [10] study a multilateral market, with a set G of agent categories. he market is characterized by an integer vector r of size |G|, called the recipe of the market. Each trade in the market involves rg agents of category g, for each g in G. The standard double auction market is a special case in which there are two categories (buyers and sellers), and the recipe is r=(1,1). They present algorithms that are SBB, IC, IR and attain (1-1/k) of the optimal GFT. One algorithm is a direct revelation mechanism based on trade-reduction, and the other is an ascending-price mechanism that is not only IC but also obviously IC.

Gilor, Gonen and Segal-Halevi [11] study a more general multilateral market, in which there are multiple different recipes, arranged as a forest, where each recipe is a path from a root to a leaf. They present randomized ascending-price mechanisms that are universally IR, obviously-IC, SBB, and attain an asymptotically-optimal GFT.

See also

Notes

  1. Friedman, Daniel (1992). The Double Auction Market Institution: A Survey (PDF).
  2. Tagiew, Rustam (22 May 2009). "Towards Barter Double Auction as Model for Bilateral Social Cooperations". arXiv: 0905.3709 [cs.GT].
  3. Nisan, Noam (2007). "Introduction to Mechanism Design for Computer Scientists". In Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Vazirani, Vijay (eds.). Algorithmic Game Theory. pp. 230–231. doi:10.1017/CBO9780511800481.011. ISBN   978-0521872829. S2CID   154357584.
  4. 1 2 3 McAfee, R. P. (1992). "A dominant strategy double auction". Journal of Economic Theory. 56 (2): 434–450. doi:10.1016/0022-0531(92)90091-u.
  5. Babaioff, M.; Nisan, N.; Pavlov, E. (2004). "Mechanisms for a spatially distributed market". Proceedings of the 5th ACM conference on Electronic commerce - EC '04. p. 9. doi:10.1145/988772.988776. ISBN   1-58113-771-0.
  6. 1 2 3 4 M. Babaioff; N. Nisan (2004). "Concurrent Auctions Across The Supply Chain". Journal of Artificial Intelligence Research. 21: 595–629. arXiv: 1107.0028 . doi:10.1613/jair.1316. S2CID   58535404.
  7. Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). "SBBA: A Strongly-Budget-Balanced Double-Auction Mechanism". In Gairing, Martin; Savani, Rahul (eds.). Algorithmic Game Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 260–272. arXiv: 1607.05139 . doi:10.1007/978-3-662-53354-3_21. ISBN   978-3-662-53354-3.
  8. Dütting, Paul; Roughgarden, Tim; Talgam-Cohen, Inbal (2014). Modularity and Greed in Double Auctions (PDF). Proceedings of the 15th Conference on Economics and Computation (EC'14). pp. 241–258. doi:10.1145/2600057.2602854. ISBN   9781450325653.
  9. Babaioff, M.; Walsh, W. E. (2005). "Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation". Decision Support Systems. 39: 123–149. CiteSeerX   10.1.1.4.4123 . doi:10.1016/j.dss.2004.08.008.
  10. Gilor, Dvir; Gonen, Rica; Segal-Halevi, Erel (2021-11-01). "Strongly budget balanced auctions for multi-sided markets". Artificial Intelligence. 300: 103548. arXiv: 1911.08094 . doi:10.1016/j.artint.2021.103548. ISSN   0004-3702.
  11. Gilor, Dvir; Gonen, Rica; Segal-Halevi, Erel (2023-12-01). "Ascending-price mechanism for general multi-sided markets" . Artificial Intelligence. 325: 104022. doi:10.1016/j.artint.2023.104022. ISSN   0004-3702.

Related Research Articles

<span class="mw-page-title-main">Auction</span> Process of offering goods or services up for bids

An auction is usually a process of buying and selling goods or services by offering them up for bids, taking bids, and then selling the item to the highest bidder or buying the item from the lowest bidder. Some exceptions to this definition exist and are described in the section about different types. The branch of economic theory dealing with auction types and participants' behavior in auctions is called auction theory.

<span class="mw-page-title-main">Mechanism design</span> Field of economics and game theory

Mechanism design is a branch of economics, social choice theory, and game theory that deals with designing games to implement a given social choice function. Because it starts at the end of the game and then works backwards to find a game that implements it, it is sometimes called reverse game theory.

<span class="mw-page-title-main">Vickrey auction</span> Auction priced by second-highest sealed bid

A Vickrey auction or sealed-bid second-price auction (SBSPA) is a type of sealed-bid auction. Bidders submit written bids without knowing the bid of the other people in the auction. The highest bidder wins but the price paid is the second-highest bid. This type of auction is strategically similar to an English auction and gives bidders an incentive to bid their true value. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893. In 1797 Johann Wolfgang von Goethe sold a manuscript using a sealed-bid, second-price auction.

<span class="mw-page-title-main">English auction</span> Type of dynamic auction

An English auction is an open-outcry ascending dynamic auction. It proceeds as follows.

<span class="mw-page-title-main">Japanese auction</span>

A Japanese auction is a dynamic auction format. It proceeds in the following way.

The Myerson–Satterthwaite theorem is an important result in mechanism design and the economics of asymmetric information, and named for Roger Myerson and Mark Satterthwaite. Informally, the result says that there is no efficient way for two parties to trade a good when they each have secret and probabilistically varying valuations for it, without the risk of forcing one party to trade at a loss.

A mechanism is called incentive-compatible (IC) or truthful if every participant can achieve their own best outcome by acting according to their true preferences. For example, there is incentive compatibility if high-risk clients are better off in identifying themselves as high-risk to insurance firms, who only sell discounted insurance to high-risk clients. Likewise, they would be worse off if they pretend to be low-risk. Low-risk clients who pretend to be high-risk would also be worse off.

<span class="mw-page-title-main">Auction theory</span> Branch of applied economics regarding the behavior of bidders in auctions

Auction theory is an applied branch of economics which deals with how bidders act in auctions and researches how the features of auctions incentivise predictable outcomes. Auction theory is a tool used to inform the design of real-world auctions. Sellers use auction theory to raise higher revenues while allowing buyers to procure at a lower cost. The conference of the price between the buyer and seller is an economic equilibrium. Auction theorists design rules for auctions to address issues which can lead to market failure. The design of these rulesets encourages optimal bidding strategies among a variety of informational settings. The 2020 Nobel Prize for Economics was awarded to Paul R. Milgrom and Robert B. Wilson “for improvements to auction theory and inventions of new auction formats.”

<span class="mw-page-title-main">Multiunit auction</span>

A multiunit auction is an auction in which several homogeneous items are sold. The units can be sold each at the same price or at different prices.

The revelation principle is a fundamental result in mechanism design, social choice theory, and game theory which shows it is always possible to design a strategy-resistant implementation of a social decision-making mechanism. It can be seen as a kind of mirror image to Gibbard's theorem. The revelation principle says that if a social choice function can be implemented using some non-truthful mechanism, the same function can be implemented by a truthful mechanism which has the same equilibrium outcome (payoffs).

<span class="mw-page-title-main">First-price sealed-bid auction</span> Auction where all participants concurrently submit undisclosed bids

A first-price sealed-bid auction (FPSBA) is a common type of auction. It is also known as blind auction. In this type of auction, all bidders simultaneously submit sealed bids so that no bidder knows the bid of any other participant. The highest bidder pays the price that was submitted.

Competitive equilibrium is a concept of economic equilibrium, introduced by Kenneth Arrow and Gérard Debreu in 1951, appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.

<span class="mw-page-title-main">Revenue equivalence</span>

Revenue equivalence is a concept in auction theory that states that given certain conditions, any mechanism that results in the same outcomes also has the same expected revenue.

In mechanism design, a Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially-optimal solution. It is a generalization of a Vickrey–Clarke–Groves auction. A VCG auction performs a specific task: dividing items among people. A VCG mechanism is more general: it can be used to select any outcome out of a set of possible outcomes.

A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of these variables.

A prior-free mechanism (PFM) is a mechanism in which the designer does not have any information on the agents' valuations, not even that they are random variables from some unknown probability distribution.

In mechanism design and auction theory, a profit extraction mechanism is a truthful mechanism whose goal is to win a pre-specified amount of profit, if it is possible.

<span class="mw-page-title-main">Price of anarchy in auctions</span>

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.

A supply-chain auction is an auction for coordinating trade among various suppliers and consumers in a supply chain. It is a generalization of a double auction. In a double auction, each deal involves two agents - a buyer and a seller, so the "supply-chain" contains only a single link. In a general supply-chain auction, each deal may involve many different agents, for example: a seller, a mediator, a transporter and a buyer.

<span class="mw-page-title-main">Budget-balanced mechanism</span>

In mechanism design, a branch of economics, a weakly-budget-balanced (WBB) mechanism is a mechanism in which the total payment made by the participants is at least 0. This means that the mechanism operator does not incur a deficit, i.e., does not have to subsidize the market. Weak budget balance is considered a necessary requirement for the economic feasibility of a mechanism. A strongly-budget-balanced (SBB) mechanism is a mechanism in which the total payment made by the participants is exactly 0. This means that all payments are made among the participants - the mechanism has neither a deficit nor a surplus. The term budget-balanced mechanism is sometimes used as a shorthand for WBB, and sometimes as a shorthand for SBB.

References