nach oben

Social Choice and Welfare

Erschienen in:

18.11.2020 | Original Paper

Markets for public decision-making

verfasst von: Nikhil Garg, Ashish Goel, Benjamin Plaut

Erschienen in: Social Choice and Welfare | Ausgabe 4/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A public decision-making problem consists of a set of issues, each with multiple possible alternatives, and a set of competing agents, each with a preferred alternative for each issue. We study adaptations of market economies to this setting, focusing on binary issues. Issues have prices, and each agent is endowed with artificial currency that she can use to purchase probability for her preferred alternatives (we allow randomized outcomes). We first show that when each issue has a single price that is common to all agents, market equilibria can be arbitrarily bad. This negative result motivates a different approach. We present a novel technique called pairwise issue expansion, which transforms any public decision-making instance into an equivalent Fisher market, the simplest type of private goods market. This is done by expanding each issue into many goods: one for each pair of agents who disagree on that issue. We show that the equilibrium prices in the constructed Fisher market yield a pairwise pricing equilibrium in the original public decision-making problem which maximizes Nash welfare. More broadly, pairwise issue expansion uncovers a powerful connection between the public decision-making and private goods settings; this immediately yields several interesting results about public decisions markets, and furthers the hope that we will be able to find a simple iterative voting protocol that leads to near-optimum decisions.

Vorheriger Artikel Choice resolutions

Nächster Artikel Some regrettable grading scale effects under different versions of evaluative voting

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

An alternative interpretation is that the issues themselves are divisible: for example, in the case of a city choosing how much money to a particular project, any amount of money is a valid outcome.

This can also be thought of as a private goods market with externalities: each agent’s utility depends not only on her own bundle, but also other agents’ bundles.

The concept of Nash welfare is due to Nash (1950) and Kaneko and Nakamura (1979).

These utility classes will be defined and discussed later.

A nested Leontief-Leontief function is still a Leontief function. Incidentally, this also implies that for a public decision making problem where agent utilities are Leontief, we get a Fisher market which has exactly the same form, i.e. with Leontief utilities.

In public goods, all agents have nonnegative utility for every good, and the question is how to allocate their money between the goods. In contrast, in public decision-making, agents have opposing preferred alternatives and are in direct competition on each issue. With a careful modification, Foley’s work does carry over to the public decision-making setting.

This discussion is thanks to Kamesh Munagala via private correspondence.

An outcome is Pareto optimal if there is no way to improve the utility of any agent without hurting another agent.

A similar result holds for indivisible goods Klaus and Miyagawa (2002).

In our model, divisibility and randomization are equivalent, but this is not always the case: for example, if there were a some sort of global budget constraint, randomization could lead to a non-viable deterministic outcome.

Although the entire supply is typically allocated, it is standard in the private goods literature to allow for outcomes where this does not occur, i.e. \(\sum _{i \in N} x_{ij} < 1\). This will be discussed in Sect. 2.2.

The weights \(w_{ij}\) have different interpretations for Leontief utilities vs other CES utilities. For example, if there is only a single good, the CES utility form reduces to \(w_{i1} x_{i1}\) and the Leontief utility form reduces to \(x_{i1}/w_{i1}\). When we say that taking the limit as \(\rho \rightarrow - \infty\) yields Leontief utilities, we mean that we obtain the form of Leontief utilities (i.e., a minimization over all the goods).

This is technically the “budget-weighted” Nash welfare, but we will omit “budget-weighted” throughout the paper.

This correspondence still holds under slightly weaker assumptions that our six assumptions Jain and Vazirani (2010).

Whenever we maximize over outcomes of a public decisions instance, i.e., \(\max _{\mathbf {z}} NW(\mathbf {z})\), we implicitly assume that only valid outcomes are considered, meaning that \(z^{j,0} + z^{j,1} \le 1\) for all \(j\in M\). The same is true when we maximize over outcomes of a private goods instance, and we adopt these conventions throughout the paper.

As in the Fisher market setting, agents are allowed to demand more than 1 unit of an issue if the cost is less than their budget. The interpretation of demanding more than unit probability is difficult, but the prices will ensure that this never occurs in equilibrium.

If some issue j is not sold completely and so \(z^{j,0} + z^{j,1} < 1\), one can think of the remaining \(1 - z^{j,0} - z^{j,1}\) being allocated to some third option that has no value for any agent.

Throughout most of the paper, we use \(\mathbf {z}\) to refer to the outcome of a public decisions instance and \(\mathbf {x}\) to refer to the outcome of a private goods instance. In this discussion, the welfare functions are the same for both public and private instances, so we will use \(\mathbf {z}\) to denote outcomes for both.

For completeness, we mention an additional mild condition required for this result: the polytope containing the set of feasible utilities of the two agents must be able to be described via a combinatorial LP.

With strictly concave utility functions, each agent’s demand at a given price is unique. With linear utilities, the demand set can be expressed as the set of goods that are equally desirable at the given prices. Also, we assume that agents are price-taking, meaning that they honestly report their demand given a set of prices, and do not anticipate how prices will change as a result of their actions.

functions that meet the five conditions from Sect. 2.

The outcome will not be well-defined for a list of private bundles not at equilibrium, since agents may have incompatible demands. This will not be important; we mention it only for completeness.

We assume that agents truthfully report their demands according to this definition: recall that we do not consider strategic behavior.

In the proof of Theorem 4.2, the definition of \(z^{j,1}\) was simply \(1 - z^{j,0}\). It is necessary to use \(\max (1 - z^{j,0}, 0)\) here instead: because this is an approximate equilibrium, it is possible that \(z^{j,0} > 1\), which would make \(1 - z^{j,0}\) negative.

Those works take great care to show conditions analogous to strong convexity or Lipschitz continuity of the gradient in the cases of interest.

It is well known that the primal objective function is strictly concave, and so \(p^*\), the optimal dual solution, is unique.

Ansolabehere S, Snyder J (2008) The end of inequality: one person. One vote and the transformation of American politics. W. W. Norton, New York

Arrow KJ, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica 22(3):265–290

Avigdor-Elgrabli N, Rabani Y, Yadgar G (2014) Convergence of tâtonnement in Fisher Markets. arXiv:1401.6637 [cs]

Bergstrom TC (1981) When does majority rule supply public goods efficiently? In: Steinar S (ed) Measurement in public choice. Palgrave Macmillan UK, London, pp 75–85

Bowen HR (1943) The interpretation of voting in the allocation of economic resources. Q J Econ 58(1):27

Brainard WC, Scarf HE (2005) How to compute equilibrium prices in 1891. Am J Econ Sociol 64(1):57–83

Briffault R (1993) Who rules at home?: One person/one vote and local governments. Univ Chicago Law Rev 60(2):339–424

Casella A, Votes S (2005) Games Econ Beh 51(2):391–419 (Special Issue in Honor of Richard D. McKelvey)

Chander P, Tulkens H (2006) A core-theoretic solution for the design of cooperative agreements on transfrontier pollution. In: Parkash C, Jacques D, Lovell CK, Jack M (eds) Public goods, environmental externalities and fiscal competition. Springer, Boston, pp 176–193

Chen Y, Pennock DM (2010) Designing markets for prediction. AI Magazine 31(4):42–52

Cheung YK, Cole R, Devanur N (2013) Tatonnement beyond gross substitutes?: gradient descent to the rescue. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing. ACM, pp 191–200

Conitzer V, Freeman R, Shah N (2017) Fair public decision making. In: Proceedings of the 2017 ACM Conference on Economics and Computation EC ’17. ACM, New York, pp 629–646

Danziger L (1976) A graphic representation of the Nash and Lindahl equilibria in an economy with a public good. J Public Econ 6(3):295–307

Dasgupta P, Hammond P, Maskin E (1979) The implementation of social choice rules: some general results on incentive compatibility. Rev Econ Stud 46(2):185

Debreu G (1959) Theory of value. Wiley, New York

Deeparnab C, Nikhil D, Vazirani Vijay V (2006) New results on rationality and strongly polynomial time solvability in Eisenberg-Gale markets. Springer, Berlin, pp 239–250

Eisenberg E (1961) Aggregation of utility functions. Manage Sci 7(4):337–350

Eisenberg E, Gale D (1959) Consensus of subjective probabilities: the Pari-Mutuel method. Ann Math Stat 30(1):165–168

Elliott M, Golub B (2013) A network approach to public goods. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC ’13. ACM, New York, pp 377–378

Fain B, Goel A, Munagala K (2016) The core of the participatory budgeting problem. Springer, Berlin, pp 384–399

Fisher I (1893) Mathematical investigations in the theory of value and prices. Bull Am Math Soc 2:204–211

Foley DK (1970) Lindahl’s solution and the core of an economy with public goods. Econometrica 38(1):66

Gabis MA (1978) One person. One vote. Northern Kentucky Law Rev 5:241

Garg D, Jain K, Talwar K, Vazirani VV (2005) A Primal-Dual Algorithm for computing Fisher equilibrium in the absence of gross substitutability property. Springer, Berlin, pp 24–33

Garg N, Kamble V, Goel A, Marn D, Munagala K (2017) Collaborative optimization for collective decision-making in continuous spaces. In: Proceedings of the 26th International Conference on World Wide Web, WWW ’17, pp 617–626

Garg N, Kamble V, Goel A, Marn D, Munagala K (2018) Iterative local voting for collective decision-making in continuous spaces. Jo Art Intell Res (To Appear)

Gersbach H (2004) Why one person one vote? Soc Choice Welfare 23(3):449–464

Goel A, Nazerzadeh H (2014) Price-based protocols for fair resource allocation: convergence time analysis and extension to leontief utilities. ACM Trans Algorithms 10(2):5:1–5:14

Goel A, Hulett R, Plaut B (2019) Markets beyond nash welfare for leontief utilities. In: Proceedings of the 15th Conference on Web and Internet Economics (WINE ’19)

Goel A, Krishnaswamy AK, Sakshuwong S, Aitamurto T (2016) Knapsack voting: voting mechanisms for participatory budgeting

Groves T, Ledyard J (1977) Optimal allocation of public goods: a solution to the “free rider” problem. Econometrica 45(4):783

Hands DW (1985) The structuralist view of economic theories: a rview essay: the case of general equilibrium in particular. Econ PhilosophyEcon Philos 1(2):303–335

Hayden GM (2003) The false promise of one person. One vote. Michigan Law Rev 102(2):213–267

Jiang L, Walrand J (2010) Scheduling and congestion control for wireless and processing networks. Synthesis Lectures Commun Netw 3(1):1–156

Kamal J, Vazirani Vijay V (2010) Eisenberg-Gale markets: algorithms and game-theoretic properties. Games Econ Behav 70(1):84–106

Kaneko M (1977) The ratio equilibrium and a voting game in a public goods economy. J Econ Theory 16(2):123–136

Kaneko M, Nakamura K (1979) The Nash social welfare function. Econometrica 47(2):423–35

Karabarbounis L (2011) One dollar, one vote*. Econ J 121(553):621–651

Klaus B, Miyagawa E (2002) Strategy-proofness, solidarity, and consistency for multiple assignment problems. Int J Game Theory 30(3):421–435

Lalley SP, Weyl EG (2014) Nash equilbria for quadratic voting. arXiv:1409.0264 [cs, math]

Mäler K (1985) Chapter 1 welfare economics and the environment. In: Handbook of natural resource and energy economics. Elsevier, Amsterdam, pp 3–60

Nash J (1950) The bargaining problem. Econometrica 18(2):155–162

Ray D, Vohra R (2001) Coalitional power and public goods. J Polit Econ 109(6):1355–1384

Riley J (1989) Justice under capitalism. Nomos 31:122–162

Satz D (2012) Why some things should not be for sale: the moral limits of markets. Oxford University Press, Oxford (reprint edition)

Schummer J (1996) Strategy-proofness versus efficiency on restricted domains of exchange economies. Soc Choice Welfare 14(1):47–56

Sen AK (1977) Rational fools: a critique of the behavioral foundations of economic theory. Philosophy Public Affairs 6(4):317–344

Shapley L, Shubik M (1977) Trade using one commodity as a means of payment. J Polit Econ 85(5):937–68

van den Nouweland A (2015) Lindahl and equilibrium. In: Individual and collective choice and social welfare. Springer, Berlin, pp 335–362

Varian H (1974) Equity, envy, and efficiency. J Econ Theory 9(1):63–91

Vazirani VV (2007) Combinatorial algorithms for market equilibria. In: Algorithmic game theory, pp 103–134

Walker M (1981) A simple incentive compatible scheme for attaining lindahl allocations. Econometrica 49(1):65

Walras L (1954) Elements of pure economics: or, the theory of social wealth. Translated by William Jaffé. Published for the American Economic Association and the Royal Economic Society

Titel: Markets for public decision-making
verfasst von: Nikhil Garg
Ashish Goel
Benjamin Plaut
Publikationsdatum: 18.11.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: Social Choice and Welfare / Ausgabe 4/2021
Print ISSN: 0176-1714
Elektronische ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-020-01298-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2021

Choice resolutions

No individual priorities and the Nash bargaining solution

Social Capital, Communication Channels and Opinion Formation

Some regrettable grading scale effects under different versions of evaluative voting

An axiomatic characterization of the Slater rule

Stabbed in the back? Mandated political representation and murders

Premium Partner