Budget-balanced mechanism

Last updated

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.

Contents

Weak budget balance

A simple example of a WBB mechanism is the Vickrey auction, in which the operator wants to sell an object to one of n potential buyers. Each potential buyer bids a value, the highest bidder wins an object and pays the second-highest bid. As all bids are positive, the total payment is trivially positive too.

As an example of a non-WBB mechanism, consider its extension to a bilateral trade setting. Here, there is a buyer and a seller; the buyer has a value of b and the seller has a cost of s. Trade should occur if and only if b > s. The only truthful mechanism that implements this solution must charge a trading buyer the cost s and pay a trading seller the value b; but since b > s, this mechanism runs a deficit. In fact, the Myerson–Satterthwaite theorem says that every Pareto-efficient truthful mechanism must incur a deficit.

McAfee [1] developed a solution to this problem for a large market (with many potential buyers and sellers): McAfee's mechanism is WBB, truthful and almost Pareto-efficient - it performs all efficient deals except at most one. McAfee's mechanism has been extended to various settings, while keeping its WBB property. [2] [3] See double auction for more details.

Strong budget balance

In a strongly-budget-balanced (SBB) mechanism, all payments are made between the participants themselves. [4] [5] An advantage of SBB is that all the gain from trade remains in the market; thus, the long-term welfare of the traders is larger and their tendency to participate may be higher.

McAfee's double-auction mechanism is WBB but not SBB - it may have a surplus, and this surplus may account for almost all the gain from trade. There is a simple SBB mechanism for bilateral trading: trade occurs iff b > s, and in this case the buyer pays (b+s)/2 to the seller. Since the payment goes directly from the buyer to the seller, the mechanism is SBB; however, it is not truthful, since the buyer can gain by bidding b' < b and the seller can gain by bidding s' > s. Recently, some truthful SBB mechanisms for double auction have been developed. [6] [7] [8] [9] [10] Some of them have been generalized to multi-sided markets. [11]

See also

Related Research Articles

<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">Double auction</span> Process of buying and selling goods

A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. 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.

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.

In economics, philosophy, and social choice theory, a person's entitlement refers to the value of goods they are owed or deserve, i.e. the total value of the goods or resources that a player would ideally receive. For example, in party-list proportional representation, a party's seat entitlement is equal to its share of the vote, times the number of seats in the legislature.

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/n of the total.

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

A sequential auction is an auction in which several items are sold, one after the other, to the same group of potential buyers. In a sequential first-price auction (SAFP), each individual item is sold using a first price auction, while in a sequential second-price auction (SASP), each individual item is sold using a second price auction.

<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.

Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.

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.

In various parts of economics, the term free disposal implies that resources can be discarded without any cost. For example, a fair division setting with free disposal is a setting where some resources have to be divided fairly, but some of the resources may be left undivided, discarded or donated.

Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:

In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query asks an agent to specify a piece of cake with a given value.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

Egalitarian cake-cutting is a kind of fair cake-cutting in which the fairness criterion is the egalitarian rule. The cake represents a continuous resource, that has to be allocated among people with different valuations over parts of the resource. The goal in egalitarian cake-cutting is to maximize the smallest value of an agent; subject to this, maximize the next-smallest value; and so on. It is also called leximin cake-cutting, since the optimization is done using the leximin order on the vectors of utilities.

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

References

  1. ↑ 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.
  2. ↑ Babaioff, Moshe; Walsh, William E. (2005-03-01). "Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation". Decision Support Systems. The Fourth ACM Conference on Electronic Commerce. 39 (1): 123–149. doi:10.1016/j.dss.2004.08.008. ISSN   0167-9236.
  3. ↑ Xu, Su Xiu; Huang, George Q.; Cheng, Meng (2016-09-16). "Truthful, Budget-Balanced Bundle Double Auctions for Carrier Collaboration". Transportation Science. 51 (4): 1365–1386. doi:10.1287/trsc.2016.0694. ISSN   0041-1655.
  4. ↑ Bachrach, Yoram; Rosenschein, Jeffrey S. (2006). "Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents". In La Poutré, Han; Sadeh, Norman M.; Janson, Sverker (eds.). Agent-Mediated Electronic Commerce. Designing Trading Agents and Mechanisms. Lecture Notes in Computer Science. Vol. 3937. Berlin, Heidelberg: Springer. pp. 71–84. doi:10.1007/11888727_6. ISBN   978-3-540-46243-9.
  5. ↑ Sakurai, Yuko; Saito, Yasumasa; Iwasaki, Atsushi; Yokoo, Makoto (2009-05-10). "Sequential partition mechanism for strongly budget-balanced redistribution". Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 2. AAMAS '09. Budapest, Hungary: International Foundation for Autonomous Agents and Multiagent Systems: 1285–1286. ISBN   978-0-9817381-7-8.
  6. ↑ Colini-Baldeschi, Riccardo; Keijzer, Bart de; Leonardi, Stefano; Turchetta, Stefano (2015-12-21). "Approximately Efficient Double Auctions with Strong Budget Balance". Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. pp. 1424–1443. doi:10.1137/1.9781611974331.ch98. hdl:11573/871600. ISBN   978-1-61197-433-1.
  7. ↑ Colini-Baldeschi, Riccardo; Goldberg, Paul W.; Keijzer, Bart de; Leonardi, Stefano; Roughgarden, Tim; Turchetta, Stefano (2020-03-11). "Approximately Efficient Two-Sided Combinatorial Auctions". ACM Transactions on Economics and Computation. 8 (1): 4:1–4:29. arXiv: 1611.05342 . doi: 10.1145/3381523 . ISSN   2167-8375. S2CID   217190707.
  8. ↑ 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. Vol. 9928. Berlin, Heidelberg: Springer. pp. 260–272. arXiv: 1607.05139 . doi:10.1007/978-3-662-53354-3_21. ISBN   978-3-662-53354-3. S2CID   14358074.
  9. ↑ Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2017-12-19). "MUDA: A Truthful Multi-Unit Double-Auction Mechanism". arXiv: 1712.06848 [cs.GT].
  10. ↑ Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2018-07-13). "Double auctions in markets for multiple kinds of goods". Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI'18. Stockholm, Sweden: AAAI Press: 489–497. arXiv: 1604.06210 . ISBN   978-0-9992411-2-7.
  11. ↑ Gonen, Rica; Segal-Halevi, Erel (2020-04-03). "Strongly Budget Balanced Auctions for Multi-Sided Markets". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1998–2005. arXiv: 1911.08094 . doi: 10.1609/aaai.v34i02.5571 . ISSN   2374-3468.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.