Finance:Budget-balanced mechanism

From HandWiki

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

  • 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" (in en). 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. http://www.sciencedirect.com/science/article/pii/S0167923604001757. 
  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. https://pubsonline.informs.org/doi/abs/10.1287/trsc.2016.0694. 
  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 (in en). Agent-Mediated Electronic Commerce. Designing Trading Agents and Mechanisms. Lecture Notes in Computer Science. 3937. Berlin, Heidelberg: Springer. pp. 71–84. doi:10.1007/11888727_6. ISBN 978-3-540-46243-9. https://link.springer.com/chapter/10.1007/11888727_6. 
  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. https://dl.acm.org/doi/abs/10.5555/1558109.1558254. 
  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. 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. doi:10.1145/3381523. ISSN 2167-8375. 
  8. ↑ Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). "SBBA: A Strongly-Budget-Balanced Double-Auction Mechanism". in Gairing, Martin; Savani, Rahul (in en). Algorithmic Game Theory. Lecture Notes in Computer Science. 9928. Berlin, Heidelberg: Springer. pp. 260–272. doi:10.1007/978-3-662-53354-3_21. ISBN 978-3-662-53354-3. https://link.springer.com/chapter/10.1007/978-3-662-53354-3_21. 
  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. ISBN 978-0-9992411-2-7. https://dl.acm.org/doi/abs/10.5555/3304415.3304485. 
  11. ↑ Gonen, Rica; Segal-Halevi, Erel (2020-04-03). "Strongly Budget Balanced Auctions for Multi-Sided Markets" (in en). Proceedings of the AAAI Conference on Artificial Intelligence 34 (2): 1998–2005. doi:10.1609/aaai.v34i02.5571. ISSN 2374-3468. https://ojs.aaai.org/index.php/AAAI/article/view/5571. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Finance:Budget-balanced_mechanism&oldid=3318558"