An official website of the United States government
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
Markets for Efficient Public Good Allocation with Social Distancing
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
- Award ID(s):
- 1454737
- PAR ID:
- 10209478
- Date Published:
- Journal Name:
- Conference of Web and Internet Economics
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Global product platforms can reduce production costs through economies of scale and learning but may decrease revenues by restricting the ability to customize for each market. We model the global platforming problem as a Nash equilibrium among oligopolistic competing firms, each maximizing its profit across markets with respect to its pricing, design, and platforming decisions. We develop and compare two methods to identify Nash equilibria: (1) a sequential iterative optimization (SIO) algorithm, in which each firm solves a mixed-integer nonlinear programming problem globally, with firms iterating until convergence; and (2) a mathematical program with equilibrium constraints (MPEC) that solves the Karush Kuhn Tucker conditions for all firms simultaneously. The algorithms’ performance and results are compared in a case study of plug-in hybrid electric vehicles where firms choose optimal battery capacity and whether to platform or differentiate battery capacity across the US and Chinese markets. We examine a variety of scenarios for (1) learning rate and (2) consumer willingness to pay (WTP) for range in each market. For the case of two firms, both approaches find the Nash equilibrium in all scenarios. On average, the SIO approach solves 200 times faster than the MPEC approach, and the MPEC approach is more sensitive to the starting point. Results show that the optimum for each firm is to platform when learning rates are high or the difference between consumer willingness to pay for range in each market is relatively small. Otherwise, the PHEVs are differentiated with low-range for China and high-range for the US.more » « less
-
Advanced Air Mobility (AAM) operations are expected to transform air transportation while challenging current air traffic management practices. By introducing a novel market-based mechanism, we address the problem of on-demand allocation of capacity-constrained airspace to AAM vehicles with heterogeneous and private valuations. We model airspace and air infrastructure as a collection of contiguous regions (or sectors) with constraints on the number of vehicles that simultaneously enter, stay, or exit each region. Vehicles request access to airspace with trajectories spanning multiple regions at different times. We use the graph structure of our airspace model to formulate the allocation problem as a path allocation problem on a time-extended graph. To ensure that the cost information of AAM vehicles remains private, we introduce a novel mechanism that allocates each vehicle a budget of “air-credits” (an artificial currency) and anonymously charges prices for traversing the edges of the time-extended graph. We seek to compute a competitive equilibrium that ensures that: (i) capacity constraints are satisfied, (ii) a strictly positive resource price implies that the sector capacity is fully utilized, and (iii) the allocation is integral and optimal for each AAM vehicle given current prices, without requiring access to individual vehicle utilities. However, a competitive equilibrium with integral allocations may not always exist. We provide sufficient conditions for the existence and computation of a fractional-competitive equilibrium, where allocations can be fractional. Building on these theoretical insights, we propose a distributed, iterative, two-step algorithm that: (1) computes a fractional competitive equilibrium, and (2) derives an integral allocation from this equilibrium. We validate the effectiveness of our approach in allocating trajectories for the emerging urban air mobility service of drone delivery.more » « less
-
We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question posed in the literature. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the complexity class continuous local search ([Formula: see text]; i.e., the intersection of polynomial local search ([Formula: see text]) and polynomial parity arguments on directed graphs ([Formula: see text])). For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have capped linear (also known as budget-additive) valuations. Finally, we significantly improve the approximation hardness for additive valuations to [Formula: see text]. Funding: J. Garg was supported by the National Science Foundation [Grant CCF-1942321 (CAREER)]. M. Hoefer was supported by Deutsche Forschungsgemeinschaft [Grants Ho 3831/5-1, Ho 3831/6-1, and Ho 3831/7-1].more » « less
-
Abstract This article studies equilibrium dynamics in consumer durable goods markets after aggregate credit shocks. We introduce two novel features into a general-equilibrium model of durable consumption with heterogeneous households facing idiosyncratic income risk and borrowing constraints: (1) indivisible durable goods are vertically differentiated in their quality and (2) trade on secondary markets at market-clearing prices, with households endogenously choosing when to trade or scrap their durables. The model highlights a new transmission mechanism for macroeconomic shocks and successfully matches several empirical patterns that we document using data on U.S. car markets around the Great Recession. After a tightening of the borrowing limit, debt-constrained households postpone the decision to scrap and upgrade their low-quality cars, which depresses mid-quality car prices. In turn, this effect reduces wealthy households’ incentives to replace their mid-quality cars with high-quality ones, thereby decreasing new-car sales. We further use our framework to evaluate targeted fiscal stimulus policies such as the Car Allowance Rebate System in 2009 (“Cash for Clunkers”).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
