Misplaced Pages

Part of a series on
Auctions
Types
All-pay Chinese Bidding fee Dollar Amsterdam Anglo-Dutch Barter double Best/not best Brazilian Calcutta Candle Click-box bidding Combinatorial Common value Deferred-acceptance Discriminatory price Double Dutch English Forward French Generalized first-price Generalized second-price Japanese Knapsack Multi-attribute Multiunit No-reserve Rank Reverse Scottish Sealed first-price Simultaneous ascending Single-price Traffic light Uniform price Unique bid Value of revenues Vickrey Vickrey–Clarke–Groves Walrasian Yankee
Bidding
Shading Calor licitantis Cancellation hunt Jump Rigging Sniping Suicide Tacit collusion
Contexts
Algorithms Autos Art Charity Children Players Domain names Flowers Loans Scam Slaves Spectrum Stamps Virginity Wine Wives
Theory
Digital goods Price of anarchy Revenue equivalence Winner's curse
Online
Ebidding Private electronic market Software
v t e

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.

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 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. See double auction for more details.

Strong budget balance

In a strongly-budget-balanced (SBB) mechanism, all payments are made between the participants themselves. 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. Some of them have been generalized to multi-sided markets.

See also

• Balanced budget - a budget in which revenues are equal to expenditures
• Government budget balance - a financial statement presenting the government's proposed revenues and spending for a financial year.
• Balanced budget amendment - a rule in the USA constitution requiring that a state cannot spend more than its income.

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

• Mechanism design
• Auction theory