Abstract
We present a strategy-proof public goods budgeting mechanism where agents determine both the total volume of expenses and specific allocation. It is constructed as a modification of VCG to a non-typical environment, where we do not assume quasi-linear utilities or direct revelation. We further show that under plausible assumptions it satisfies strategyproofness in strictly dominant strategies, and consequently implements the social optimum as a Coalition-Proof Nash Equilibrium. A primary (albeit not an exclusive) motivation of our model is Participatory Budgeting, where members of a community collectively decide the spending policy of public tax dollars. In that scenario, charging individual payments from voters as the VCG method instructs would be undesirable, thus our second main result provides that, under further specifications relevant in that context, these payments will vanish in large populations, and can further be constructed as non-positive in some cases.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
- 2.
‘The Participatory Budget Project’: https://www.participatorybudgeting.org/.
- 3.
- 4.
See for example https://data.oecd.org/gga/general-government-spending.htm, and [29].
- 5.
- 6.
For example, if \(h(\vec {\alpha }_{-i})=\sum _{j \ne i}v_k(g(\bar{\alpha }_{-i}))\) and all agents collude and report \(\bar{\alpha }\), the outcome does not change while their payments will be eliminated.
- 7.
- 8.
In applications other than PB this may not be plausible. However, in such applications charging payments from agents could be acceptable.
- 9.
See for example https://data.oecd.org/gga/general-government-spending.htm, and [29].
- 10.
In the full version of the paper we show some preliminary regularity condition that implies differentiability given that \(g(\bar{\alpha })\) is unique.
References
Aziz, H., Bogomolnaia, A., Moulin, H.: Fair mixing: the case of dichotomous preferences. In: ACM-EC 2019, pp. 753–781 (2019)
Aziz, H., Ganguly, A.: Participatory funding coordination: model, axioms and rules. In: Fotakis, D., Ríos Insua, D. (eds.) ADT 2021. LNCS (LNAI), vol. 13023, pp. 409–423. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-87756-9_26
Bachrach, Y.: Honor among thieves: collusion in multi-unit auctions. In: AAMAS’10, pp. 617–624 (2010)
Benade, G., Nath, S., Procaccia, A.D., Shah, N.: Preference elicitation for participatory budgeting. Manage. Sci. 67(5), 2813–2827 (2021)
Bernard, A.: Optimal taxation and public production with budget constraints. In: The Economics of Public Services: Proceedings of a Conference held by the International Economic Association at Turin, Italy, pp. 361–389. Palgrave Macmillan, London (1977). https://doi.org/10.1007/978-1-349-02917-4_15
Bernheim, B.D., Peleg, B., Whinston, M.D.: Coalition-proof nash equilibria i. concepts. J. Econ. Theory 42(1), 1–12 (1987)
Bjorvatn, K., Schjelderup, G.: Tax competition and international public goods. Int. Tax Public Finan. 9, 111–120 (2002)
Booij, A.S., Van Praag, B.M., Van De Kuilen, G.: A parametric analysis of prospect theory’s functionals for the general population. Theory Decis. 68(1–2), 115–148 (2010)
Brandl, F., Brandt, F., Peters, D., Stricker, C.: Distribution rules under dichotomous preferences: two out of three ain’t bad. In: Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 158–179 (2021)
Brandl, F., Brandt, F., Peters, D., Stricker, C., Suksompong, W.: Funding public projects: a case for the nash product rule. arXiv preprint arXiv:2005.07997 (2020)
Cavallo, R.: Optimal decision-making with minimal waste: strategyproof redistribution of VCG payments. In: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 882–889 (2006)
Clarke, E.H.: Multipart pricing of public goods. Public choice, pp. 17–33 (1971)
Conitzer, V., Sandholm, T.: Failures of the VCG mechanism in combinatorial auctions and exchanges. In: AAMAS’06, pp. 521–528 (2006)
Fain, B., Goel, A., Munagala, K.: The core of the participatory budgeting problem. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 384–399. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-54110-4_27
Fairstein, R., Lauz, A., Gal, K., Meir, R.: Modeling peoples voting behavior with poll information. arXiv preprint arXiv:1909.10492 (2019)
Freeman, R., Pennock, D.M., Peters, D., Wortman Vaughan, J.: Truthful aggregation of budget proposals. In: ACM-EC’19, pp. 751–752 (2019)
Garg, N., Kamble, V., Goel, A., Marn, D., Munagala, K.: Iterative local voting for collective decision-making in continuous spaces. J. Artif. Intell. Res. 64, 315–355 (2019)
Gibbard, A.: Manipulation of voting schemes: a general result. Econometrica: J. Econ. Soc., pp. 587–601 (1973)
Goel, A., Krishnaswamy, A.K., Sakshuwong, S., Aitamurto, T.: Knapsack voting for participatory budgeting. ACM Trans. Econ. Comput. (TEAC) 7(2), 1–27 (2019)
Guo, M., Conitzer, V.: Worst-case optimal redistribution of VCG payments in multi-unit auctions. Games Econ. Behav. 67(1), 69–98 (2009)
Jain, K., Vazirani, V.V.: Eisenberg-gale markets: algorithms and structural properties. In: STOC’07, pp. 364–373 (2007)
Krugman, P., Wells, R.: Microeconomics. Macmillan (2008)
Lahkar, R., Mukherjee, S.: Dominant strategy implementation in a large population public goods game. Econ. Lett. 197, 109616 (2020)
Nehring, K., Puppe, C.: The structure of strategy-proof social choice-part i: general characterization and possibility results on median spaces. J. Econ. Theory 135(1), 269–305 (2007)
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic game theory, 2007. Book available for free online (2007)
Rey, S., Maly, J.: The (computational) social choice take on indivisible participatory budgeting. arXiv preprint arXiv:2303.00621 (2023)
Roberts, K.: The characterization of implementable choice rules. Aggregation Revelation Preferences 12(2), 321–348 (1979)
Satterthwaite, M.A.: Strategy-proofness and arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory 10(2), 187–217 (1975)
Stiglitz, J.E.: The theory of local public goods. In: The Economics of Public Services: Proceedings of a Conference Held by the International Economic Association at Turin, Italy. pp. 274–333. Springer (1977). https://doi.org/10.1007/978-1-349-02917-4_12
Talmon, N., Faliszewski, P.: A framework for approval-based budgeting methods. In: AAAI’19, vol. 33, pp. 2181–2188 (2019)
Tversky, A., Kahneman, D.: Advances in prospect theory: cumulative representation of uncertainty. J. Risk Uncertainty 5(4), 297–323 (1992)
Vazirani, V.V., Yannakakis, M.: Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM (JACM) 58(3), 1–25 (2011)
Wagner, J., Meir, R.: Strategy-proof budgeting via a VCG-like mechanism. arXiv preprint arXiv:2303.06923 (2023)
Wildasin, D.E.: Nash equilibria in models of fiscal competition. J. Public Econ. 35(2), 229–240 (1988)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Wagner, J., Meir, R. (2023). Strategy-Proof Budgeting via a VCG-Like Mechanism. In: Deligkas, A., Filos-Ratsikas, A. (eds) Algorithmic Game Theory. SAGT 2023. Lecture Notes in Computer Science, vol 14238. Springer, Cham. https://doi.org/10.1007/978-3-031-43254-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-031-43254-5_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43253-8
Online ISBN: 978-3-031-43254-5
eBook Packages: Computer ScienceComputer Science (R0)