Budget-balanced mechanism: Difference between revisions
Content deleted Content added
Erel Segal (talk | contribs) ←Created page with 'In mechanism design, a branch of economics, a '''budget-balanced (BB) mechanism''' is a mechanism in which the total payment made by the participants is...' |
Erel Segal (talk | contribs) No edit summary |
||
| Line 1: | Line 1: | ||
In [[mechanism design]], a branch of [[economics]], a '''budget-balanced (BB) 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 spending|deficit]], i.e., does not have to subsidize the market. Budget balance is considered a necessary requirement for the economic feasibility of a mechanism. |
In [[mechanism design]], a branch of [[economics]], a '''budget-balanced (BB) 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 spending|deficit]], i.e., does not have to subsidize the market. Budget balance is considered a necessary requirement for the economic feasibility of a mechanism. |
||
== Examples == |
== Examples == |
||
A simple example of a BB 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. |
A simple example of a BB 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-BB 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|Myerson-satterthwaite theorem]] says that ''every'' [[Pareto-efficient]] truthful mechanism must run a deficit. McAfee<ref name="mcafee92">{{Cite journal|last1=McAfee|first1=R. P.|year=1992|title=A dominant strategy double auction|journal=Journal of Economic Theory|volume=56|issue=2|pages=434–450|doi=10.1016/0022-0531(92)90091-u}}</ref> developed a solution to this problem for a large market (with many potential buyers and sellers): McAfee's mechanism is BB, truthful and almost Pareto-efficient |
As an example of a non-BB 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|Myerson-satterthwaite theorem]] says that ''every'' [[Pareto-efficient]] truthful mechanism must run a deficit. |
||
McAfee<ref name="mcafee92">{{Cite journal|last1=McAfee|first1=R. P.|year=1992|title=A dominant strategy double auction|journal=Journal of Economic Theory|volume=56|issue=2|pages=434–450|doi=10.1016/0022-0531(92)90091-u}}</ref> developed a solution to this problem for a large market (with many potential buyers and sellers): McAfee's mechanism is BB, truthful and almost Pareto-efficient - it performs all efficient deals except at most one. See [[double auction]] for more details. |
|||
== Strong and weak == |
|||
In a '''strongly-budget-balanced (SBB) mechanism''', the total payment of the participants in the mechanism is exactly 0. This means that the mechanism has neither a deficit nor a surplus; all payments are made between the participants themselves.<ref>{{Cite journal|last=Bachrach|first=Yoram|last2=Rosenschein|first2=Jeffrey S.|date=2006|editor-last=La Poutré|editor-first=Han|editor2-last=Sadeh|editor2-first=Norman M.|editor3-last=Janson|editor3-first=Sverker|title=Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents|url=https://link.springer.com/chapter/10.1007/11888727_6|journal=Agent-Mediated Electronic Commerce. Designing Trading Agents and Mechanisms|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=71–84|doi=10.1007/11888727_6|isbn=978-3-540-46243-9}}</ref><ref>{{Cite journal|last=Sakurai|first=Yuko|last2=Saito|first2=Yasumasa|last3=Iwasaki|first3=Atsushi|last4=Yokoo|first4=Makoto|date=2009-05-10|title=Sequential partition mechanism for strongly budget-balanced redistribution|url=https://dl.acm.org/doi/abs/10.5555/1558109.1558254|journal=Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 2|series=AAMAS '09|location=Budapest, Hungary|publisher=International Foundation for Autonomous Agents and Multiagent Systems|pages=1285–1286|doi=10.5555/1558109.1558254|isbn=978-0-9817381-7-8}}</ref> An advantage of SBB is that all the [[Gains from trade|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. |
|||
A BB mechanism which may has a surplus is often called '''weakly-budget-balanced (WBB)'''. McAfee's mechanism is only WBB - it may have a surplus, and this surplus may account for almost all the gain from trade. Recently, some SBB mechanisms for double auction have been developed.<ref>{{Citation|last=Colini-Baldeschi|first=Riccardo|title=Approximately Efficient Double Auctions with Strong Budget Balance|date=2015-12-21|url=https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch98|work=Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms|pages=1424–1443|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611974331.ch98|access-date=2020-10-16|last2=Keijzer|first2=Bart de|last3=Leonardi|first3=Stefano|last4=Turchetta|first4=Stefano}}</ref><ref>{{Cite journal|last=Colini-Baldeschi|first=Riccardo|last2=Goldberg|first2=Paul W.|last3=Keijzer|first3=Bart de|last4=Leonardi|first4=Stefano|last5=Roughgarden|first5=Tim|last6=Turchetta|first6=Stefano|date=2020-03-11|title=Approximately Efficient Two-Sided Combinatorial Auctions|url=https://doi.org/10.1145/3381523|journal=ACM Transactions on Economics and Computation|volume=8|issue=1|pages=4:1–4:29|doi=10.1145/3381523|issn=2167-8375}}</ref><ref>{{Cite journal|last=Segal-Halevi|first=Erel|last2=Hassidim|first2=Avinatan|last3=Aumann|first3=Yonatan|date=2016|editor-last=Gairing|editor-first=Martin|editor2-last=Savani|editor2-first=Rahul|title=SBBA: A Strongly-Budget-Balanced Double-Auction Mechanism|url=https://link.springer.com/chapter/10.1007/978-3-662-53354-3_21|journal=Algorithmic Game Theory|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=260–272|doi=10.1007/978-3-662-53354-3_21|isbn=978-3-662-53354-3}}</ref> |
|||
== See also == |
== See also == |
||
Revision as of 12:40, 16 October 2020
In mechanism design, a branch of economics, a budget-balanced (BB) 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. Budget balance is considered a necessary requirement for the economic feasibility of a mechanism.
Examples
A simple example of a BB 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-BB 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 run a deficit.
McAfee[1] developed a solution to this problem for a large market (with many potential buyers and sellers): McAfee's mechanism is BB, truthful and almost Pareto-efficient - it performs all efficient deals except at most one. See double auction for more details.
Strong and weak
In a strongly-budget-balanced (SBB) mechanism, the total payment of the participants in the mechanism is exactly 0. This means that the mechanism has neither a deficit nor a surplus; all payments are made between the participants themselves.[2][3] 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.
A BB mechanism which may has a surplus is often called weakly-budget-balanced (WBB). McAfee's mechanism is only WBB - it may have a surplus, and this surplus may account for almost all the gain from trade. Recently, some SBB mechanisms for double auction have been developed.[4][5][6]
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
- ^ 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.
- ^ Bachrach, Yoram; Rosenschein, Jeffrey S. (2006). La Poutré, Han; Sadeh, Norman M.; Janson, Sverker (eds.). "Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents". Agent-Mediated Electronic Commerce. Designing Trading Agents and Mechanisms. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 71–84. doi:10.1007/11888727_6. ISBN 978-3-540-46243-9.
- ^ 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. doi:10.5555/1558109.1558254. ISBN 978-0-9817381-7-8.
{{cite journal}}: Check|doi=value (help) - ^ 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, Proceedings, Society for Industrial and Applied Mathematics, pp. 1424–1443, doi:10.1137/1.9781611974331.ch98, retrieved 2020-10-16
- ^ 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.
- ^ Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). Gairing, Martin; Savani, Rahul (eds.). "SBBA: A Strongly-Budget-Balanced Double-Auction Mechanism". Algorithmic Game Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 260–272. doi:10.1007/978-3-662-53354-3_21. ISBN 978-3-662-53354-3.