Top

Social Choice and Welfare

Published in:

07-06-2023 | Original Paper

Strength in numbers: robust mechanisms for public goods with many agents

Authors: Jin Xi, Haitian Xie

Published in: Social Choice and Welfare | Issue 3/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This study examines the mechanism design problem for public goods provision in a large economy with n independent agents. We propose a class of dominant-strategy incentive compatible and ex-post individually rational mechanisms, which we call the adjusted mean-thresholding (AMT) mechanisms. We show that when the cost of provision grows slower than the \(\sqrt{n}\)-rate, the AMT mechanisms are both eventually ex-ante budget balanced and asymptotically efficient. When the cost grows faster than the \(\sqrt{n}\)-rate, in contrast, we show that any incentive compatible, individually rational, and eventually ex-ante budget balanced mechanism must have provision probability converging to zero and hence cannot be asymptotically efficient. The AMT mechanisms have a simple form and are more informationally robust when compared to, for example, the second-best mechanism. This is because the construction of an AMT mechanism depends only on the first moment of the valuation distribution.

previous article How does exposure to COVID-19 influence health and income inequality aversion?

next article Leading by example in a public goods experiment with benefit heterogeneity

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Myerson and Satterthwaite (1983) establish the impossibility result in the bilateral trade setting, but it extends directly to the public goods problem. We provide a more substantial overview of this problem below.

For any measurable set E, we use \({\mathbf {1}}E\) to denote the indicator function of E.

The second-best mechanism maximizes welfare among the class of mechanisms that are incentive compatible, individually rational, and budget balance. We discuss more about the second-best mechanism in Sects. 1.1 and 2.

The central limit theorem states that the distribution of sum of iid random variables is approximately a normal distribution. The Berry-Esseen theorem further specifies how close the normal approximation is.

For example, it would be difficult to derive such a result based on the proof method in Hellwig (2003). We provide a discussion on this issue in Appendix B.

This version can be found at: https://doi.org/10.48550/arXiv.2101.0242.

There is another notion of “large economy” in the literature that considers a continuum of agents and each agent is negligible compared to the population (Bierbrauer 2009, 2014; Bierbrauer and Hellwig 2015, 2016).

Hellwig (2003) also identifies the \(\sqrt{n}\)-rate in the context of Bayesian incentive compatibility. Our results are focused on the dominant-strategy incentive compatibility. One take-away here is that the weaker notion of Bayesian incentive compatibility does not relax this bound. This notion of equivalence between Bayesian incentive compatibility and dominant-strategy incentive compatibility represented by the requirement on the growth rate of cost can be seen as a complement to the theoretical results in Gershkov et al (2013).

This moment can come from any increasing and continuous transformation of the valuation. See Sect. 3.

In Sect. 3.3, we provide a more formal discussion of the qualitative difference between a moment and the distribution by using results in the information theory.

These papers examine the model of independent valuations. It is also possible to allow for correlated valuations while maintaining the moment restrictions on the marginal distributions. See Brooks and Du (2021); Zhang (2021).

Other works regarding the asymptotic efficiency of auctions in the independent private value setting include Swinkels (2001); Feldman et al (2016).

Other works on asymptotic approximation of the optimal revenue using robust auctions include Segal (2003), Neeman (2003), Goldberg et al (2006), Dhangwatnotai et al (2015). See also Hartline (2016, Chapter 5) for a comprehensive treatment of prior-independent mechanism design.

In Sect. 3, we discuss why the support is assumed to be in this form.

We can relax the assumptions that \({\bar{v}}\) is finite and that f is bounded away from zero. We only need to assume that the appropriate moments exist. However, that makes the exposition inconvenient.

In this paper, we use upper case letters to denote random variables and lower case letters to denote realizations or reported values.

We use the notion “budget balance” as in Kuzmics and Steg (2017) and Börgers (2015). It is also termed “feasible” or “subsidy-free” in the literature. Some literature uses the term “budget balance” to refer to the more stringent case where the total payment exactly equals the cost.

This definition of social welfare is standard in the literature. From the social planner’s perspective, the production cost does not enter into welfare because it does not directly affect agents’ utility. The cost only plays a role through the budget constraint.

See, for example, Myerson and Satterthwaite (1983) and Mailath and Postlewaite (1990).

The valuations explored in Kunimoto and Zhang (2021) are discrete. However, this aspect does not impact the results qualitatively, as both discrete and continuous distributions can be addressed using the general measure theory. Specifically, discrete probability measures have density functions with respect to the counting measure, enabling the computation of virtual valuations accordingly.

They refer to the “regret ratio” in this paper as “competitive ratio.”

This definition is equivalent to Definition 3.8 in Börgers (2015).

Since F is supported on \([0,{\bar{v}}]\), we have \(\int _{0}^{{\bar{v}}} (1-F(v)) dv = {\mathbb {E}}[V_i]\), \({\mathbb {E}}[\psi (V_i)] = {\mathbb {E}}[V_i] - \int _{0}^{{\bar{v}}} (1-F(v)) dv\) = 0. See the end of Sect. 3.2 for a discussion of the support.

See Eq. (12) and the discussion before it.

A similar intuition can be found in the proof of Proposition 3 in Hellwig (2003). Here, we provide a more detailed discussion regarding the rate of the threshold \(\alpha _n\).

However, we can extend our analysis to allow for a point mass at 0 in the distribution F. In that case, the density f is the Radon-Nykodim derivative of the probability measure F with respect to the measure \(L + \delta _0\), where L is the Lebesgue measure on \({\mathbb {R}}_+\) and \(\delta _0\) is the Dirac measure at 0. This underlying measure is \(\sigma\)-finite, and hence our analysis applies.

We are grateful to a referee for pointing this out.

For every random variable X and increasing functions \(g_1\) and \(g_2\), the random variables \(g_1(X)\) and \(g_2(X)\) are positively correlated (see, e.g., Thorisson 1995).

To see this, note that the definition of \(\psi\) implies \(d\log (1-F(v)) / dv = -1/(v-\psi (v))\).

See, for example, Stone (1980). If the density f is differentiable, then the optimal rate of convergence is \(m^{-1/3}\). Please refer to that paper for the exact definition of optimal convergence rates.

The optimal uniform convergence rate of density estimators is derived in Stone (1983).

To obtain a crude estimate, we can use Lemma 7 in the Appendix, which indicates that the expected total payment from the pivot mechanism is at most \(O\left( n^{1/4}\right)\). Therefore, the pivot mechanism runs a growing budget deficit if the cost grows faster than that rate.

Notice that, however, the cost cannot grow exactly at the \(\sqrt{n}\)-rate, because in that case we would need the adjustment term \(\alpha _n\) to also decrease at the \(\sqrt{n}\)-rate to balance the budget, leading to an inefficient allocation decision.

As we clarify in Appendix B, while the result in Hellwig (2003) are correct, the proof is slightly flawed. On the other hand, Kleinberg and Yuan (2013) only provide a heuristic (but informal) argument with the uniform distribution to explain why the optimal revenue grows at the \(\sqrt{n}\)-rate.

The nature of the assumption on the growth rate of \(c_n\) is essentially about the production technology and how the marginal cost decreases with the number of agents. See Roberts (1976) for a discussion on the relationship between the cost of a public good and the number of consumers.

The first five notations are standard. The expression \(d_n = O_\varepsilon (e_n)\) means that \(d_n\) is asymptotically bounded above by \(e_n\) divided by some (sufficiently small) power of n. The expression \(d_n = \omega _{\varepsilon }(e_n)\) means that \(d_n\) asymptotically dominates \(e_n\) divided by any power of n.

Armstrong M (1999) Price discrimination by a many-product firm. Rev Econ Stud 66(1):151–168. https://doi.org/10.1111/1467-937X.00082. https://arxiv.org/abs/https://academic.oup.com/restud/article-pdf/66/1/151/4682948/66-1-151.pdf

Azar PD, Micali S (2013) Parametric digital auctions. In: Proceedings of the 4th conference on innovations in theoretical computer science. Association for computing machinery, New York, ITCS ’13, pp 231-232. https://doi.org/10.1145/2422436.2422464

Bentkus V (2005) A lyapunov-type bound in \(r^d\). Theory Prob Appl 49(2):311–323. https://doi.org/10.1137/S0040585X97981123CrossRef

Bierbrauer FJ (2009) Optimal income taxation and public good provision with endogenous interest groups. J Public Econ Theory 11(2):311–342. https://doi.org/10.1111/j.1467-9779.2009.01412.x. https://arxiv.org/abs/https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-9779.2009.01412.x

Bierbrauer FJ (2014) Optimal tax and expenditure policy with aggregate uncertainty. Am Econ J Microecon 6(1):205–257. https://doi.org/10.1257/mic.6.1.205. https://www.aeaweb.org/articles?id=10.1257/mic.6.1.205

Bierbrauer FJ, Hellwig MF (2015) Public good provision in large economies. In: Working paper, Max Planck Institute for Research on Collective Goods

Bierbrauer FJ, Hellwig MF (2016) Robustly coalition-proof incentive mechanisms for public good provision are voting mechanisms and vice versa. Rev Econ Stud 83(4):1440–1464. https://doi.org/10.1093/restud/rdw015. https://arxiv.org/abs/https://academic.oup.com/restud/article-pdf/83/4/1440/6869959/rdw015.pdf

Börgers T (2015) An introduction to the theory of mechanism design. Oxford University Press, Oxford. https://doi.org/10.1093/acprof:oso/9780199734023.001.0001CrossRef

Brafman RI, Tennenholtz M (2000) An axiomatic treatment of three qualitative decision criteria. J ACM 47(3):452–482. https://doi.org/10.1145/337244.337251CrossRef

Brooks B, Du S (2021) Maxmin auction design with known expected values. https://econweb.ucsd.edu/~sodu/brooksdu_knownexpval.pdf

Carrasco V, Farinha Luz V, Kos N et al (2018) Optimal selling mechanisms under moment conditions. J Econ Theory 177:245–279. https://doi.org/10.1016/j.jet.2018.05.005. http://www.sciencedirect.com/science/article/pii/S0022053118301637

Clarke EH (1971) Multipart pricing of public goods. Public Choice 11(1):17–33. https://doi.org/10.1007/BF01726210CrossRef

Crémer J, McLean RP (1988) Full extraction of the surplus in bayesian and dominant strategy auctions. Econometrica 56(6):1247–1257. https://doi.org/10.2307/1913096CrossRef

Dhangwatnotai P, Roughgarden T, Yan Q (2015) Revenue maximization with a single sample. Games Econ Behav 91:318–333. https://doi.org/10.1016/j.geb.2014.03.011. http://www.sciencedirect.com/science/article/pii/S0899825614000645

Du S (2018) Robust mechanisms under common valuation. Econometrica 86(5):1569–1588. https://doi.org/10.3982/ECTA14993CrossRef

Feldman M, Immorlica N, Lucier B, et al (2016) The price of anarchy in large games. In: Proceedings of the forty-eighth annual ACM symposium on theory of computing. Association for computing machinery, New York, STOC ’16, pp 963–976. https://doi.org/10.1145/2897518.2897580

Gershkov A, Goeree JK, Kushnir A et al (2013) On the equivalence of bayesian and dominant strategy implementation. Econometrica 81(1):197–220CrossRef

Goldberg AV, Hartline JD, Karlin AR et al (2006) Competitive auctions. Games Econ Behav 55(2):242–269. https://doi.org/10.1016/j.geb.2006.02.003. http://www.sciencedirect.com/science/article/pii/S0899825606000303

Green J, Laffont JJ (1977) Révélation des préférences pour les biens publics: Caractérisation des mécanismes satisfaisants. Cahiers Séminaire d’Écon 19:83–103. http://www.jstor.org/stable/20075503

Groves T (1973) Incentives in teams. Econometrica 41(4):617–631. https://doi.org/10.2307/1914085CrossRef

Güth W, Hellwig M (1986) The private supply of a public good. J Econ 5(1):121–159. https://doi.org/10.1007/BF03051789. https://EconPapers.repec.org/RePEc:kap:jeczfn:v:5:y:1986:i:1:p:121-159

Hartline JD (2016) Mechanism design and approximation. http://jasonhartline.com/MDnA/, manuscript

Hellwig MF (2003) Public-good provision with many participants. Rev Econ Stud 70(3):589–614. https://doi.org/10.1111/1467-937X.00257CrossRef

Kleinberg R, Yuan Y (2013) On the ratio of revenue to welfare in single-parameter mechanism design. In: Proceedings of the fourteenth ACM conference on electronic commerce. Association for computing machinery, New York, EC ’13, pp 589-602. https://doi.org/10.1145/2492002.2482584

Kosenok G, Severinov S (2008) Individually rational, budget-balanced mechanisms and allocation of surplus. J Econ Theory 140(1):126–161. https://doi.org/10.1016/j.jet.2007.07.002. http://www.sciencedirect.com/science/article/pii/S0022053107001032

Kunimoto T, Zhang C (2021) On incentive compatible, individually rational public good provision mechanisms. Soc Choice Welf 57(2):431–468. https://doi.org/10.1007/s00355-021-01329-8CrossRef

Kuzmics C, Steg JH (2017) On public good provision mechanisms with dominant strategies and balanced budget. J Econ Theory 170:56–69. https://doi.org/10.1016/j.jet.2017.04.006. http://www.sciencedirect.com/science/article/pii/S0022053117300522

Mailath GJ, Postlewaite A (1990) Asymmetric information bargaining problems with many agents. Rev Econ Stud 57(3):351–367. https://doi.org/10.2307/2298018CrossRef

McLean R, Postlewaite A (2018) A very robust auction mechanism. In: Pier working paper archive, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania. https://EconPapers.repec.org/RePEc:pen:papers:18-001

Myerson RB, Satterthwaite MA (1983) Efficient mechanisms for bilateral trading. J Econ Theory 29(2):265–281. https://doi.org/10.1016/0022-0531(83)90048-0. http://www.sciencedirect.com/science/article/pii/0022053183900480

Neeman Z (2003) The effectiveness of english auctions. Games Econ Behav 43(2):214–238. https://doi.org/10.1016/S0899-8256(03)00005-8. http://www.sciencedirect.com/science/article/pii/S0899825603000058

Pınar MC, Kızılkale C (2017) Robust screening under ambiguity. Math Program 163(1–2):273–299. https://doi.org/10.1007/s10107-016-1063-xCrossRef

Roberts J (1976) The incentives for correct revelation of preferences and the number of consumers. J Public Econ 6(4):359–374. https://doi.org/10.1016/0047-2727(76)90048-7. http://www.sciencedirect.com/science/article/pii/0047272776900487

Roughgarden T, Talgam-Cohen I (2019) Approximately optimal mechanism design. Annu Rev Econ 11(1):355–381. https://doi.org/10.1146/annurev-economics-080218-025607CrossRef

Segal I (2003) Optimal pricing mechanisms with unknown demand. Am Econ Rev 93(3):509–529. https://doi.org/10.1257/000282803322156963. https://www.aeaweb.org/articles?id=10.1257/000282803322156963

Stone CJ (1980) Optimal rates of convergence for nonparametric estimators. Ann Stat 8(6):1348–1360. http://www.jstor.org/stable/2240947

Stone CJ (1983) Optimal uniform rate of convergence for nonparametric estimators of a density function or its derivatives11research was supported by nsf grant mcs 80-02732. In: Rizvi MH, Rustagi JS, Siegmund D (eds) Recent advances in statistics. Academic Press, Hoboken, pp 393–406, https://doi.org/10.1016/B978-0-12-589320-6.50022-8. https://www.sciencedirect.com/science/article/pii/B9780125893206500228

Swinkels JM (1999) Asymptotic efficiency for discriminatory private value auctions. Rev Econ Stud 66(3):509–528. https://doi.org/10.1111/1467-937X.00096CrossRef

Swinkels JM (2001) Efficiency of large private value auctions. Econometrica 69(1):37–68. https://doi.org/10.1111/1468-0262.00178CrossRef

Thorisson H (1995) Coupling methods in probability theory. Scand J Stat 22(2):159–182. http://www.jstor.org/stable/4616351

Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J Financ 16(1):8–37. https://doi.org/10.1111/j.1540-6261.1961.tb02789.xCrossRef

Wilson R (1987) Game-theoretic analyses of trading processes. Advances in economic theory. Fifth world congress. Cambridge University Press, Cambridge, pp 33–70CrossRef

Zhang W (2021) Robust bilateral trade mechanisms with known expectations. arXiv:2105.05427

Title: Strength in numbers: robust mechanisms for public goods with many agents
Authors: Jin Xi
Haitian Xie
Publication date: 07-06-2023
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 3/2023
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-023-01466-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2023

Social acceptability and the majoritarian compromise rule

How does exposure to COVID-19 influence health and income inequality aversion?

Constrained school choice: an experimental QRE analysis

Manipulation of moves in sequential contests

Leading by example in a public goods experiment with benefit heterogeneity

On the safety of group manipulation

Premium Partner