skip to main content

Explore Research Products in the NSF-PAR

Title: Markets for Public Decision-Making
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.  more » « less
Award ID(s):
1637418
NSF-PAR ID:
10139081
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Web and Internet Economics - 14th International Conference
Page Range / eLocation ID:
445
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ( , Conference of Web and Internet Economics)
    null (Ed.)
    Public goods are often either over-consumed in the absence of regulatory mechanisms, or remain completely unused, as in the Covid-19 pandemic, where social distance constraints are enforced to limit the number of people who can share public spaces. In this work, we plug this gap through market based mechanisms designed to efficiently allocate capacity constrained public goods. To design these mechanisms, we leverage the theory of Fisher markets, wherein each agent in the economy is endowed with an artificial currency budget that they can spend to avail public goods. While Fisher markets provide a strong methodological backbone to model resource allocation problems, their applicability is limited to settings involving two types of constraints - budgets of individual buyers and capacities of goods. Thus, we introduce a modified Fisher market, where each individual may have additional physical constraints, characterize its solution properties and establish the existence of a market equilibrium. Furthermore, to account for additional constraints we introduce a social convex optimization problem where we perturb the budgets of agents such that the KKT conditions of the perturbed social problem establishes equilibrium prices. Finally, to compute the budget perturbations we present a fixed point scheme and illustrate convergence guarantees through numerical experiments. Thus, our mechanism, both theoretically and computationally, overcomes a fundamental limitation of classical Fisher markets, which only consider capacity and budget constraints. 
    more » « less
  2. ; ; ( , Lecture notes in computer science)
    We consider information design in spatial resource competition, motivated by ride sharing platforms sharing information with drivers about rider demand. Each of N co-located agents (drivers) decides whether to move to another location with an uncertain and possibly higher resource level (rider demand), where the utility for moving increases in the resource level and decreases in the number of other agents that move. A principal who can observe the resource level wishes to share this information in a way that ensures a welfare-maximizing number of agents move. Analyzing the principal’s information design problem using the Bayesian persuasion framework, we study both private signaling mechanisms, where the principal sends personalized signals to each agent, and public signaling mechanisms, where the principal sends the same information to all agents. We show: 1) For private signaling, computing the optimal mechanism using the standard approach leads to a linear program with 2 N variables, rendering the computation challenging. We instead describe a computationally efficient two-step approach to finding the optimal private signaling mechanism. First, we perform a change of variables to solve a linear program with O(N^2) variables that provides the marginal probabilities of recommending each agent move. Second, we describe an efficient sampling procedure over sets of agents consistent with these optimal marginal probabilities; the optimal private mechanism then asks the sampled set of agents to move and the rest to stay. 2) For public signaling, we first show the welfare-maximizing equilibrium given any common belief has a threshold structure. Using this, we show that the optimal public mechanism with respect to the sender-preferred equilibrium can be computed in polynomial time. 3) We support our analytical results with numerical computations that show the optimal private and public signaling mechanisms achieve substantially higher social welfare when compared with no-information and full-information benchmarks. 
    more » « less
  3. ; ( , Journal of Artificial Intelligence Research)
    We consider the problem of fairly allocating a set of indivisible goods among n agents. Various fairness notions have been proposed within the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously, all while satisfying a standard economic concept of efficiency, Pareto optimality. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. We address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. Our techniques are based on a market interpretation of a fractional max NSW allocation. We present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a market equilibrium into an integral allocation in a way that provides most of the fairness properties of an integral max NSW allocation. 
    more » « less
  4. ; ( , Improving Nash Social Welfare Approximations)

    We consider the problem of fairly allocating a set of indivisible goods among n agents. Various fairness notions have been proposed within the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the 'unreasonable' fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously, all while satisfying a standard economic concept of efficiency, Pareto optimality. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. We address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. Our techniques are based on a market interpretation of a fractional max NSW allocation. We present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a market equilibrium into an integral allocation that provides most of the fairness properties of an integral max NSW allocation. 

     
    more » « less
  5. ; ; ; ; ; ; ; ( , NSF Workshop Reports)
    null (Ed.)
    On August 2-3, 2021, the Thomas J. O’Keefe Institute for Sustainable Supply of Strategic Minerals at Missouri University of Science and Technology (Missouri S&T) hosted the NSF-funded virtual workshop ‘Resilient Supply of Critical Minerals’. The workshop was convened via Zoom and attracted 158 registrants, including 108 registrants from academia (61 students), 30 registrants from government agencies, and 20 registrants from the private sector. Four topical sessions were covered: A. Mineral Exploration and Source Diversification. B. Supply Chain and Policy Issues. C. Improving Mineral Recycling and Reprocessing Technologies. D. Technological Alternatives to Critical Minerals. Each topical session was composed of two keynote lectures and followed by a breakout session that was designed to identify promising pathways towards increasing critical supply chain resilience in the United States. During each breakout session, participants were asked to address five questions: Q1. What are the roadblocks that affect the resilient supply of critical minerals? Q2. What are the most pressing research needs? Q3. What opportunities can lead to the fastest and biggest impact? Q4. What skills training is required to meet future workforce demands? Q5. What other questions should be asked, but are commonly overlooked? Several issues that limit critical mineral supply chain resilience in the United States were identified and discussed in all breakout sessions, including: 1. Insufficient understanding of domestic critical minerals resources. To address this issue, workshop participants highlighted the need for (i) more geologic research to identify new and evaluate existing resources; and (ii) a qualitative and quantitative assessment of critical minerals that may be recovered as by/co-products from existing production streams. 2. Technical limitations of current mineral processing and recycling technologies. To address this issue, workshop participants highlighted the need for (i) innovative mineral processing technologies, including more environmentally friendly chemicals/solvents, and (ii) automated recycling technologies for appliances and e-waste. Participants also highlighted the need for a centralized and simplified way to collect recyclable materials, and incentives for the public to participate in recycling. 3. Long permitting processes for mining and mineral processing operations, with often unpredictable outcomes. To address this issue, workshop participants suggested the development of new critical mineral focused policies with faster processing times and more transparent / predictable decision-making processes. 4. The negative public image of mining and mineral processing operations. To address this issue, workshop participants suggested to design public outreach / education initiatives and to include local communities into decision-making processes. 5. Limited availability of a critical mineral workforce. To address this issue, workshop participants suggested an increased focus on critical mineral specific skill training in higher education institutions, and advanced training of the existing workforce. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email