Markets for Public Decision-making
Nikhil Garg Ashish Goel Benjamin Plaut








Markets for Public Decision-making
    Nikhil Garg Ashish Goel Benjamin Plaut
    {nkgarg, ashishg, bplaut}@stanford.edu
 Stanford University
===============================================================







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.










§ INTRODUCTION


Fair and transparent public decision-making is a key element of a democratic society, but many public decisions are made by government officials behind closed doors. In this paper, we investigate mechanisms for large-scale public decision-making where citizens directly vote on a set of issues at the same time, focusing on the case where each issue has exactly two alternatives. In particular, we examine connections to private goods allocation (i.e., standard resource allocation). One can think of each issue that is under consideration as a “good", and public decision-making as “allocating" the good to one of the alternatives. We allow randomized outcomes, where the outcome can put nonzero probability on multiple alternatives: this is analogous to divisible private goods, where a good can be split among multiple agents[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.]. The fundamental difference is that in private goods allocation, each agent's utility depends only on the bundle of goods she receives; in public decision-making, the group makes a single decision that affects all agents. 

Market economies are one of the longest-studied areas in the distributions of private goods. The simplest market model is that of a Fisher market (see <cit.> for a modern exposition), which consists of a set of available goods and a set of agents with money they wish to spend. It is typically assumed that the agents have no value for the money itself, and wish to spend their entire budget to acquire goods that they desire. Each good has a price which determines how much money an agent must spend to purchase one unit of the good. The goods are divisible, meaning that an agent can purchase any fraction of a good. A market equilibrium assigns a price to each good such that every agent purchases their favorite bundle that is affordable under the prices, and that the demand meets the supply. Under some mild conditions (elaborated on in Section <ref>), a market equilibrium always exists <cit.>.




 §.§ Our contribution


We consider adaptations of markets to the public decision-making setting. Many democracy theorists believe that it is unethical (eg. see <cit.>) and many democratic countries stipulate that it is illegal to allow citizens to purchase political influence with actual money. Instead, we think of each agent being endowed with the same amount of “artificial currency" that is useful only for voting on these issues; thus our approach to public decision markets is consistent with the spirit of “one person one vote". Prices are assigned to issues, and agents can use their artificial currency to “purchase" probability for their preferred alternatives on the issues they most value[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.].

Markets have the desirable property that each agent can choose how to allocate her money across goods, based on their relative values to her. In the context of large-scale public decision-making, this allows agents to express their relative weights for the different issues in a fine-grained way. This is in contrast to approaches like asking agents to rank the issues by importance, which are more limited in expressiveness. Markets have the additional property that the equilibria are “supported" by prices: prices provide a sort of certificate of fairness, in that each agent can verify that she is spending her budget in the best way possible.

The simplest pricing model assigns a single price to each issue, and all agents are subject to the same set of prices. We refer to this as “per-issue pricing", or just “issue pricing". In the private goods setting, per-good pricing is sufficient to yield a market equilibrium with optimal Nash welfare: the product of agent utilities[The concept of Nash welfare is due to <cit.> and <cit.>.]. Unfortunately, we show in Section <ref> that issue pricing in the public decisions setting can result in very poor equilibria: the Nash welfare of the equilibrium may be a factor of O(n) worse than optimal, where n is the number of agents. The same instance shows that the utilitarian welfare (the sum of agent utilities) and egalitarian welfare (the minimum agent utility) may both be a factor of O(n) worse than optimal as well.



  §.§.§ Pairwise issue expansion.


This negative result motivates a more complex market model. Our main contribution is a reduction which transforms any public decision-making instance into a private goods Fisher market instance that is “equivalent" in a strong sense. For each issue, we construct a good for each pair of agents who disagree on that issue. The outcome on that issue can be thought of as the result of pairwise negotiations between each pair of agents who disagree. We refer to this reduction as pairwise issue expansion. The equilibrium prices of the constructed Fisher market yield a “pairwise pricing equilibrium" in the original public decisions instance. We show that the resulting pairwise pricing equilibrium maximizes Nash welfare in the public decisions instance.


Furthermore, pairwise issue expansion allows us to directly import results for Fisher markets to the public decisions setting. If the utilities in the public decisions instance are in class  (say, linear utilities), the utilities in the constructed Fisher market will be nested -Leontief (for example, nested linear-Leontief)[These utility classes will be defined and discussed later.]. This means that any result which works for Fisher markets with nested -Leontief utilities can be imported to public decisions instances with utilities in class . The main Fisher market results we consider are: (1) a strongly polynomial-time algorithm for finding a Fisher market equilibrium with two agents and any utility functions <cit.>, (2) a strongly polynomial-time algorithm for finding a Fisher market equilibrium for Leontief utilities with weights in {0,1} <cit.>, (3) a polynomial-time algorithm for a Fisher market with Leontief utilities which yields a O(log n) approximation simultaneously for all canonical welfare functions (i.e. Nash welfare, utilitarian welfare, egalitarian welfare, etc) <cit.>, and (4) a discrete-time process for finding the Fisher market equilibrium for nested CES-Leontief utilities that converges in polynomial-time <cit.>. Thus pairwise issue expansion yields the following results for the public decision-making setting:




  * A strongly polynomial-time algorithm for finding a public decisions market equilibrium with two agents and any utility functions.


  * A strongly polynomial-time algorithm for finding a public decisions market equilibrium for Leontief utilities with weights in {0,1}.


  * A polynomial-time algorithm for a public decisions instance with Leontief utilities which yields a O(log n) approximation simultaneously for all canonical welfare functions (i.e. Nash welfare, utilitarian welfare, egalitarian welfare, etc).


  * A discrete-time process for finding a public decisions market equilibrium for CES utilities that converges in polynomial-time.



These Fisher market results yield the analogous results for public decisions instances for two agents with any utilities, Leontief utilities with weights in {0,1}[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.], any Leontief utilities, and CES utilities, respectively. We also discuss public decisions in more depth, and show how our reduction can be used to implement a process where agents only interact with the public decisions instance, and never see the constructed Fisher market.





More broadly, our work uncovers a powerful connection between private goods allocation and public decision-making. We hope that pairwise issue expansion will have applications in future work as well. One particularly promising direction is to design an iterative local voting scheme akin to prediction markets (see <cit.>), where agents (or pairs of agents) arrive sequentially and move the current decision vector in their preferred direction subject to offered issue prices. Our proof of the existence of a simple for public decision markets offers hope that such a scheme may be possible.








 §.§ Related work


Equilibrium theory has a long history in economics <cit.>. More recently, this topic has garnered significant interest in the computer science community as well (see <cit.> for an algorithmic introduction).



  
Foley's work on Lindahl Equilibria The market concept most directly relevant to our public decision markets is that of Lindahl equilibria, developed by Foley <cit.>, who showed that personalized prices (i.e., each agent may be assigned a different price for each good with no restrictions) can support any Pareto optimal solution in the context of public goods[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.]. Our work can be thought of as improving upon Foley's work to get much stronger properties for the special case of public decision-making. We obtain these stronger properties using a more sophisticated reduction, one which is in fact weaker in the sense that there is a correspondence between the public decisions market and the private market only at equilibrium. Our reduction explicitly relies on the fact that agents are in opposition on each issue in the public decisions setting, which is not the case in the public goods setting.




The stronger properties we obtain are as follows. First, Foley's work <cit.> allows arbitrary personalized prices, whereas we only require pairwise prices: for each issue, there is a price for each pair of agents who disagree on that issue. Our Fisher market can be thought of as negotiating independently with each person that disagrees with you through a normal market; we are not aware of any such simple interpretation that follows from Foley's very general work. Second, in our private goods reduction, a feasible public goods decision (where each agent shares the same societal decision) emerges naturally: we leverage properties of nested-Leontief utilities and the Nash welfare objective function to implicitly represent the feasibility constraints, which allows us to obtain the correspondence only at equilibrium. In contrast, Foley adds cone constraints to a private goods market to explicitly enforce the feasibility constraints of the public decision-making problem; these constraints have no natural real-world analogue. Third, we reduce the public goods setting to a Fisher market, arguably the simplest possible and most-studied private goods market. Because of this, our reduction allows us to lift many Fisher market equilibrium results to the public decision-making setting. In particular, our reduction allows us to obtain a for public decision-making, even though intermediate steps in the are in a regime where the public and private markets are not in direct correspondence. It is unclear whether this is possible with Foley's construction. We discuss this in technical detail and elaborate on how our work relates to Lindahl equilibria in Appendix <ref>.



  
Tâtonnement As mentioned above, one of our results is a for public decision-making. A is an iterative process which presents agents with a set of prices, asks what they would buy given those prices, and updates the price of each good based on the aggregate demand of each good. A -like process for computing the maximum Nash welfare outcome in participatory budgeting (see e.g. <cit.> for more on PB) was recently given by Fain et al. <cit.>. They showed that the maximum Nash welfare outcome can be computed by using a stochastic gradient descent style algorithm. Their algorithm iteratively elicits agents' demands using a process very similar to quadratic voting <cit.> and updates the current solution accordingly. While this is similar to a , there is one crucial difference. A true (such as the one we present) allows the agents to directly change the current point: the price of each good is updated by a fixed rule based on the aggregate demand of that good. In contrast, the algorithm of <cit.> moves to a point that is different from the one elicited by the quadratic voting. Also, their result also holds only for linear utilities[This discussion is thanks to Kamesh Munagala via private correspondence.].

A , with a similar elicitation scheme, has been shown to work in practice in the participatory budgeting setting <cit.>. In those works, a new budget is directly elicited from voters, and the mechanism works for ℓ_p normed cost functions. However, 
their mechanism finds a total welfare maximizing point as opposed to a Nash welfare maximizing outcome. One direction for future work is to adapt the from this work into such an implementable mechanism with a large number of voters.




  
Inefficiencies of pricing schemes Another relevant paper from the economics literature is <cit.>, which shows that per-good pricing can lead to inefficiency for public goods. Their examples do not provide bounds on how much worse per-good pricing can be: in contrast, we show that for linear utilities, issue pricing can be a factor of O(n) worse than optimal. Also, we note that it is easy to adapt the examples in Section 3 to show that two other popular market-based approaches, namely Quadratic Voting <cit.> and Trading Post Prices <cit.>, also do not result in good equilibria with issue pricing in our public decision market setting.

Not sure if we should include the following paragraph
Lets remove

Much of the public decision-making literature focuses on the single-issue ordinal preferences model, where each agent reports only a reports a ranking of the alternatives, from most preferred to least preferred (for a single issue). Our model differs in that there may be many issues, and that agents have cardinal utility functions, as opposed to just ordinal preferences. Although this makes the problem more difficult in some ways, it allows more expressiveness in the mechanisms. In particular, a market-based mechanism allows agents to express the relative importance of different issues to them based on how they choose to allocate their money[For example, imagine co-authors who disagree on multiple issues during the revision process of an academic paper. Using a market mechanism, each co-author can allocate her money on the issues that matter most to her.].




  
Strategic agents A key property in mechanism design is strategy-proofness (or lack thereof). A mechanism is strategy-proof if even a selfish agent would always honestly report her preferences. Most relevant to us is <cit.>, which shows that even for two agents with linear utilities over divisible goods, any mechanism which is both strategy-proof and Pareto optimal[An outcome is Pareto optimal if there is no way to improve the utility of any agent without hurting another agent.] is dictatorial, meaning that one agent receives all of the resources[A similar result holds for indivisible goods <cit.>.]. Our binary-issue public decisions setting generalizes the two agent private goods setting, and hence we immediately inherit this impossibility result: any mechanism which is both strategy-proof and Pareto optimal is dictatorial. A dictatorial solution is clearly not desirable, and we would like our outcomes to be Pareto optimal, so we assume throughout this paper that agents honestly report their preferences and do not address the issue of strategic behavior.  Other incentive compatibility results for implementation of general classes of social choice functions are discussed in <cit.>. 

We note that several works extending Foley relax the assumption that agents report their preferences truthfully, by building voting games in which the equilibrium is one in which truthful reporting is incentive compatible for each agent <cit.>. Most notably, Groves and Ledyard <cit.> construct an allocation-taxation scheme – using message passing – for a market with both private goods and public commodities, such that the equilibrium behavior results in a Pareto optimal solution. As in our work, however, their mechanism is still susceptible to a manipulation in which a consumer considers how future prices and the behavior of others are affected by her current decisions.







  
Other voting schemes, and one person one vote Other works also propose alternate voting schemes for multiple issues. Storable Votes <cit.> allows members of a committee to store votes for future meetings so as to spend their votes on issues that matter most to them; the work proves welfare gains in the case of two voters but does not give a principled way to balance the relative importance or cost of different issues, as we do here. In <cit.>, the authors study adaptations of private goods fairness notions (such as proportionality) to the public decision-making context when randomized outcomes are not allowed. In contrast, we allow fractional solutions (i.e. randomized outcomes) and exactly maximize Nash welfare. 

Such works, especially this one, may seem to violate the principle of One Person One Vote <cit.>. In particular, as we propose individual prices, a given issue may “cost” more for one voter than for another. However, as discussed below, these prices are generated in a principled manner – for each issue, there is a single price for each pair of voters who disagree on the issue. Furthermore, we note that, at the onset, each voter is allocated the same “budget” through which to vote on issues.



  
Other works in market equilibria for public goods Finally, we note that many more strands of literature, too many to detail here, discuss and extend the work of Foley <cit.> and more generally the idea of equilibria for the funding of public goods. This work includes both stronger results in a more specific model, as this work, and computational hardness analysis of equilibria theory in general <cit.>. To our knowledge, our public decision-making setting has not been studied as a special case of such public goods markets.

In <cit.> and <cit.>, the authors ask what happens when the decision to fund a single public good is simply made through a majority vote; in particular, they study under what conditions of voter preferences for the public good and distribution of tax shares of each voter is the funding of the good Pareto optimal. They find that majority vote can fall short of optimal if income is asymmetrically distributed. In Section <ref>, we show that the case with multiple public decisions is far worse: a generalization of majority vote – where each issue has a price – leads to highly suboptimal outcomes, even when everyone is endowed with the same income. 

Another strand aims to study the implications of relationships between individuals. For example, in <cit.>, agents are allowed to form coalitions through binding contracts, resulting in inefficiencies. In <cit.>,  there are people who can “produce” a given public good and those who “benefit” from that good. These relationships can be represented by a network in a certain way, and the Lindahl outcomes correspond to a solution characterized by the eigenvector centralities of each node. In this work, voters who agree on a given issue end up on the same side of a bipartite graph, resulting in them purchasing the same probability for that issue.

The assumptions and philosophical underpinnings of equilibria theory are also well-studied, as are applications to other fields.
Sen <cit.> challenges the notion that people have consistent preferences that can be elicited. In particular, he posits that people have “commitments” to a particular social group of other people, whose welfare they care about. We note that the assumption of a utility function is nevertheless common, though it is important to be aware of the limitations of such behavioral abstractions. In <cit.>, competitive equilibria is connected to the idea that in capitalism people are given fruits commensurate to their labor, as part of a discussion of the relationship of notions of justice and capitalism. General equilibrium theories are even connected to Structuralism within the philosophy of science <cit.>. One prominent application of the economics of public goods has been to study environmental (non-)cooperation <cit.>. Our work extends such applications by connecting market equilibria ideas to voting on different issues in a fair and efficient way, as discussed above.


The rest of the paper is organized as follows. Section <ref> formally defines the models of private goods allocation, public decision-making, and Fisher markets. Section <ref> shows that issue pricing can result in (very) poor equilibria for public decisions markets. Section <ref> presents the concept of pairwise issue expansion, and shows how this can be used to obtain optimal equilibria, as well as other properties. Section <ref> gives examples of Fisher market results that we can import to the public decisions setting using our reduction. Section <ref> focuses on a particular such result: . Finally, Appendix <ref> discusses the connection to <cit.> and Lindahl equilibria in more depth. Proofs are also deferred to the appendix. 
















§ MODEL


We first introduce general notation that applies to both private goods allocation and public decision-making. As much as possible, we intentionally use the same notation for the private and public settings, as one of our primary contributions is to highlight the connections between these. We then discuss our assumptions on utility functions. Finally we discuss aspects specific to private goods and specific to public decision-making.

Let [k] denote the set {1,2 , …, k}. A private goods instance consists of a set of agents N = [n] and a set of goods M = [m]; a public decisions instance consists of a set of agents N = [n] and a set of issues M = [m]. We will typically use i and k to denote agents, and j and ℓ to denote goods/issues. We assume that issues are binary, meaning that each issue j has two alternatives: 0 and 1. Each agent i ∈ N has a preferred alternative for each issue j, denoted by a_ij, which they truthfully report.

We assume that goods/issues are divisible, meaning that a single good/issue can split among multiple agents. In a public decision instance, divisibility can be interpreted as randomization over alternatives. An outcome of a private goods instance is an allocation ∈ [0,1]^m× n, where x_i ∈ [0,1]^m is the bundle given to agent i, and x_ij∈ [0,1] is the fraction of good j given to agent i. An allocation cannot allocate more than the available supply[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. ∑_i ∈ N x_ij < 1. This will be discussed in Section <ref>.]:  is valid only if ∑_i ∈ N x_ij≤ 1 for all j∈ M. The outcome of a public decisions instance is denoted by = (z^1, …, z^m) ∈ [0,1]^m× 2, where z^j = (z^j,0, z^j,1) ∈ [0,1]^2, and z^j,a∈ [0,1] is the probability put on alternative a for issue j. An outcome  is valid only if ∑_a ∈{0,1} z^j,a≤ 1 for all j∈ M. 



 


 §.§ Utility functions


In a private goods instance, we use u_i() ∈ℝ to denote i's utility for allocation ; in a public decisions instance,  we use u_i() ∈ to denote i's utility for outcome . In a private goods instance, it is assumed that an agent's utility depends on only the bundle she receives: u_i() = u_i(x_i). In a public decisions instance, agents do not receive separate bundles: instead, the group makes a single decision that affects all agents. We will assume that agents only have utility for their preferred alternative: this will let us standardize notation as follows. For a public decisions outcome , let x_ij() = z^j, a_ij for all  i∈ N and j ∈ M (we will typically write x_ij() = x_ij for brevity). Then we can define agent i's public bundle as x_i =(x_i1, …, x_im). An agent's public bundle represents the fraction of the public decision allocated to her preferred alternative, and so we have u_i() = u_i(x_i) in a public decisions instance as well. 

Throughout the paper, we make the following standard assumptions on each agent's utility function u_i:


	
  * Continuous: u_i: [0,1]^m→ℝ_≥ 0 is a continuous function.
	
  * Normalized: u_i(0,0,...0) = 0.
		
  * Non-constant: There exists a bundle x_i where u_i(x_i) > 0.
	
  * Monotone: For any bundles x_i and x'_i where x_ij≥ x'_ij for all j, u_i(x_i) ≥ u_i(x'_i).
	
  * Concave: For any bundles x_i and x'_i and constant λ∈ [0,1], we have u_i(λ x_i + (1 - λ) x'_i) ≥λ u_i( x_i) + (1-λ)u_i( x'_i).
	
  * Homogeneous of degree 1: For any bundles x_i and x'_i and constant λ≥ 0 where x_ij = λ x'_ij for all j, u_i(x_i) = λ u_i(x'_i).


The first five are standard assumptions in the market literature. The last is less ubiquitous, but still common: in particular, the vast majority of the popular subclasses of utility functions satisfy this assumption. For example, it is often assumed in real-world applications that utility functions are linear, meaning that

    u_i(x_i) = ∑_j ∈ M w_ij x_ij

where w_ij≥ 0 is the weight agent i has for good j. Another important class is Leontief functions, where

    u_i(x_i) = min_j ∈ M: w_ij 0 x_ij/w_ij

Linear utilities imply that goods are independent, whereas Leontief utilities represent perfect complements: goods that only have value in combination. For Leontief utilities, w_ij is the relative proportion agent i needs of good j.

Both Linear and Leontief utilities are generalized by the class of constant elasticity of substitution (CES) utilities, where u_i(x_i) = (∑_j ∈ M w_ij^ρ x_ij^ρ)^1/ρ for some constant ρ∈ (-∞, 0) ∪ (0, 1]. Linear utilities are obtained by setting ρ = 1, and taking the limit as ρ approaches -∞ yields Leontief utilities. Taking the limit as ρ approaches 0 gives Cobb-Douglas utility functions, which have the form u_i(x_i) = (∏_j ∈ M x_ij^w_ij)^1/∑_j ∈ M w_ij[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 ρ→ - ∞ yields Leontief utilities, we mean that we obtain the form of Leontief utilities (i.e., a minimization over all the goods).].

While many of our results hold for any utility functions satisfying our six assumptions, some hold only for particular subclasses; we will make it clear when this is the case.




 §.§ Private goods & Fisher markets




In this work, we primarily consider private goods instances that are Fisher markets. A Fisher market <cit.> is a private goods instance (N, M) where each agent i also has a budget B_i ≥ 0. Each agent's budget can be interpreted as her relative importance. We would typically expect all agents to have the same importance, especially in public decision-making, but allow for the possibility of different budgets for completeness.

For prices p = (p_1, …, p_m) ∈ℝ_≥ 0^m, bundle x_i is affordable for agent i if x_i · p = ∑_j∈ M x_ijp_j ≤ B_i. agent i's demand set for prices p is

    D_i(p) = _x_i ∈^m_≥ 0: x_i · p ≤ B_i u_i(x_i)

i.e., the set of her favorite affordable bundles. A market equilibrium (ME) (, p) is an allocation  and prices p where

	
  * Each agent receives a bundle in her demand set: x_i ∈ D_i(p).
	
  * The market clears: for all j, ∑_i ∈ N x_ij≤ 1. Also, if p_j > 0, then ∑_i ∈ N x_ij = 1.

The most natural case is when all agents have the same budget, in which case the ME is also called the competitive equilibrium from equal incomes <cit.>.

Condition <ref> states that the demand never exceeds the supply, and that any good whose supply is not fully exhausted must have price zero. This implies that agents have no utility for the leftover goods: otherwise they would simply buy more with no additional cost. Note that agents can demand more of a good than the available supply if the cost is less than their budget. It is the role of prices at equilibrium to ensure that demand does not exceed supply. 

Under the first five assumptions on utility functions described in Section <ref>, a market equilibrium is guaranteed to exist for any Fisher market instance <cit.>. With the addition of the sixth assumption (homogeneity of degree 1), the equilibrium allocations are exactly the allocations maximizing the Nash welfare[This is technically the “budget-weighted" Nash welfare, but we will omit “budget-weighted" throughout the paper.]:

    NW() = (∏_i ∈ N u_i(x_i)^B_i)^1/

where  = ∑_i ∈ N B_i. Maximum Nash welfare allocations can be computed in polynomial time by the celebrated Eisenberg-Gale (EG) convex program <cit.>[This correspondence still holds under slightly weaker assumptions that our six assumptions <cit.>.]. The Nash welfare has been lauded as a compromise between fairness and efficiency, and it will be the primary objective function we seek to maximize.





 §.§ Public decisions


As in the private markets case, the maximum Nash welfare outcome can be found via a convex program:

    max_∈ [0,1]^m×2(∏_i ∈ N u_i()^B_i)^1/   
    s.t.    z^j,0 + z^j,1≤ 1  ∀ j ∈ M

 
 The solution to this convex program can be found in polynomial time. This program is very different than the EG program; however, we will show via our reduction that these programs become identical under a transformation of utility functions and issue space.

Furthermore, even without any knowledge of utility functions, a 1/2 approximation of this program emerges. Because issues are binary, we can very easily guarantee each agent half of her maximum possible utility simply by putting equal probability on each alternative, i.e., z^j,0 = z^j,1 = 1/2. It follows from concavity and u_i(0,0,...,0) = 0 that this also achieves 1/2 of the maximum possible Nash welfare.


Let Γ be a public decisions instance (N,M) with agent budgets B = (B_1...B_n), and let  be the outcome where z^j,0 = z^j,1 = 1/2 for all j ∈ M. Then max_𝐳' NW(𝐳')NW()≤ 2[Whenever we maximize over outcomes of a public decisions instance, i.e., max_ NW(), we implicitly assume that only valid outcomes are considered, meaning that z^j,0 + z^j,1≤ 1 for all j∈ M. The same is true when we maximize over outcomes of a private goods instance, and we adopt these conventions throughout the paper.].















In light of this, we would expect any reasonable mechanism for public decision-making to do no worse than this (in terms of Nash welfare), and hopefully do substantially better. Unfortunately, we show in the next section that the natural adaption of Fisher markets to the public decisions setting does no better than this for several important classes of utility functions. Even worse, in the case of linear utilities – the most important class of utilities in practice – the Nash welfare can be a factor of O(n) worse than optimal.







§ INEFFICIENCY OF PUBLIC DECISIONS MARKETS WITH ISSUE PRICING


In a Fisher market, each good is assigned a single price which is common to all agents: thus all agents are treated the same, which is desirable for fairness. This section shows that in the public decisions setting, setting a single price for each issue (issue pricing) can result in very poor equilibria. Although we primarily consider Nash welfare in this paper, the same family of instances will show that the utilitarian welfare (sum of agent utilities) and egalitarian welfare (the minimum agent utility) can also be much worse than optimal.

A public decisions market (PDM) consists of a public decisions instance (N, M) along with agent budgets B = (B_1… B_n). This definition is independent of the pricing scheme: we  use the term “PDM" to describe all notions of markets for the public decisions setting. This section uses the following scheme: each issue has a price, each agent uses her budget to purchase probability for her preferred alternatives, and the total probability placed on an alternative is the sum over agents of the probability purchased for that alternative. 

Given per-issue prices p ∈ℝ_≥ 0^m, a private bundle y_i ∈ℝ_≥ 0^m is affordable if y_i · p ≤ B_i. Throughout the paper, we will use y_i to refer to i's private bundle, and x_i to refer to i's public bundle. This distinction only matters in the public decisions setting: we use y_i and x_i interchangeably in the private goods setting.

In this section, for private bundles = (y_1...y_n), the corresponding outcome = (z^1...z^m) ∈ [0,1]^m× 2 is

    z^j,a = ∑_i ∈ N: a_ij = a y_ij

The above definition of  as a function of  is specific to the issue pricing scheme. The different pricing scheme discussed in Section <ref> will define  differently.

In a Fisher market, an agent's demand set contains the bundles which maximize her utility subject to being affordable. In a PDM with issue pricing, an agent's utility depends not only on her own bundle, but also on other agent's bundles. Thus if we want to define an agent's demand set as the bundles which maximize her utility subject to being affordable, the demand set must depend not only on the prices, but also on the private bundles of other agents. With this in mind, we define the demand set by

    D_i(p, y_-i) = _y_i ∈^m_≥ 0: y_i · p ≤ B_i u_i(y_-i, y_i)

where y_-i is the list of private bundles other than that of agent i, and with slight abuse of types, u_i(y_-i, y_i) is agent i's utility for the outcome when i purchases private bundle y_i and the other agents purchase private bundles y_-i[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.].

An issue-pricing market equilibrium (IME) (, p) is a list of private bundles  and issue prices p ∈ℝ_≥ 0^m where


  * Each agent receives a private bundle in her demand set: y_i ∈ D_i(p, y_-i).

  * The market clears: for all j, ∑_i ∈ N y_ij≤ 1. Also, if p_j > 0, then ∑_i ∈ N y_ij = 1.

By the same reasoning as in the private setting, whenever an issue is not sold completely, agents have no utility for the unsold fraction of the issue[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.].

In general it is not known whether every PDM admits an IME. However, for several important utility classes, we give an instance where an IME does exist, but where every IME has poor Nash welfare.




 §.§ Linear utilities

We first show that for linear utilities, an IME always exists. Furthermore, the set of IMEs is identical to the set of private goods MEs that would be obtained if the input were instead treated as a Fisher market (i.e., if each agent's utility only depended on her private bundle).

To see this, we can write agent i's utility for private bundles  as

    u_i() = ∑_j ∈ M w_ij∑_k ∈ N:
     a_kj = a_ij y_kj = 
    ∑_j ∈ M w_ij y_ij + ∑_j ∈ M w_ij∑_k ∈ N\{i}:
     a_kj = a_ij y_kj

Agent i cannot affect the actions of other agents, and so has no control over the second term. Thus agent i maximizes her utility by maximizing the first term, ∑_j ∈ Mw_ijy_ij, which is exactly the utility function of an agent in a Fisher market. This is expressed formally by Theorem <ref>, whose proof appears in Appendix <ref>.

theoremlinPerIssueExist

For a PDM (N,M, B) with linear utilities given by weights w_ij≥ 0, for every list of private bundles  and list of prices p, (, p) is an IME if and only (, p) is a ME for the Fisher market (N,M,B) with linear utilities given by the same weights.



We now define the family of instances that exhibit poor equilibria in the issue pricing model. For any integer n≥ 2 and real number w ≥ 0, let Φ(n, w) be the PDM defined by n = m, w_ii = w for all i, w_ij = 1 for all j ≠ i, a_ii = 0, a_ij = 1 for all j≠ i, and B_i = 1 for all i. In words, on each issue i, agent i is alone on one side of the issue, and the other n-1 agents are on the opposite side. Each agent i has weight w for issue i, and weight 1 for every other issue.

Our next theorem shows that for linear utilities, the Nash welfare of the IME can be a linear factor worse than optimal. This is especially dreadful in light of how easy it is to achieve half of the optimal Nash welfare via Proposition <ref>.

theoremlinPerIssueLower

For any ϵ > 0, Φ(n, 1+ϵ) with linear utilities has a unique equilibrium (, p), where

    max_𝐳' NW(𝐳')/NW()≥n-1/1+ϵ



The proof is in Appendix Section <ref>, but we give some intuition here. We observe that an agent's demand set in a Fisher market always maximizes her “bang-per-buck" ratio: w_ij/p_j. To see this, suppose agent i spends some money on a good that does not maximize her bang-per-buck ratio: she could instead spend the same amount of money to get strictly more utility by spending it on a good with maximum bang-per-buck. By Theorem <ref>, this property carries over to the IME.

By symmetry, every issue will have the same price. Since w_ii > w_ij for all i and for all j≠ i, agent i's bang-per-buck ratio is maximized only by good i. Thus each agent i spends all of her budget on good i. This leads to the outcome where y_ii = 1 for all i, and y_ij = 0 for all j ≠ i. Thus z^j,0 = 1 for all j ∈ M. The utility of each agent for this outcome 1+ϵ, so the Nash welfare is also 1+ϵ. But in the outcome where z^j,1 = 1, for all j, each agent has utility n-1, so the Nash welfare is n-1. This yields the desired bound of (n-1)/(1+ϵ).

If we used w_ii = w_ij = 1 for all i,j, the outcome where z^j,0 = 1 would still be an IME. However, there would now be many more IMEs, including ones with optimal Nash welfare. By setting w_ii = 1+ϵ instead of w_ii = 1, we can make the outcome where x_ii = 1 for all i the unique equilibrium. This same issue is not present for Cobb-Douglas and CES utilities with ρ∈ (-∞, 0) ∪ (0, 1), which we examine in the next section.




 §.§ Other utilities

We briefly mention two results we have for other classes of utility functions. Using the same Φ construction, Theorems <ref> and <ref> state that the Nash welfare of an IME cannot be much better than 1/2 for Cobb-Douglas utilities and CES utilities, respectively. The formal proofs of Theorems <ref> and <ref> appear in Appendix <ref>. 









theoremcdLower

For any IME (, p) of Φ(n, 1) with Cobb-Douglas utilities,

    max_𝐳' NW(𝐳')/NW()≥2 - 2/n/(n-1)^1/n





theoremcesLower

For any IME (, p) of Φ(n, 1) with CES utilities for parameter ρ∈ (-∞, 0) ∪ (0, 1), 

    max_𝐳' NW(𝐳')/NW()≥ 2(1 - 1/n)^1/ρ



As the number of agents approaches infinity, the bounds in Theorems <ref> and <ref> approach 2. This means that for those classes of utility functions, the issue pricing market model cannot be guaranteed to do better than simply picking the midpoint on every issue (Proposition <ref>). The situation is even worse for linear utilities, where the Nash welfare of an IME can be arbitrarily worse than the optimal Nash welfare. 

One may wonder why Cobb-Douglas and CES utilities with ρ∈ (-∞, 0) ∪ (0, 1) do not fail as badly as linear utilities on this family of instances. On a high level, the reason is that both Cobb-Douglas and CES utilities exhibit diminishing returns: the more one buys of a particular good, the less value it adds. This leads to agents splitting their money across multiple goods, regardless of their weights on the individual goods. As a result, small changes in agents' weights end up not affecting their purchases too much. In contrast, for linear utilities, an agent might spend her entire budget on a single good: in fact, if there is a unique good which maximizes her bang-per-buck, she must spend her entire budget on that good. This is exactly the property we use in our inefficiency example, where the fact the w_ii = 1 + ϵ > w_ij for j ≠ i causes agent i to spend her entire budget on good i.

These negative results motivate a more complex market model, which we present in the next section.















§ PAIRWISE ISSUE EXPANSION AND PAIRWISE PRICING


In this section, we describe a more complex model of a public decisions market, which relies on pairwise pricing: for each issue, there will be a price for each pair of agents who disagree on that issue. We then present our main result: a reduction from any PDM to an equivalent Fisher market. This reduction, which we call pairwise issue expansion, can be used to construct a pairwise pricing equilibrium that maximizes the Nash welfare.

The section is organized as follows. Section <ref> introduces pairwise issue expansion and gives an informal argument for correctness. Section <ref> gives some additional notation and setup, and states our theorems. The formal proofs of correctness are somewhat technical and appear only in the appendix. Finally, Section <ref> discusses some Fisher market results that this reduction allows us to immediately lift to the public decisions setting.







 §.§ Pairwise issue expansion

For any PDM Γ, we construct a Fisher market R(Γ) as follows. The set of agents N = {1...n} and their budgets B_1...B_n will be the same. Every issue j ∈ M will become O(n^2) goods in R(Γ). Specifically, for every issue j, there will one good for each pair of agents who disagree on issue j. Let R(M) be the set of goods in R(Γ): then

    R(M) = {(i,k,j) | j ∈ M, i,k ∈ N, a_ij≠ a_kj}

We we will refer to goods (k,k',j) where i ∈{k,k'} as agent i's “pairwise goods". Note that (i,k,j) and (k,i,j) refer to the same good.

If y_i is a bundle associated with Γ (denoted y_i ∼Γ), then y_i ∈ℝ_≥ 0^|M|. If y_i is a bundle associated with R(Γ) (denoted y_i ∼ R(Γ)), then y_i ∈ℝ_≥ 0^|R(M)|. 

We will use j to represent issues in M and ℓ to represent goods in R(M). We also use y_i(ikj) to denote y_iℓ when ℓ = (i,k,j).

In order to purchase α units of issue j in the PDM, agent i will need to purchase at least α units of all of her pairwise goods for issue j. Formally, agent i's utility for a bundle y_i ∈ℝ_≥ 0^|R(M)| is

    u_i( min_k ∈ N:
     a_i1≠ a_k1 y_i (ik1),min_k ∈ N:
     a_i2≠ a_k2 y_i (ik2),…min_k ∈ N:
     a_im≠ a_km y_i (ikm))

Agent i's utility is as if she purchased min_k ∈ N: a_ij≠ a_kj y_i (ikj) probability of each issue j in the PDM Γ. For example, if agent i's utility in Γ is linear with weights w_ij, her utility in R(Γ) would be

    ∑_j ∈ M w_ij( min_k ∈ N:
     a_ij≠ a_kj y_i (ikj))

These utility functions are nested Leontief; this will be discussed formally in Section <ref>.

Figure <ref> gives a graphical representation of R(Γ) for five agents and a single issue j, where a_1j = a_2j = a_3j = 0 and a_4j = a_5j = 1.  An edge from an agent to a good indicates that that agent desires that good. One key aspect of pairwise issue expansion is that on each issue j, each agent is in competition with everyone she disagrees with, and not in competition with anyone she agrees with.



We first argue informally for the correctness of the reduction. Agent i will only ever spend money on her pairwise goods, because other goods do not affect her utility. Because of the nested Leontief structure of the utilities in R(Γ), for a fixed issue j, agent i will buy the same amount of each of her pairwise goods: buying a larger amount of one of the goods would not increase her utility (because it would not increase the minimum), so she would be wasting money. Thus for a fixed issue, agent i buys the same amount of each of her pairwise goods (though this can differ across issues). 

So suppose that for each issue j, agent i buys α_ij of each of her pairwise goods for that issue. If R(Γ) is at equilibrium, every agent k who disagrees with agent i on issue j can receive at most 1-α_ij of good (i,k,j), since the total supply of each good is 1. As argued above, agent k will never buy more than 1 - α_ij of any of her pairwise goods on issue j, because of the nested Leontief structure. Thus every agent k who disagrees with agent i on issue j will buy exactly 1- α_ij of each of her pairwise goods for issue j. This leaves exactly α_ij for everyone who agrees with agent i on issue j. Thus in equilibrium, everyone who agrees with agent i buys α_ij of their pairwise goods on issue j, and everyone who disagrees with agent j buys 1- α_ij of their pairwise goods on issue j.

This means that when R(Γ) is in equilibrium, whenever two agents agree on an issue, they buy the same amount of their pairwise goods for that issue, and whenever they disagree, the amounts they buy sum to 1. Let  be the outcome where z^j,a_ij = α_ij and z^j, 1-a_ij = 1 - α_ij for all j ∈ M. Then  is a valid outcome of the PDM. Also, because R(Γ) is a Fisher market, an equilibrium price vector assigns a single price to each good: this yields a price for each pairwise disagreement on each issue. This leads to the pairwise pricing equilibrium notion, which  as defined above will satisfy.

Furthermore, we know that any Fisher market equilibrium maximizes Nash welfare. The agents will have the same utilities in both the PDM and the constructed Fisher market at equilibrium, so the Fisher market equilibrium will respond to a pairwise pricing equilibrium which maximizes Nash welfare in the PDM.

Finally, we mention that this reduction can be generalized to d-ary issues under the assumption that each agent has utility for at most one alternative per issue. Instead of one good for each pair of agents who disagree, there would be one good for each set of d agents where each agent has a different preferred alternative, and a similar argument will hold.






 §.§ Additional setup and formal theorem statements


Some additional notation will be useful. We define relations R and  which will map bundles and prices between Γ and R(Γ).

For a bundle y_i ∼Γ, we define a corresponding bundle R(y_i) ∼ R(Γ) by

    R(y_i)_(kk'j) =
    
    y_ij if i ∈{k,k'}
    
    0 if i∉{k, k'}∀ (k,k',j) ∈ R(M)

where R(y_i)_(kk'j) denotes the quantity of good (k, k', j) in bundle R(y_i). For a bundle y_i ∼ R(Γ), the corresponding bundle (y_i) ∼Γ is defined by

    (y_i)_j = min_k ∈ N:
     a_ij≠ a_kj y_i (ikj)∀ j∈ M

where (y_i)_j denotes the quantity of issue j in bundle (y_i). Also, for a list of private bundles ∼Γ, we use R() to refer to the list of private bundles in R(Γ) where agent i's bundle is R(y_i). Similarly, for any ∼ R(Γ), () is a list of private bundles in Γ where agent i's bundle is (y_i). 

It is important to note that while the equilibria of Γ and R(Γ) coincide, the correspondence is not always meaningful for non-equilibrium outcomes. In particular, not every y_i ∼ R(Γ) satisfies y_i = R((y_i)): for example if y_i(kk'j) > 0 when i ∉{k,k'}.


Let u_i be agent i's utility function in Γ. Then agent i's utility function in R(Γ) is given by

    u_i^R(y_i) = u_i((y_i))

This is equivalent to the definition of agent utilities given in Section <ref>: simply subtitute the definition of (y_i). Also note that for any y_i ∼Γ, we have y_i = (R(y_i)), and so u_i(y_i) = u_i^R(R(y_i)).

We would also like to relate prices in Γ and R(Γ). Since R(Γ) is a Fisher market, any price vector p associated with R(Γ) (denoted p ∼ R(Γ)) assigns a single price to each good ℓ∈ R(M): p ∈ℝ_≥ 0^|R(M)|. We will be considering per-person per-issue prices for the PDM Γ, so any set of prices p associated with Γ (denoted p ∼Γ) assigns one price to each person i ∈ N for each issue j ∈ M: p ∈ℝ_≥ 0^m× n.

For a price vector p ∼ R(Γ), we define prices (p) ∼Γ by

    (p)_ij = ∑_k ∈ N:
     a_ij≠ a_kj p_(ikj)∀ i∈ N, j∈ M

where (p)_ij is the price of issue j for agent i in price vector (p). In words, (p)_ij is the sum of agent i's pairwise prices for issue j. We will also use (p)_i to denote the vector of agent i's prices: (p)_i = ((p)_i1...(p)_im).



Before we stating our theorems, we should verify that the utilities in R(Γ) satisfy the necessary requirements. If the utility functions in Γ are in class  ( could be the set of linear utility functions, for example), the utility functions in R(Γ) will be -nested Leontief.


For some agent i, let f_i1, f_i2...f_iL be Leontief utility functions. Then a utility function u_i is ℋ-nested-Leontief if there exists a utility function h_i: ^L_≥ 0→_≥ 0 such that h_i ∈, and

    u_i(y_i) = h_i(f_i1(y_i), f_i2(y_i)… f_iL(y_i))

for any bundle y_i.


In our setting, L = m for all agents, and for each j ∈ M, f_ij(y_i) = (y_i)_j = min_k ∈ N: a_ij≠ a_kj y_i (ikj). Then for each agent i, u_i^R(y_i) = u_i((y_i)) = u_i(f_i1(y_i), f_i2(y_i)...f_iL(y_i)).

The next lemma states that as long as h_i and f_i1, f_i2...f_iL satisfy our assumptions on utility functions, their composition does as well.

lemmalemNestedUtilities

	Suppose that the functions h_i, f_i1, f_i2… f_iL are continuous, normalized, concave, homogeneous of degree 1, non-decreasing, and non-constant. Then u_i = h_i(f_i1, f_i2… f_iL) meets the same conditions.



We will claim that each market equilibrium in R(Γ) corresponds to a pairwise-pricing market equilibrium (PME) in Γ. The formal definition of a PME appears in Appendix <ref>. Informally, it is a list of private bundles  and per-person per-issue prices p ∈_≥ 0^m× n generated by pairwise issue expansion (i.e., p = (p') for some p' ∼ R(Γ)) such that


  * Every agent receives a private bundle in her demand set.

  * Whenever two agents agree on an issue, they purchase the same amount of that issue.

  * Whenever two agents disagree on an issue, they amounts of that issue that they purchase sum to 1.


This is exactly the definition alluded to via the α_ij variables in the informal argument given in Section <ref>. This leads to the following theorem:

theoremthmReductionEq

For an allocation ∼ R(Γ) and prices p ∼ R(Γ), (, p) is a ME of the market R(Γ) if and only if ((), (p)) is a PME of the PDM Γ.


Finally, we wish to claim the maximum Nash welfare outcomes in Γ and R(Γ) correspond. We will actually prove this correspondence for all welfare functions, not just the Nash welfare, and even for approximations of welfare functions.

Formally, let Ψ: ℝ_≥ 0^n →ℝ be a function. When the n inputs to Ψ are understood to be the n agent utilities for a particular outcome (of a pubic or private instance), we call Ψ a welfare function. Because Ψ depends only on the agent utilities, we will use this terminology and notation for both the public and private settings. With slight abuse of types, we will write Ψ() = Ψ(u_1(), u_2(),...u_n())[Throughout most of the paper, we use  to refer to the outcome of a public decisions instance and  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  to denote outcomes for both.].

Common welfare functions include the utilitarian welfare function, Ψ() = ∑_i ∈ N u_i(), the egalitarian welfare function, Ψ() = min_i ∈ N u_i(), and most importantly for us, the (budget-weighted) Nash welfare function, Ψ() = (∏_i ∈ N u_i()^B_i)^1/. We say that an outcome  is a α-approximation of Ψ if

    Ψ() ≥α·max_𝐳'∼ΓΨ(𝐳')




If  is an outcome of a public decisions instance, technically R() does not typecheck, since = (z^1...z^m) is not a list of bundles. We interpret R() to mean R(x_1, x_2...x_n), where x_i is agent i's public bundle as induced by .

theoremthmReductionMax

Let Ψ be a welfare function, let Γ be the public decisions instance (N,M) with budgets B_1...B_n, and let α≥ 0. Then  is an α-approximation of Ψ in Γ if and only if R() is an α-approximation of Ψ in R(Γ).


Note that by the same reasoning, ∼ R(Γ) is an α-approximation of Ψ if and only if () ∼Γ is also an α-approximation of Ψ. Thus for any welfare function Ψ and any α≥ 0, the α-approximations of Γ and R(Γ) correspond exactly.



 §.§ Lifting Fisher markets results using pairwise issue expansion


In addition to uncovering a surprising conceptual connection, pairwise issue expansion allows us to immediately lift many results from the Fisher market literature to the public decision-making setting. In particular, if a result holds for Fisher market with -nested Leontief utilities, it holds in the public decisions setting for  utilities. Any Fisher market result regarding the ME can be lifted using Theorem <ref>, and any Fisher market result regarding any approximation of any welfare function can be lifted using Theorem <ref>. The following Fisher market results are known:



  * There exists a strongly polynomial-time algorithm for finding a Fisher market equilibrium with two agents and any utility functions <cit.>[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.].


  * There exists a strongly polynomial-time algorithm for finding a Fisher market equilibrium for Leontief utilities with weights in {0,1} <cit.>.


  * There exists a polynomial-time algorithm for a Fisher market with Leontief utilities which yields a O(log n) approximation simultaneously for all canonical welfare functions (i.e. Nash welfare, utilitarian welfare, egalitarian welfare, etc) <cit.>.


The first two can be lifted using Theorem <ref>, and the third can be lifted using Theorem <ref>. Note that nested Leontief-Leontief functions are just Leontief functions. This yields the following PDM results:




  * There exists a strongly polynomial-time algorithm for finding a PME with two agents and any utility functions.


  * There exists a strongly polynomial-time algorithm for finding a PME for Leontief utilities with weights in {0,1}.


  * There exists a polynomial-time algorithm for a PDM with Leontief utilities which yields a O(log n) approximation simultaneously for all canonical welfare functions (i.e. Nash welfare, utilitarian welfare, egalitarian welfare, etc).


The final result we are interested in lifting is a discrete-time process for finding the Fisher market equilibrium for nested CES-Leontief utilities that converges in polynomial-time <cit.>. The next section discusses this in more depth.

As a final comment, there are also results of interest that do not immediately fall under the framework of Theorems <ref> and <ref>, but which we conjecture could be lifted using our reduction. For example, <cit.> studies Leontief utilities in the context of price curves, where the cost of a good may be any increasing function of the quantity purchased (as opposed to just a linear function, as is usually assumed). We believe that pairwise issue expansion could be used to generate pairwise price curves, where there would be a price curve assigned to each pair of agents who disagree on an issue, instead of a single price. Pairwise issue expansion seems general enough to apply to non-standard market models, such as that of <cit.>, but we leave it for future work.



§ PUBLIC MARKET TÂTONNEMENTS





In this section, we describe how the reduction immediately leads to existence of several public market tâtonnements. In particular, we show that any Fisher market that works for -nested utilities yields a PDM for  utilities. 

This does not immediately follow from pairwise issue expansion for several reasons. The first is that deals with approximate equilibria, and Theorem <ref> only considers exact equilibria. Because this correspondence holds for approximate equilibria as well (see proof of Theorem 5.4), any Fisher market that works for -nested utilities immediately yields an algorithm for computing PDM equilibria for  utilities, but not a . A true PDM would only have access to agents' demands in the PDM, but the resulting algorithm would need to elicit agents' demands in the constructed Fisher market. We handle this by running the Fisher market as a hidden subroutine within the PDM , as demonstrated by Figure <ref>.


Let a Fisher market 𝒯 be an iterative algorithm that starts at an initial price vector p^0, and then at each time t, 
	
  * Receives demand set D_i(p^t)[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.] from each agent i.
	
  * Updates prices as some function g of the demands, p^t+1 = g_𝒯(p^t, D(p^t)). 

As time increases, prices and associated demands approach an approximate equilibrium, for some notion of approximate. Figure <ref> illustrates the meta-algorithm for public market tâtonnements. From a Fisher market 𝒯, let (𝒯) be the induced public market tâtonnement that initializes an initial price vector p^0 in the hidden Fisher market and then at each time t,
	
  * Converts prices p^t to public market prices (p^t) and shows them to agents.
	
  * Receives demand set D_i((p^t)) from each agent i.
	
  * Converts the agent demands to the associated private market demand set 𝐲^R = {R(y_i)}_y_i∈ D_i((p^t)). 
	
  * Updates prices through the Fisher market function, p^t+1 = g_(p^t, 𝐲^R). 
 




We begin with the definitions of approximate equilibria and convergence.


	A δ-equilibrium (, p) in a Fisher market  is an allocation  and prices p where
	
		
  * Each agent receives a bundle in her demand set: x_i ∈ D_i(p).
		
  * p_j > δ∑_i ∈ N x_ij > 1-δ  
		
  * ∀ j, ∑_i ∈ N x_ij≤ 1+δ
	



Note that this definition is introduced in <cit.>.


A δ-PME (, p) is a list of private bundles  and per-person per-issue prices p ∈ℝ_≥ 0^m× n where

	
  * Each agent receives a private bundle in her demand set: y_i ∈ D_i(p_i).
	
  * The market approximately clears: there exists a outcome = (z^1...z^m) ∈ [0,1]^m× 2 where for every issue j ∈ M, all of the following hold:
	
		
  * z^j,0 + z^j,1≤ 1+δ
		
  * For all i∈ N, y_ij≤ z^j, a_ij + δ. If p_ij > nδ, then y_ij > z^j,a_ij - δ.
	





	A  has converged to a δ-equilibrium at time T if ∃ where (, p^T) is a δ-equilibrium. Similarly, () has converged to a δ-PME at time T if ∃ where (, (p^T)) is a δ-PME.
	

The definition does not imply that all demands at the equilibrium prices form an approximate equilibrium, only that there exists an allocation consistent with demands at the equilibrium prices such that the supply constraints are met. However, note that when utility functions are strictly concave, demands are unique.

Our first theorem shows that any Fisher market for ℋ-nested Leontief utility functions yields a PDM for ℋ utility functions. Theorem <ref>, whose proof appears in the appendix, allows one to lift both convergence and convergence rates from Fisher market tâtonnements. 

theoremtatLift
	Consider a Fisher market tâtonnement 𝒯. Suppose 𝒯 converges to a δ-equilibrium for ℋ-nested leontief utilities in O(κ(m,n,δ)) time steps, where n is the number of agents and m the number of goods. Then (𝒯) converges to a 3δ-PME for the PDM with ℋ utilities in O(κ(n^2m,n,δ)). 
	









One Fisher market that we can lift using Theorem <ref> comes from <cit.>, which gives a polynomial-time tâtonnement that converges to a δ-equilibrium for CES-Leontief utilities with ρ∈ (-∞, 0)∪(0, 1) in polynomial time. By Theorem <ref>, this yields a PDM for CES utilities.




We would also like a PDM that works for a wider range of utility functions, especially linear utilities. Section <ref> presents a stochastic gradient descent style tâtonnement for Fisher markets which converges asymptotically to an equilibrium for all EG utility functions[functions that meet the 5 conditions from Section <ref>.], following the framework of <cit.>. Combined with Theorem <ref>, this tâtonnement implies existence of a PDM tâtonnement with asymptotic convergence to an equilibrium for all EG utility functions.


















§ CONCLUSION


In this paper, we studied adaptations of markets to the public decision-making setting. In Section <ref>, we showed that issue pricing in the public decisions setting can yield very poor equilibria: for linear utilities, the Nash welfare can be a factor of O(n) worse than optimal. This is in contrast to private goods, where per-good pricing is the accepted standard, and yields optimal equilibria. We showed in Section <ref> that pairwise issue expansion reduces any public decisions market to an equivalent Fisher market, how optimal equilibria can be constructed using this reduction. We used pairwise issue expansion to lift various Fisher market results to the public decision-making context, including , which we discussed in Section <ref>.

Most importantly, our reduction uncovers a powerful connection between the private goods and public decision-making settings that we believe has many possible applications. For example, suppose we had a mechanism for private goods which computes some desirable outcome other than maximum Nash welfare (maybe it computes the allocation which maximizes the minimum utility, for example). If that algorithm works for nested -Leontief utilities for private goods, we imagine that it could be immediately lifted to work for  utilities in for public-decisions. More generally, it seems like more or less any result that applies to -Leontief utilities for private goods would apply for  utilities for public decisions. We believe this merits more study.



§ ACKNOWLEDGEMENTS

This research was supported in part by NSF grant CCF-1637418, 
ONR grant N00014-15-1-2786, and the NSF Graduate Research Fellowship under grants DGE-114747 and DGE-1656518.

plain







§ LINDAHL EQUILIBRIA

In this section, we show how our public decisions setting corresponds to a natural public goods market in the setting of Lindahl equilibria, and how our reduction can also be used to compute Lindahl prices for this public goods market. The Lindahl Equilibrium has a long history and, at times, the term has been used to mean slightly different things <cit.>. Foley <cit.> gave general conditions for the existence of the Lindahl Equilibrium and its correspondence to the core. We first introduce a simplified definition of Lindahl Equilibria. 


	A Lindahl Equilibrium with m public goods, 1 private good, n agents, and entry private good amounts {w_i}_i=1^n is an (public goods allocation, private goods allocation, per-person per-issue price) vector (z^*∈_+^m, {y_i^* ∈_+}_i=1^n, {p_i^* ∈_+^m}_i=1^n) such that
	
		
  * z^* is a solution to max_z (∑_j=1^n p_j^*)z - c(z)
		
  * For each i∈{1, …, n}, (z^*, y_i^*) is a solution to	max_(z,y_i)
		u_i(z, y_i) subject to p^*_i z + y_i ≤ w_i
	
where c(z) is the cost to produce the public good vector z in terms of the private good and u_i is the participant utility function in terms of the public and private goods. 


In a Public Decision Market, the private good is the “influence” of each agent, for which agents have no utility, i.e., influence not spent is lost. Furthermore, there are 2 public goods per issue, 1 for each alternative, and each with the same price for each agent. Similarly,

    c(z) = 
    0    z^j,0 + z^j,1≤ 1   ∀ j
    ∞   else

i.e., if in the case in which each alternative on each issue is implemented with some probability, then there is no cost of using the entire probability, and no possibility of creating more probability.


	An equilibrium (z^*∈_+^2× m, {y_i^* ∈_+}_i=1^n, {p_i^* ∈_+^2× m}_i=1^n) of the PDM with m issues and agent budgets B_i, where z^* is the decision vector, p^* are the per-person per-issue prices from the Fisher market reduction, and final influence vectors are y_i^* = 0, is a Lindahl Equilibrium with entry private good amounts w_i = B_i. 


	Condition 2 follows directly from the equilibrium condition that optimal allocation is in the demand set of each agent at the equilibrium prices. Condition 1 requires a bit more work. Note that ∀ j, for each copy of the good, the sub-price p_ikj = p_kij, where a_ij≠ a_kj. Then, ∀ j, p^0_j = ∑_i:a_ij = a∑_k:a_kj≠ a p_ikj  p^0_j = p^1_j. Thus, all feasible x are in the solution set in the first condition, and an equilibrium of the PDM is feasible.



Lemma <ref>, alongside Theorem <ref> and the existence of Fisher market equilibria <cit.> establishes the existence of a Lindahl equilibrium in our setting. 

We note that Lemma <ref> further establishes that the solution is in the core, as Lindahl Equilibria are in the core <cit.>.


 §.§ Economies with public goods

The existence of Lindahl Equilibria in Public Good economies (of which Public Decision Markets are a special case, as we will show) was established by Foley <cit.>. The chief technique is a reduction to Private Goods economies. The reduction yields a non-constructive existence proof, and operates as follows: create a copy of each good for each participant, with equality of the amount of each good enforced through conic constraints. Then, the proof is finished by invoking the existence of equilibria satisfying certain conditions in Private Goods economies, after showing that the additional constraints restricting the cone of production do not violate any assumptions <cit.>. We note that existence of Lindahl equilibria of the PDM can also be established non-constructively through the same technique, by showing that the resulting market satisfies the assumptions in <cit.>. 

One natural question is how Foley's reduction to private goods compares to the reduction in this work. Equation (<ref>) contains the convex program to find MNW through Foley's reduction. We use s∈{0,1} to denote each side of the issue. Equation (<ref>) contains our reduction, which has a nested utility function structure. 





    max_∈ [0,1]^(2× m)× n   (∏_i ∈ N u_i(x_i)^B_i)^1/
    
    s.t.       x^0_ij + x^1_ij≤ 1   ∀ j ∈ M, i ∈ N 
       x^s_ij = x^s_kj   ∀ j ∈ M,  i,k ∈ N, s∈{0, 1}
    
    max_v ∈ [0,1]^m× n, ∈ [0,1]^ñ   (∏_i ∈ N u_i(v_i)^B_i)^1/
    
    s.t.       v_ij≤ x_i(ikj)   ∀ j ∈ M, i,k ∈ N, a_ij≠ a_kj
       x_i(ikj) + x_k(ikj)≤ 1   ∀ j ∈ M, i,k ∈ N, a_ij≠ a_kj

Where ñ is 2(# of disagreement pairs across issues). 

Both programs can be solved in polynomial time. However, Foley's reduction does not obviously resemble a Fisher market due to the extra equality constraints. 

	Program (<ref>) does not transform into a Fisher market.


	We write the Lagrangian of the Program (<ref>), with the objective function written in log form.
	
    L(x, p, q)    = ∑_i B_i log (u_i(x_i)) - ∑_i,j p_ij(x^0_ij + x^1_ij) + ∑_i,jp_ij - ∑_i≠ k,j,s q^s_ikj (x^s_ij - x^s_kj)
        s.t.     p≥ 0, x≥0, q^s_ikj≥ 0

	This Lagrangian has per-person per-issue prices q^s_ikj, p_ij for each side of each issue that cannot be trivially turned into per-good prices with separate goods not having joint constraints. If one considers each (i,j,s) tuple a good in the Fisher market, the two goods associated with the two sides of each issue, x^0_ij, x^1_ij are coupled through p_ij. Similarly, if pair (i,j) corresponds to a good, goods across individuals x^s_ij, x^s_kj are coupled through q^s_ikj in a way that does not resemble supply constraints. Merging the goods for each side, such that the good represents the probability on one of the alternatives for each issue, would violate the non-decreasing constraint for utility functions. Eliminating or combining either of these variables would amount to eliminating the corresponding constraints. This coupling prevents a non-trivial mapping to the Fisher market case, which does not have cross-good constraints but has per-good prices. 




 Our reduction fills this gap for Public Decision markets, showing that these prices can emerge from a pure Fisher market with a modification of buyer utilities. In Program (<ref>), there is a good (i,k,j) for each (i,k) pair that disagrees on issue j, with i's utility function only dependent on the amount i buys, x_ikj. This program thus yields goods with per-good pricing (on the Fisher market goods) and no cross-goods constraints.


Programs (<ref>) and (<ref>) are equivalent.


	Both are equivalent to Program (<ref>), which we repeat below:
    max_∈ [0,1]^2× m   (∏_i ∈ N u_i(z)^B_i)^1/
    
    	s.t.       z^j,0 + z^j,1≤ 1     ∀ j ∈ M

Program (<ref>) and (<ref>) are immediately equivalent by combining variables. The equivalence of the reduction (Theorem <ref>) establishes that Program (<ref>) and PDM Program (<ref>) have the same solution. 


























We note that the dual program from the Foley reduction may yield a tatonnement similar to that presented in Section <ref>. However, tatonnements from Fisher markets cannot directly be lifted using the reduction. 



















§ OMITTED DEFINITIONS AND PROOFS FROM SECTION 4


Section <ref> contains the formal definitions of the pairwise pricing model. Section <ref> contains the formal analysis of R and , leading to Theorems <ref> and <ref>. 



 §.§ Pairwise pricing


In the issue pricing model of Section <ref>, the price for an issue was the same for all agents, and the amount of probability put on alternative a on issue j in the outcome (denoted z^j,a) was the sum of the agents' purchases. Formally, Section <ref> defined z^j,a = ∑_k ∈ N: a_ij = a y_ij where y_ij is the probability that agent i purchased on issue j (y_i is agent i's private bundle).

The definition of z^j,a will be different here. This section describes a model where agents may have different prices for the same issue. This will allow us to enforce that in equilibrium, all agents who agree on issue j will purchase the same amount of issue j. For every i ∈ N and j ∈ M where agent i's price for issue j is nonzero, at equilibrium[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 will have

    z^j, a_ij = y_ij
 
The key consequence is that each agent's private and public bundles will be the same in equilibrium, and so u_i(y_i) = u_i(x_i()). Thus each agent's utility can be written as a function of only her private bundle: this will enable the reduction to private goods.

We now formally describe the personalized pricing model. For prices p ∈_≥ 0^m× n, let p_ij be the price for agent i for issue j, and let p_i = (p_i1...p_im). Formally, a private bundle y_i is affordable if y_i · p_i = ∑_j∈ My_ijp_ij≤ B_i. Because we will have u_i(y_i) = u_i(x_i) in equilibrium, we can define agent i's demand to be independent of other agents' private bundles[We assume that agents truthfully report their demands according to this definition: recall that we do not consider strategic behavior.]:

    D_i(p) = _y_i ∈^m_≥ 0: y_i · p_i ≤ B_i u_i(y_i)


A personalized-pricing market equilibrium (PME) (, p) is a list of private bundles  and personalized prices p ∈ℝ_≥ 0^m× n where


  * Each agent receives a private bundle in her demand set: y_i ∈ D_i(p_i).

  * The market clears: there exists an outcome = (z^1...z^m) ∈ [0,1]^m where for every issue j ∈ M, all of the following hold:
	
	
  * z^j,0 + z^j,1 = 1
	
  * For all i∈ N, y_ij≤ z^j, a_ij. If p_ij > 0, then y_ij = z^j,a_ij.
	


The market clearing condition (Condition <ref>) is different than in traditional private goods markets. Instead of the sum of the agent's demands being equal to the supply, the condition here is that there is a single outcome that is consistent with every agent's demand. Roughly speaking, this means that whenever two agents agree on an issue, they demand the same quantity of that issue, and whenever two agents disagree, the sum of their demands equals the supply. This can be thought of as all agents buying the “same" private bundle, modulo their preferred alternatives. 

At equilibrium,  is treated as the outcome of the public decisions instance. However,  may not be unique: if y_ij < z^j, a_ij for some i,j, there may be multiple outcomes compatible with the list of agent demands. The following proposition shows that all outcomes compatible with  are more or less the same.





Let (, p) be a PME. Then for any outcome  satisfying the market clearing condition, u_i() = u_i(y_i) for all i∈ N.


Fix some agent i ∈ N, and let y'_i be the private bundle where y'_ij = z^j, a_ij for all j ∈ M. For every issue j where y_ij≠ z^j, a_ij, we have p_ij = 0. Thus y_i and y'_i have the same cost. Since y_i is in agent i's demand set, y_i is affordable. Thus y'_i is also affordable. Suppose u_i() = u_i(y'_i) > u_i(y_i): then y_i would not be in agent i's demand set, which is a contradiction.


Since each agent's private and public bundles are the same at equilibrium in this model, we mostly omit “private" and “public" and just use the term “bundle". We reserve  for denoting the overall outcome of the PDM, and just use y_i to denote agent i's bundle.






 §.§ Formal analysis of pairwise issue expansion


We begin with Lemma <ref>, which states that as long as agents only buy their pairwise goods, the cost of a bundle y_i ∼ R(Γ) at prices p is the same as the cost of bundle (y_i)∼Γ at prices (p). The proof primary consists of arithmetic and substituting definitions.


Given prices p ∼ R(Γ) and a bundle y_i ∼ R(Γ),


  * (y_i) ·(p)_i ≤ y_i · p

  * Suppose that (1) for any j ∈ M and k,k' ∈ N\{i} where y_i(kk'j)≠ 0, we have p_(kk'j) = 0, and (2) for any j ∈ M and k∈ N where y_i(ikj)≠min_k ∈ N:
 a_ij≠ a_kj y_i (ikj), we have p_(ikj) = 0. Then (y_i) ·(p)_i = y_i · p.




Suppose y_i is a bundle in R(Γ). The cost of y_i at prices p is 

    y_i · p =    ∑_ℓ∈ R(M) y_iℓp_ℓ    (by definition)
    
    =    ∑_j ∈ M∑_k,k' ∈ N:
     a_kj≠ a_k'j y_i(kk'j)p_(kk'j)    (rewriting each good ℓ∈ R(M) as a triple (i,k,j))
    ≥    ∑_j ∈ M∑_k ∈ N:
     a_ij≠ a_kj y_i(ikj)p_(ikj)    (only including agent i's pairwise goods in the sum)
    ≥    ∑_j ∈ M∑_k ∈ N:
     a_ij≠ a_kj p_(ikj)min_k' ∈ N:
     a_ij≠ a_k'j y_i (ik'j)    (replacing each y_i(ikj) with min_k' ∈ N:
     a_ij≠ a_k'j y_i (ik'j))
    
    =    ∑_j ∈ M∑_k ∈ N:
     a_ij≠ a_kj p_(ikj)(y_i)_j     (by definition)
    
    =    ∑_j ∈ M(y_i)_j ∑_k ∈ N:
     a_ij≠ a_kj p_(ikj)    (moving (y_i)_j out of the inner sum)
    
    =    ∑_j ∈ M(y_i)_j (p)_ij    (by definition)
    
    =    (y_i) ·(p)_i     (by definition)

Furthermore, the first inequality holds with equality if for any j ∈ M and k,k' ∈ N\{i} where y_i(kk'j)≠ 0, p_(kk'j) = 0. Similarly, the second inequality holds with equality if for any j ∈ M and k∈ N where y_i(ikj)≠min_k ∈ N:
 a_ij≠ a_kj y_i (ikj), p_(ikj) = 0. Therefore under those two assumptions, (y_i) ·(p)_i = y_i · p.



Lemma <ref> is a simple application of Lemma <ref>.

For prices p ∼ R(Γ) and a bundle y_i ∼Γ, we have y_i ·(p)_i = R(y_i) · p.



By definition of R(y_i), we have (1) y_i(kk'j) = 0 for all j ∈ M and k,k' ∈ N\{i}, and (2) y_i(ikj) = min_k ∈ N:
 a_ij≠ a_kj y_i(ikj) for all j ∈ M and k∈ N. Then by Lemma <ref>, y_i ·(p)_i = R(y_i) · p.



Lemma <ref> states that if a bundle y_i ∼ R(Γ) is agent i's demand set D_i^R(p), then (1) y_i contains only agent i's pairwise goods, and (2) for a fixed issue j, y_i contains the same amount of each of her pairwise goods. The proof is based on the informal argument given before: violating either (1) or (2) wastes money that could be spend to increase her utility.


Given prices p∼ R(Γ), suppose a bundle y_i  ∼ R(Γ) is in D_i^R(p). Then (1) for any j ∈ M and k,k' ∈ N\{i} where y_i(kk'j)≠ 0, we have p_(kk'j) = 0, and (2) for any j ∈ M and k∈ N where y_i(ikj)≠min_k ∈ N:
 a_ij≠ a_kj y_i (ikj), we have p_(ikj) = 0.



First, suppose for sake of contradiction that there exists j ∈ M and k, k' ∈ N\{i} where p_(kk'j) > 0 and y_i(kk'j) > 0. Consider the bundle y_i' ∼ R(Γ) which is identical to y_i, except that y'_i(kk'j) = 0. Since (y_i) = (y_i'), we have u_i^R(y_i) = u_i^R(y_i'). But since p_j > 0, the y_i · p - y_i'· p = y_i(kk'j)p_(kk'j). Consider the bundle y”_i ∼ R(Γ) where for all ℓ∈ R(M),

    y”_iℓ = y'_iℓ + y_i(kk'j)p_(kk'j)/∑_ℓ' ∈ R(M) p_ℓ '

Then we have y”_i · p = y_i' · p + y_i(kk'j)p_(kk'j) = y_i · p. Since y_i ∈ D_i^R(p), y_i is affordable at prices p. Thus y”_i is affordable at prices p. 

Finally, we show that u_i^R(y”_i) > u_i^R(y_i). We have y”_iℓ > y'_iℓ for all ℓ∈ R(M). Thus for all ℓ, there exists a constant α_ℓ > 1 where y”_iℓ = α_ℓ y'_iℓ. Let α = min_ℓ∈ R(M)α_ℓ. Then y”_iℓ≥α y'_iℓ for all ℓ∈ R(M). Because u_i^R is homogenous of degree 1 and monotone, we have u_i^R(y”_iℓ) ≥α· u_i^R(y'_iℓ) > u_i^R(y'_iℓ) = u_i^R(y_i).

Thus we have u_i^R(y”_iℓ) > u_i^R(y_iℓ) and y”_i · p = y_i' · p. But then y_i cannot be in agent i's demand set, which is a contradiction.

The second case is similar. Suppose that there exists j ∈ M and k ∈ N where p_(ikj) > 0 and y_i(ikj) > min_k' ∈ N:
 a_ij≠ a_k'j y_i (ik'j). Define the bundle y'_i ∼ R(Γ) to be identical to y_i, except that y_i(ikj) = min_k' ∈ N:
 a_ij≠ a_k'j y_i (ik'j). Define the bundle y”_i ∼ R(Γ) by 

    y”_iℓ = y'_iℓ + (y_i(ikj) - min_k' ∈ N:
     a_ij≠ a_k'j y_i (ik'j))p_(ikj)/∑_ℓ' ∈ R(M) p_ℓ '

Then u_i^R(y”_i) > u_i^R(y'_i) = u_i^R(y_i), and y”_i · p = y_i · p. Thus y_i cannot be in agent i's demand set, which is a contradiction.



Lemma <ref> is a straightforward combination of the previous two lemmas.

Given prices p∼ R(Γ), suppose a bundle y_i  ∼ R(Γ) is in D_i^R(p). Then (y_i) ·(p)_i = y_i · p.



By Lemma <ref>, we have (1) for any j ∈ M and k,k' ∈ N\{i} where y_i(kk'j)≠ 0, we have p_(kk'j) = 0, and (2) for any j ∈ M and k∈ N where y_i(ikj)≠min_k ∈ N:
 a_ij≠ a_kj y_i (ikj), we have p_(ikj) = 0. Therefore by Lemma <ref>, we have (y_i) ·(p)_i = y_i · p.



Lemma <ref> states that y_i is in agent i's demand set in R(Γ) if and only if (y_i) is in agent i's demand set in Γ. This will not only play an important role in the proof of Theorem <ref>, but also later on in tâtonnement.

The majority of the proof of Lemma <ref> is devoted to proving that

    max_y_i' ∼Γ:
     y_i' ·(p)_i ≤ B_i u_i(y_i')
    = max_y_i'∼ R(Γ): 
     y'_i · p ≤ B_i u_i^R(y_i')


The intuitive argument for the above equality is that the utilities and costs of bundles are the same in both Γ and R(Γ). Slightly more formally, for any bundle y_i ∼Γ, R(y_i) ∼ R(Γ) has the same utility (by definition) and the same cost (by Lemma <ref>). For any bundle y_i ∼ R(Γ), u_i^R(y_i) = u_i((y_i)) is also true by definition, but y_i and (y_i) do not necessarily have the same cost. That is where Lemma <ref> will be important.


Given prices p ∼ R(Γ) and a bundle y_i ∼ R(Γ), y_i ∈ D_i^R(p) if and only if (y_i) ∈ D_i((p)).



Lemma <ref> states that y'_i ·(p)_i = R(y'_i) · p for any bundle y'_i ∼Γ. This implies the following set equivalence:

    {y'_i | y'_i∼Γ and y'_i ·(p)_i ≤ B_i}
    = {y'_i | y'_i ∼Γ and R(y'_i) · p ≤ B_i}

Next, recall that for any bundle y'_i ∼Γ, (R(y'_i)) = y'_i, so

    {y'_i | y'_i∼Γ and y'_i ·(p)_i ≤ B_i}
    = {(R(y'_i)) | y'_i ∼Γ and R(y'_i) · p ≤ B_i}

For every bundle y'_i ∼Γ, R(y_i') is a bundle in R(Γ). Therefore we can replace R(y'_i) with y'_i and get

    {(R(y'_i)) | y'_i ∼Γ and R(y'_i) · p ≤ B_i}⊆{(y'_i) | y'_i ∼ R(Γ) and y'_i · p ≤ B_i}

Note that the relationship is now subset instead of equality. This is because there may be some y'_i ∼ R(Γ) that does not equal R(y”_i) for any y”_i ∼Γ. Combining this subset relationship with the previous equality gives us

    {y'_i | y'_i∼Γ and y'_i ·(p)_i ≤ B_i}⊆{(y'_i) | y'_i ∼ R(Γ) and y'_i · p ≤ B_i}

Since u_i((y'_i)) = u_i^R(y'_i) by definition, we have

    {u_i(y'_i) | y'_i∼Γ and y'_i ·(p)_i ≤ B_i}⊆{u_i^R(y'_i) | y'_i ∼ R(Γ) and y'_i · p ≤ B_i}

Taking the max gives us

    max({u_i(y'_i) | y'_i∼Γ and y'_i ·(p)_i ≤ B_i})
    ≤max({u_i^R(y'_i) | y'_i ∼ R(Γ) and y'_i · p ≤ B_i})

which we can rewrite as

    max_y_i' ∼Γ:
     y_i' ·(p)_i ≤ B_i u_i(y_i')
    ≤max_y_i'∼ R(Γ): 
     y'_i · p ≤ B_i u_i^R(y_i')

Consider an arbitrary y_i”∈ D_i^R(p): then

    u_i^R(y_i”) = max_y_i'∼ R(Γ): 
     y'_i · p ≤ B_i u_i^R(y_i')

and y_i”· p ≤ B_i. Then by Lemma <ref>, (y_i”) ·(p)_i = y_i”· p ≤ B_i. Since (y_i”) ∼Γ and (y_i”) ·(p)_i ≤ B_i, we have

    max_y_i' ∼Γ:
     y_i' ·(p)_i ≤ B_i u_i(y_i')
    ≥ u_i((y_i”))

By definition, u_i^R(y_i”) = u_i((y_i”)), so

    max_y_i'∼ R(Γ): 
     y'_i · p ≤ B_i u_i^R(y_i')
    = u_i^R(y_i”) = u_i((y_i”)) ≤max_y_i' ∼Γ:
     y_i' ·(p)_i ≤ B_i u_i(y_i')
    ≤max_y_i'∼ R(Γ): 
     y'_i · p ≤ B_i u_i^R(y_i')

Therefore,

    max_y_i' ∼Γ:
     y_i' ·(p)_i ≤ B_i u_i(y_i')
    = max_y_i'∼ R(Γ): 
     y'_i · p ≤ B_i u_i^R(y_i')


Finally, suppose y_i ∈ D_i^R(p): then y_i · p ≤ B_i, and by Lemma <ref> we have (y_i) ·(p)_i = y_i · p ≤ B_i. Also,

    u_i((y_i)) = u_i^R(y_i) = 
    max_y_i'∼ R(Γ): 
     y'_i · p ≤ B_i u_i^R(y_i')
    = max_y_i' ∼Γ:
     y_i' ·(p)_i ≤ B_i u_i(y_i')

so (y_i) ∈ D_i((p)). Suppose (y_i) ∈ D_i((p)): then (y_i) ·(p)_i ≤ B_i. Since y_i = R((y_i)), we have y_i · p = (y_i) ·(p)_i ≤ B_i. Also,

    u_i^R(y_i) 
    = u_i((y_i))
    = max_y_i' ∼Γ:
     y_i' ·(p)_i ≤ B_i u_i(y_i')
    = max_y_i'∼ R(Γ): 
     y'_i · p ≤ B_i u_i^R(y_i')

Therefore y_i ∈ D_i^R(p).




Recall that for any bundle y_i ∼Γ, (R(y_i)) = y_i. Thus by Lemma <ref>, R(y_i) ∈ D_i^R(p) if and only if y_i = (R(y_i)) ∈ D_i(p). This is expressed by Corollary <ref>, which will be useful in Section <ref> when considering processes in the PDM.

[of Lemma <ref>]
Given prices p∼ R(Γ) and a bundle y_i ∼Γ, y_i ∈ D_i((p)) if and only if R(y_i) ∈ D_i^R(p).







*


() Suppose (, p) is a ME of the Fisher market R(Γ): then y_i ∈ D_i^R(p) for all i ∈ N, and ∑_i ∈ N y_iℓ = 1 or p_ℓ = 0 for all ℓ∈ R(M). By Lemma <ref>, we have (y_i) ∈ D_i((p)).

We define = (x^1...x^m) ∈ [0,1]^m× 2 as follows:

    x^j,0 =    max_i∈ N: a_ij = 0(y_i)_j
    
    x^j,1 =    1 - x^j,0

for all j ∈ M. We claim that for all i ∈ N and j ∈ M, (y_i)_j ≤ x^j,a_ij, and that (y_i)_j = x^j, a_ij if (p)_ij > 0. 

We first show that (y_i)_j ≤ x^j,a_ij for all i,j. When a_ij = 0, this is true by definition, so assume a_ij = 1. Since (, p) is a ME of R(Γ), for any ℓ∈ R(M), we have ∑_k' ∈ N y_k'ℓ≤ 1. Thus for any k ∈ N where a_ij≠ a_kj (i.e. a_kj = 0), we have ∑_k' ∈ N y_k'(ikj)≤ 1.

Also, recall that by definition, (y_i)_j = min_k∈ N: a_ij≠ a_kj y_i(ikj). Thus (y_i)_j ≤ y_i(ikj) for all k. Similarly, (y_k)_j ≤ y_k(ikj). Therefore

    (y_i)_j    + (y_k)_j ≤ y_i(ikj) + y_k(ikj)≤∑_k' ∈ N y_k'(ikj)≤ 1 ∀ k ∈ N: a_kj = 0 
    (y_i)_j    + max_k ∈ N: a_kj = 0(y_k)_j ≤ 1
    (y_i)_j    ≤ 1 - max_k ∈ N: a_kj = 0(y_k)_j = x^j,1

Thus (y_i)_j ≤ x^j,a_ij for all i ∈ N. It remains to show that (y_i)_j = x^j, a_ij whenever (p)_ij > 0.

Suppose for sake of contradiction there exists i ∈ N and j ∈ M where (y_i)_j < x^j,a_ij and (p)_ij > 0. Since (y_i)_j = min_k ∈ N: a_ij≠ a_kj y_i(ikj), there must exist k ∈ N where a_ij≠ a_kj and y_i(ikj) < x^j,a_ij. Since (p)_ij = ∑_k' ∈ N: a_ij≠ a_k'j p_(ik'j), there must exist k' where p_(ik'j) > 0.

If y_i(ik'j) > y_i(ikj), we have p_(ik'j) = 0 by Lemma <ref>. Thus assume y_i(ik'j)≤ y_i(ikj) < x^j,a_ij. We showed above that (y_k')_j ≤ x^j,a_k'j = 1 - x^j,a_ij: thus y_k'(ik'j)≤ 1-x^j, a_ij. Therefore y_i(ik'j) + y_k'(ik'j) < x^j, a_ij + 1 - x^j, a_ij  = 1. If there exists i' ∉i, k' where y_i'(ik'j) > 0, then p_(ik'j) = 0, which is a contradiction. Therefore ∑_ℓ∈ R(M) y_iℓ = y_i(ik'j) + y_k'(ik'j) < 1.

But then by the definition of a ME, we have p_(ik'j) = 0, which is again a contradiction. Therefore (y_i)_j = x^j, a_ij whenever (p)_ij > 0. This shows that ((y), (p)) is a PME of Γ.


() Suppose ((), (p)) is a PME of the PDM Γ. Then (y_i) ∈ D_i((p)) for all i ∈ N, so y_i ∈ D_i^R(p) by Lemma <ref>. Also, there exists = (x^1...x^m) ∈ [0,1]^m× 2 where for all i∈ N and j ∈ M, 


  * x^j,0 + x^j,1 = 1

  * (y_i)_j ≤ x^j, a_ij

  * (y_i)_j = x^j, a_ij whenever (p)_ij = 0.


It remains to show that for all ℓ∈ R(M), either ∑_i∈ N y_iℓ = 1 or p_ℓ = 0. Suppose for sake of contradiction that there exists ℓ = (i,k,j) ∈ R(M) where ∑_k' ∈ N y_k'(ikj) < 1 and p_(ikj) > 0. If there exists k' ∉{i,k} where y_k'(ikj) > 0, then p_(ikj) = 0 by Lemma <ref>. Thus 

    ∑_k' ∈ N y_k'(ikj) = y_i(ikj) + y_k(ikj) < 1

Furthermore, if either y_i(ikj)≠(y_i)_j or y_k(ikj)≠(y_k)_j, we have p_(ikj) = 0 again by Lemma <ref>. Thus y_i(ikj) = (y_i)_j and y_k(ikj) = (y_k)_j, so

    (y_i)_j +(y_k)_j < 1


Recall that (y_i)_j ≤ x^j, a_ij and (y_k)_j ≤ x^j, a_kj, and that x^j, a_ij + x^j, a_kj = 1 since a_ij≠ a_kj. Thus in order for (y_i)_j +(y_k)_j < 1 to be true, either (y_i)_j < x^j, a_ij or (y_k)_j < x^j, a_kj. By symmetry, suppose (y_i)_j < x^j, a_ij without loss of generality. Then because ((), (p)) is a PME, we have (p)_ij = 0.

By definition, (p)_ij = ∑_k' ∈ N: a_ij≠ a_k'j p_(ik'j). Since p_(ik'j)≥ 0 for all i,k',j, we have p_(ik'j) for all k' ∈ N where a_ij≠ a_k'j. But then p_(ikj) = 0, which is a contradiction. Thus for all ℓ∈ R(M), either ∑_i∈ N y_iℓ = 1 or p_ℓ = 0. Therefore (, p) is a ME of R(Γ).






*


We first claim that R() is a valid allocation in R(Γ), meaning that ∑_i ∈ N R(x_i)_ℓ≤ 1 for all ℓ∈ R(M). By definition of R(x_i), R(x_i)_(kk'j) = 0 whenever i ∉{k,k'}, and R(x_i)_(kk'j) = x_ij whenever i ∈{k,k'}. Therefore, for all ℓ∈ R(M),

    ∑_i ∈ N R(x_i)_ℓ = ∑_i,k,k' ∈ N R(x_i)_(kk'j)
    = R(x_i)_(ikj) + R(x_k)_(ikj)  = x_ij + x_kj

By definition of R(M), the fact that good (i,k,j) exists implies that a_ij≠ a_kj.  Since  is a valid outcome of Γ, for all j∈ M we must have x_ij + x_kj≤ 1 whenever a_ij≠ a_kj. Therefore ∑_i ∈ N R(x_i)_ℓ≤ 1. Since this holds for all ℓ∈ R(M), R() is a valid allocation in R(Γ).

By definition of  and u_i^R, we have u_i^R(x_i) = u_i((x_i)). Since Ψ depends only on the agents' utilities, we have Ψ(𝐱') = Ψ(R(𝐱')) for any outcome 𝐱'∼Γ. Similarly, recall that u_i(x_i') = u_i^R(R(x_i')) for any bundle x_i' ∼Γ, so Ψ(𝐱') = Ψ((𝐱')) for any outcome 𝐱'∼ R(Γ). 

Thus for every possible outcome of Γ, there is an outcome of R(Γ) which has the same value of Ψ, and for every possible outcome of R(Γ), there is an outcome of Γ which has the same value of Ψ. Therefore we have the numeral equality


    max_𝐱'∼ΓΨ(𝐱') = max_𝐱'∼ R(Γ)Ψ(𝐱')


Finally, because Ψ() = Ψ(R()), we have Ψ() ≥α·max_𝐱'∼ΓΨ(𝐱') if and only if Ψ(R()) ≥α·max_𝐱'∼ R(Γ)Ψ(𝐱'). Therefore  is an α-approximation of Ψ in Γ if and only if R() is an α-approximation of Ψ in R(Γ).










§ OTHER OMITTED PROOFS




 §.§ Omitted proofs from Section <ref>



*


Let Γ be the PDM (N,M, B) with linear utilities u_i given by weights w_ij, and Γ̃ be the Fisher market (N,M, B) with linear utilities ũ_̃ĩ given by the same weights.

Let (, p) be an IME of Γ: then y_i ∈ D_i(p, y_-i) for all i. Let x_i be agent i's public bundle in , let 𝐲' = (y_-i, y'_i) for an arbitrary private bundle y'_i, and let x'_i be agent i's public bundle for private bundles 𝐲'. Then we have


    u_i(y_-i, y_i) =    max_y_i': y_i' · p ≤ B_i u_i(y_-i, y_i')
    ∑_j ∈ M w_ij x_ij =    max_y_i': y_i' · p ≤ B_i∑_j ∈ M w_ij x'_ij
    ∑_j ∈ M w_ij∑_k ∈ N:
     a_kj = a_ij y_kj =   max_y_i': y_i' · p ≤ B_i(∑_j ∈ M w_ijy'_ij +∑_j ∈ M w_ij∑_k ∈ N\{i}:
     a_kj = a_ij y_kj)
    ∑_j ∈ M w_ijy_ij + ∑_j ∈ M w_ij∑_k ∈ N\{i}:
     a_kj = a_ij y_kj =   max_y_i': y_i' · p ≤ B_i(∑_j ∈ M w_ijy'_ij +∑_j ∈ M w_ij∑_k ∈ N\{i}:
     a_kj = a_ij y_kj)
    ∑_j ∈ M w_ijy_ij + ∑_j ∈ M w_ij∑_k ∈ N\{i}:
     a_kj = a_ij y_kj =   max_y_i': y_i' · p ≤ B_i(∑_j ∈ M w_ijy'_ij) +∑_j ∈ M w_ij∑_k ∈ N\{i}:
     a_kj = a_ij y_kj
    ∑_j ∈ M w_ijy_ij =   max_y_i': y_i' · p ≤ B_i∑_j ∈ M w_ijy'_ij
    ũ_̃ĩ(y_i) =    max_y_i': y_i' · p ≤ B_iũ_̃ĩ(y_i')


Also, the total price of y_i is y_i· p in both Γ and Γ̃. Let D̃_̃ĩ(p) be agent i's demand set for prices p in Γ̃: then by the above chain of equations, if y_i ∈ D_i(p, y_-i) for any y_-i, we have y_i ∈D̃_̃ĩ(p). Furthermore, the exact same chain of equations in reverse order shows that if y_i ∈D̃_̃ĩ(p), then y_i ∈ D_i(p, y_-i) for all y_-i.

Since y_i ∈D̃_̃ĩ(p), the allocation  in Γ̃ gives each agent a bundle in her demand set given prices p. Also, because (, p) is an IME of Γ, we have that ∑_i ∈ N y_ij≤ 1, and ∑_i ∈ N y_ij = 1 whenever p_j > 0. Therefore (, p) is a ME of Γ̃.

Now let (, p) be a ME of Γ̃. Since y_i ∈D̃_̃ĩ(p) implies y_i ∈ D_i(p, y_-i), we have that  in Γ gives each agent a bundle in her demand set. By the definition of ME, we have ∑_i ∈ N y_ij≤ 1, and ∑_i ∈ N y_ij = 1 whenever p_j > 0. Therefore (, p) is an IME of Γ.




*


Let Φ'(n,1+ϵ) be the Fisher market with the same agents, goods, and weights as Φ(n,1+ϵ), also with linear utilities. Let (, p) be a ME of Φ'(n,1+ϵ). Then y_i · p = B_i = 1 for all i, and so ∑_j ∈ M p_j =  = n.

We next observe for a Fisher market with linear utilities, any (private) bundle in an agent's demand set maximizes her “bang-per-buck" ratio: w_ij/p_j. To see this, consider agent i moving δ of her budget to a good that does not maximize her bang-per-buck: this would decrease her utility, and so that bundle cannot be in her demand set.

Suppose for sake of contradiction that there exists ℓ where p_ℓ≠ 1. Since ∑_j ∈ M p_j = n, there must exist ℓ where p_ℓ < 1. Let ℓ = min_j ∈ M p_j. Since w_ℓℓ > w_ℓ j for all j≠ℓ, only issue ℓ maximizes agent ℓ's bang-per-buck. Thus there is a single bundle y_i in her demand set, and it consists of her spending her entire budget on issue ℓ. But since p_ℓ < 1 = B_ℓ, agent ℓ purchases more of good ℓ than exists in the supply, and so the market cannot clear. Thus any ME of Φ'(n,1+ϵ) must have p_j = 1 for all j.

Now assume that p_j = 1 for all j. Since for each agent i, w_ii = w > 1 = w_ij for all j≠ i, the only bundle that maximizes agent i's bang-per-buck consists of her spending her entire budget on issue i. Thus the unique ME is (, p) where y_ii = 1 for all i, and y_ij = 0 whenever i≠ j. Furthermore, by Theorem <ref>, (, p) is the unique IME of Φ(n,1+ϵ). 

The Nash welfare of  in Φ(n,1+ϵ) is

    NW() =
    (∏_i ∈ N∑_j∈ M w_ijy_ij)^1/n
    = (∏_i ∈ N 1+ϵ)^1/n = 1+ϵ

Now consider the outcome  where z^j,0 = 0 and z^j,1 = 1 for all j∈ M. Let x_ij be agent i's public bundle, as usual. Then

    NW() 
    =(∏_i ∈ N∑_j∈ M w_ijx_ij)^1/n
    = (∏_i ∈ N∑_j∈ M\{i} 1 · x_ij)^1/n
    = (∏_i ∈ N (n-1) )^1/n = n-1

and therefore

    max_𝐳' NW(𝐳')/NW()≥n-1/1+ϵ





We now present the proofs of Theorems <ref> and <ref>, which state that issue-pricing equilibria can be inefficient for Cobb-Douglas and CES utilities, respectively. 

We first prove a lemma motivated by the following concept. In Section <ref>, we described how for linear utilities, the bundles in an agent's demand set maximize her bang-per-buck, in both the public and private settings. This is not true in general for other utilities, since goods are not independent. However, the same concept still applies: agent i will not spend any money on issue j if there is another issue ℓ where she has a higher marginal utility per dollar spent on issue ℓ. This concept will be made formal by examining ∂(u_i(x_i))∂ x_ij, which is the partial derivative of agent i's utility with respect to x_ij. Although these derivatives may be complicated in general, they are well-behaved for Cobb-Douglas and CES utilities with ρ∈ (-∞, 0) ∪ (0, 1).

We will use this concept to show that for Cobb-Douglas utilities, x_ij p_j = min_ℓ∈ M x_iℓ p_ℓ for any issue j that agent i is spending any money on. For CES utilities with ρ∈ (-∞, 0) ∪ (0, 1), we will show that x_ij^1-ρ p_j = min_ℓ∈ M x_iℓ^1-ρ p_ℓ (note that 1- ρ > 0 since ρ∈ (-∞, 0) ∪ (0, 1)). Using these two properties, the following lemma will imply that x_ij = 1/2 for all j, which allows us to compute the Nash welfare.

lemmaotherUtilitiesEq

Let ( ,p) be an IME of Φ(n,1) and let x_i be agent i's public bundle as induced by . Suppose that there exists c > 0 such that for every issue j that agent i spends any money on, x_ij^c p_j = min_ℓ∈ M x_iℓ^c p_ℓ. Then x_ij = 1/2 for all i and j.



The majority of the proof will be dedicated to showing that for every agent i, there must exist an issue j where x_ij^cp_j ≤ 1/2^c. Suppose for sake of contradiction that there exists an agent i where x_ij^c p_j > 1/2^c for every issue j. 


We first show that there must exist an agent k and issue j where x_kj^c p_j < 1/2. Because (, p) is an IME, all agents exhaust their budgets, so ∑_j ∈ M p_j = ∑_k ∈ N B_k = n. Because |M| = n here, there must exist j ∈ M where p_j ≤ 1. Since x_ij^c p_j > 1/2^c, we have x_ij > 1/2. Let k be any agent where a_kj≠ a_ij: then x_kj < 1/2, and so x_kj^c p_j < 1/2^c.

We know by definition of Φ(n,1), agents i and k agree on all issues other than i and k: a_i ℓ = a_kℓ whenever ℓ∉{i,k}. Thus for all issues ℓ∉{i,k}, x_kℓ^c p_ℓ > 1/2^c > x_kj^c p_j. By assumption, agent k only spends money on issues ℓ which minimize x_k ℓ^c p_ℓ. Thus agent k does not spend money on any issues besides i and k (note that either j = i or j = k). 

Therefore amount of money agent k spends in total is ∑_ℓ∈ M y_kℓp_ℓ = y_kkp_k + y_kip_i. Since agent k exhausts her budget, we have y_kkp_k + y_kip_i = B_k = 1. Thus there must exist ℓ∈{k,i} where y_kℓp_ℓ≥ 1/2. Therefore x_kℓp_ℓ≥ 1/2.

Since a_kk≠ a_ik and a_ki≠ a_ii, we have a_kℓ≠ a_iℓ. Because (, p) is an IME, we have x_iℓ = 1 - x_kℓ. Also, since agent k spends money on issue ℓ, we have x_kℓ^c p_ℓ≤ x_kj^c p_j < 1/2^c by assumption. Therefore

    x_kℓ^c p_ℓ <    1/2^c < x_iℓ^c p_ℓ
    
    x_kℓ^cp_ℓ <    (1-x_kℓ)^c p_ℓ
    
    x_kℓ^c <    (1-x_kℓ)^c
    
    x_kℓ <    (1-x_kℓ)
    
    x_kℓ <    1/2

Since agent k exhausts her budget, we have y_kkp_k + y_kip_i = B_k = 1, and so x_kkp_k + x_kip_i = 1. Thus there must exist ℓ∈{i, k} where y_kℓp_ℓ≥ 1/2. Because x_kℓ^c p_ℓ < 1/2^c, we have x_kℓ^1-c/2^c > x_kℓp_ℓ≥ 1/2. Therefore

    x_kℓ^1-c2^c >   12
    (1/2)^1-c2^c >    12
    
    1 >    1

which is a contradiction. Therefore for every agent i, there exists an issue j where x_ij^c p_j ≤ 1/2^c. 

By assumption, if x_ij^c p_j > min_ℓ∈ M x_iℓ^c p_ℓ, then agent i spends no money on issue j. Since there exists an issue j where x_ij^c p_j ≤ 1/2^c, we have that agent i spends no money on any issue j where x_ij^c p_j > 1/2^c. 

Suppose for sake of contradiction that an agent i and issue j exist where x_ij^c p_j > 1/2^c: then some agent k where a_kj = a_ij is spending money on issue j. But since a_kj = a_ij, we have x_kj^c p_k > 1/2^c, so agent k cannot be spending any money on issue j. Therefore for every agent i and every issue j, x_ij^c p_j ≤ 1/2^c.

Suppose for sake of contradiction that there exists an issue j where p_j ≠ 1. Since ∑_ℓ∈ M p_ℓ = n, there must exist an issue ℓ where p_ℓ > 1. Let k be any other agent other than ℓ: then a_kℓ≠ a_ℓℓ. Since x_kℓ + x_ℓℓ = 1, we have max(x_kℓ, x_ℓℓ) ≥ 1/2. Therefore (max(x_kℓ, x_ℓℓ))^c p_ℓ > 1/2^c, which is a contradiction. Therefore p_j = 1 for all j.

Finally, suppose there exists an agent i and issue j where x_ij≠ 1/2, there must exist an agent k where x_kj > 1/2. Then x_kj^c p_j > 1/2^c, which is again a contradiction. Therefore for every agent i and issue j, x_ij = 1/2.




We are now ready to prove Theorems <ref> and <ref>.

*


Let x_i be agent i's public bundle as induced by . Recall that a Cobb-Douglas utility is given by

    u_i() = u_i(x_i) = ( ∏_j∈ M x_ij^w_ij)^1/∑_j ∈ Mw_ij

which for Φ(n,1), simplifies to

    u_i(x_i) = ( ∏_j∈ M x_ij)^1/n

Thus for all j, we have

    1p_j∂(u_i())∂ x_ij 
    = x_ij^1/n-1p_j n( ∏_ℓ∈ M\{j} 
    	x_iℓ)^1/n
    = 1x_ij p_j n( ∏_ℓ∈ M 
    	x_iℓ)^1/n
    = 1/x_ij p_j nu_i(x_i)

We are going to invoke Lemma <ref> with c = 1. Suppose that there exists an agent i and issues j,ℓ such that agent i is spending on issue j, but x_ij p_j >  x_iℓ p_ℓ. Then

    1/p_j∂(u_i())∂ x_ij < 1/p_ℓ∂(u_i())∂ x_iℓ

Thus there exists some δ > 0 such that if agent i spent δ less on issue j and δ more on issue ℓ, agent i's utility would increase. But x_i is in agent i's demand set, so it cannot be possible for her to increase her utility while staying within her budget. This is a contradiction, so therefore x_ij p_j = min_ℓ∈ M x_iℓ p_ℓ for all i,j.

Therefore by Lemma <ref>, we have x_ij = 1/2 for all i and j. So the Nash welfare of  is

    NW() = (∏_i ∈ N( ∏_j∈ M x_ij)^1/n)^1/n
    = (∏_i ∈ N( ∏_j∈ M 1/2 )^1/n)^1/n
    = (∏_i ∈ N 1/2 )^1/n
    = 1/2

Consider the outcome 𝐳' where x'_ii(𝐳') = 1/n for all i, and x'_ij(𝐳') = n-1n whenever j≠ i. Then

    NW(𝐳') 
    = (∏_i ∈ N( ∏_j∈ M x'_ij)^1/n)^1/n
    = (∏_i ∈ N(1n(n-1n)^n-1)^1/n)^1/n
    = (1n(n-1n)^n-1)^1/n


    = (1n-1(n-1n)^n)^1/n
    = 1(n-1)^1/nn-1n
    = 1 - 1/n(n-1)^1/n

Therefore

    max_𝐳' NW(𝐳')/NW()≥2 - 2/n/(n-1)^1/n






*


Let x_i be agent i's public bundle as induced by . Recall that a CES utility is given by

    u_i() = u_i(x_i) = (∑_j ∈ M w_ij^ρ x_ij^ρ)^1/ρ
    = (∑_j ∈ M x_ij^ρ)^1/ρ

and so we have

    1p_j∂(u_i())∂ x_ij 
    = 1/p_j1ρρ x_ij^ρ - 1(∑_j ∈ M x_ij^ρ)^1/ρ - 1
    = 1x_ij^1 - ρp_j u_i(x_i)^ρ(1/ρ - 1)

This time, we are going to invoke Lemma <ref> with c = 1 - ρ (note that since ρ∈ (-∞, 0) ∪ (0, 1), we have 1 - ρ > 0). Suppose that there exists an agent i and issues j,ℓ such that agent i is spending on issue j, but x_ij^1-ρ p_j >  x_iℓ^1-ρ p_ℓ. Then

    1/p_j∂(u_i())∂ x_ij < 1/p_ℓ∂(u_i())∂ x_iℓ

So again there exists some δ > 0 such that if agent i spent δ less on issue j and δ more on issue ℓ, agent i's utility would increase. But x_i is in agent i's demand set, so this is a contradiction for the same reason as in the previous proof. Thus x_ij p_j = min_ℓ∈ M x_iℓ p_ℓ for all i,j.

Therefore, by Lemma <ref>, we have x_ij = 1/2 for all i and j, so the Nash welfare of  is

    NW() = (∏_i ∈ N( ∑_j∈ M x_ij^ρ)^1/ρ)^1/n
    = (∏_i ∈ N( ∑_j∈ M (1/2)^ρ)^1/ρ)^1/n
    = (∏_i ∈ Nn^1/ρ2)^1/n
    = n^1/ρ2

Consider the outcome 𝐳' where x'_ii(𝐳') = 0 for all i and x'_ij(𝐳') = 1 whenever j≠ i. Then

    NW(𝐳') 
    = (∏_i ∈ N( ∑_j∈ M x_ij^ρ)^1/ρ)^1/n
    = (∏_i ∈ N( ∑_j∈ M\{i} 1 )^1/ρ)^1/n
    = (∏_i ∈ N (n-1)^1/ρ)^1/n = (n-1)^1/ρ

Therefore

    max_𝐳' NW(𝐳')/NW()≥(n-1)^1/ρ/n^1/ρ/2 = 2 ( n-1/n)^1/ρ = 2 (1 - 1/n)^1/ρ











 §.§ Omitted proofs from Section <ref>




*


	By the reduction defined in Section <ref>, the hidden private market has O(n^2m) goods (1 copy of each good for each pair of agents who disagree on the issue) and n agents. 
	
	We next show the  is being run correctly, i.e., the sequence of prices (p^0, p^1, p^2...), alongside some demands (y^t_i ∈ D_i^R(p^t)) converges to a δ-equilibrium. This is not trivial since  is run with a detour through the PDM. By Corollary <ref>, given prices p∼ R(Γ) and a bundle y_i ∼Γ, y_i ∈ D_i((p))  R(y_i) ∈ D_i^R(p). Thus at each step, p^t+1 is being calculated by g_ based on valid demands in D_i^R(p^t), so the sequence of prices (p^0, p^1, p^2...) converges to a δ-equilibrium. Then, by supposition, there exist demands y ∼ R(Γ) at time T such that (𝐲, p^T) ∼ R(Γ) form a δ-equilibrium in the hidden Fisher market, for T = O(κ(n^2m,n,δ)). 
	
	Recall Theorem <ref>: (, p) is a Fisher market equilibrium if and only if ((), (p)) is a PME. The rest of the proof involves showing that Theorem <ref> holds for approximate equilibria as well, as defined. Recall that (y_i)_j = min_k ∈ N:
 a_ij≠ a_kj y_i (ikj) ∀ j∈ M, and (p)_ij = ∑_k ∈ N:
 a_ij≠ a_kj p_(ikj) ∀ i∈ N, j∈ M.






We claim ((y), (p^t)) forms a 3δ-PME:
	
		
  * y_i ∈ D_i^R(p^t) (y_i) ∈ D_i((p^t)). (Lemma <ref>)
		
  * We define = (z^1...z^m) ∈ [0,1]^m× 2 as follows, analogously to Equation (<ref>) in the proof of Theorem <ref>[In the proof of Theorem <ref>, 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.]:
		
    z^j,0 =    max_i∈ N: a_ij = 0(y_i)_j
    
    		z^j,1 =    max(1 - z^j,0, 0)
 Then, ∀ j∈ M,
		
			
  * z^j,0 + z^j,1≤ 1+δ follows from the definition and from y part of a δ-equilibrium of a Fisher market.
			
  * For all i∈ N, (y_i)_j ≤ z^j, a_ij+ δ follows from Equations (<ref>)-(<ref>), with 1 replaced with 1+δ and the = in line (<ref>) replaced with ≤. Finally,
			
    (p)_ij > nδ   ∃k̃ s.t.  p_(ikj) > δ
        y_i(ik̃j) + y_k̃(ik̃j) > 1 - δ   (Condition <ref> of Fisher δ-equilibrium)

			By Lemma <ref>, p_(ik̃j) > 0  y_i(ik̃j) = min_k ∈ N:
 a_ij≠ a_k̃j y_i (ik̃j) = (y_i)_j, and y_k̃(ik̃j) = (y_k̃)_j. Then
			
    (y_i)_j    > 1- (y_k̃)_j - δ
       > 1-z^j,a_k̃j - 2δ   (First part of Condition (b)
       > z^j,a_ij - 3δ   definition of z^j,a_ij)

			Thus, (p)_ij > nδ(y_i)_j> z^j,a_ij - 3δ
		
	








§ GENERAL TÂTONNEMENT WITH ASYMPTOTIC CONVERGENCE IN FISHER MARKETS


The prior work discussed in Section <ref> established deterministic tâtonnements with polynomial time convergence rates only for certain classes of utility functions, or for those that converge to weak equilibria. However, we would like a general PDM converges for a wider class of utilities (in particular, linear utilities). To achieve this, we sacrifice convergence in polynomial time (or any characterization of convergence rates), which has been the primary focus on prior work such as <cit.>[Those works take great care to show conditions analogous to strong convexity or Lipschitz continuity of the gradient in the cases of interest.]. In this section, we present a discrete stochastic gradient descent style tâtonnement for all Fisher markets that result from PDMs with EG utility functions through the reduction. This can then be lifted through Theorem <ref> to yield a general PDM .

This section broadly follows the gradient descent framework for Fisher market tâtonnements from <cit.>, and the can be seen as an asymptotic discretization of their continuous time . The tâtonnement operates on the dual of the EG convex program, which is a function of the prices, and whose gradient is the excess demand (Lemma <ref>). We first establish that there exists a bounded, convex region Π in which demands are bounded, with p^*∈Π[It is well known that the primal objective function is strictly concave, and so p^*, the optimal dual solution, is unique.]. We finish the proof with a standard SGD convergence technique, Lemma <ref>. 


 Let ϕ(p) be the objective of the dual of EG convex program. We use D^R to denote demands as the demands are in a Fisher market R(Γ) that is constructed from PDM Γ. The following lemma from <cit.> establishes that ϕ(p) is itself a convex function whose gradient is the excess demand.   
 


	∇ϕ(p) = 1 - ∑_i D^R_i(p_i) 

Note that ϕ(p) refers to the set of sub-gradients, and D^R_i(p_i) to the set of demands. Even when demands at a given price are not unique (such as with linear utilities), each combination of demands yields a sub-gradient of the dual objective function. 

Before being able to apply a canonical gradient descent convergence theorem, we need to establish that there exists a bounded, convex set which contains the optimal price p^* in its interior. We construct such a set next.


 ∃Π⊂_+^m bounded and convex s.t. p^* ∈maxϕ(p)⊂Π, and that ∀ p∈Π, ∀ i, D^R_i(p) < ∞.  
	

	We claim p^* ∈ [0,2]^m in our setting. Let y_i∈ D^R_i(p^*_i), and thus p^*_j y_ij≤ B_i = 1 ∀ j. By Fisher market equilibrium conditions, p^*_j>0 ∑_i y_ij = 1. In our setting, y_ij>0 for at most two distinct i. Thus, ∃ i s.t. y_ij≥1/2 p^*_j ≤ 2. 
	
	Let p_min be any value such that 0 < p_min < min_{j:p^*_j>0} p^*_j. Then, let Π = [p_min^1, 2] ×…× [p_min^m, 2], where p_min^j = 
	0     p^*_j=0

	p_min   else. Π as defined has the desired properties.
	 


Throughout, we use [·]_𝒳 denote the projection onto a set 𝒳.
We will also use the following stochastic gradient descent convergence lemma.

	Consider a convex function f on a non-empty bounded closed convex set 𝒳⊂^m, and use [·]_𝒳 to designate the projection operator. Starting with some x_0∈𝒳, consider the SGD update rule x_t = [x_t-1 - η_t (∇ f(x_t) + z_t + e_t)]_𝒳, where z_t is a zero-mean random variable and e_t is a constant. Let _t[·] be the conditional expectation given ℱ_t, the σ-field generated by x_0,x_1,…,x_t. If
	
    f(·) has a unique minimizer x^* ∈𝒳
       η_t > 0, ∑ _t η_t = ∞, ∑ _t η_t^2 < ∞
       ∃ C_1 ∈ < ∞ s.t. ∇ f(x)_2 ≤ C_1,∀  x ∈𝒳
       ∃ C_2 ∈ < ∞ s.t. _t[z_t^2] ≤ C_2, ∀  t 
       ∃ C_3 ∈ < ∞ s.t. e_t_2 ≤ C_3,∀  t 
       ∑_tη_t e_t < ∞ w.p. 1

	Then x_t → x^* w.p. 1 as t →∞.  
	













We can now construct a stochastic tâtonnement for a Fisher Market R(Γ) that is constructed from PDM Γ when agents have any EG utility function in the PDM, as ℋ-nested leontief utility functions remain EG utility functions.













	Suppose p^* ∈minϕ(p). Then, ∃ y = (y_1 … y_n) s.t. y_i ∈ D^R_i (p^*), (y, p^*) is a ME. 
	

Follows directly from Part 2 of Lemma 5 in <cit.>, that max_x≥0 L(x, p) ⊆ D^R(p). The ME (x^*, p^*) is such that x^* ∈max_x≥0 L(x, p^*) ⊆ D^R(p^*). 




 Let agents i in the PDM Γ have utilities u_i∈ℋ that are concave, continuous, non-decreasing, non-constant, and homogeneous of degree 1. Then there exists a stochastic gradient descent-style tâtonnement for which, as t→∞, p^t → p^*, where p^* ∈minϕ(p), and ∃ x s.t. x_i ∈ D_i(p^*) and (x, (p^*)) is a PME.	


	
	Construct a Fisher market R(Γ) through the reduction.
	
	Let  be the following descent in the constructed market. Start with prices p^0∈Π, where Π as defined in Lemma <ref>. Update prices using the rule p^t+1 = [p^t - η_t(1 - ∑_i D̃^R_i(p^t_i))]_Π, for η_t = 1/t, and D̃^R_i(p) = y_i,t + b_i,t + z_i,t, for some y_i,t∈ D^R_i(p^t). Assume z_i,t a zero-mean random variable and b_i,t a constant that follow the conditions of Lemma <ref>. 
	
	By Lemma <ref>, the implied utility functions still yield Eisenberg-Gale markets and by Lemma <ref>, ∇ϕ(p) = 1 - ∑_i D^R_i(p). By Lemma <ref>, ∃ C<∞ s.t. ∇ϕ(p) < C, ∀ p∈Π. Convergence to prices p^* ∈minϕ(p) follows from Lemma <ref>. By Lemma <ref>, ∃y, y_i ∈ D^R_i (p^*) s.t. (y, p^*) is a ME in the Fisher market. Thus,  converges asymptotically to a ME. 
	
	
	 By Theorem <ref>,  can be lifted to create a () in the PDM that converges asymptotically to a PME.  
	









Note that Π is not known a priori. However, it can be approximated during the gradient descent without affecting convergence: for example, if at any point demand goes to infinity, backtrack and impose a minimum price. Then, if demand goes to 0 with a positive price, lower this minimum price.






Theorem <ref> and Theorem <ref> together create a tâtonnement with asymptotic convergence for Public Decision Markets for general concave, continuous, non-constant, non-decreasing, and homogeneous of degree 1 utility functions. 






	
	

