skip to main content


Title: Learning Competitive Equilibria in Noisy Combinatorial Markets
We present a methodology to robustly estimate the competitive equilibria (CE) of combinatorial markets under the assumption that buyers do not know their precise valuations for bundles of goods, but instead can only provide noisy estimates. We first show tight lower- and upper-bounds on the buyers' utility loss, and hence the set of CE, given a uniform approximation of one market by another. We then present two probably-approximately-correct algorithms for learning CE with finite-sample guarantees. The first is a baseline and the second leverages a connection between the first welfare theorem of economics and uniform approximations to adaptively prune value queries when it is determined that they are provably not part of a CE. Extensive experimentation shows that pruning achieves better estimates than the baseline with far fewer samples.  more » « less
Award ID(s):
1761546
NSF-PAR ID:
10290824
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
AAMAS Conference proceedings
ISSN:
2523-5699
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Atmospheric rivers (AR) are critically important to water resources management along the US west coast, driving variability in both droughts and floods across the region. Inter‐annual variability of ARs is well documented in the instrumental record back to the mid‐twentieth century, but long‐term variations in the frequency and landfall location of ARs along the US west coast are poorly understood due to limited records. This limitation impedes the ability to contextualize emerging trends and projections of AR activity. Here we use station‐based records of daily precipitation and tree‐ring records to present novel, spatially explicit estimates of daily AR occurrences in the first half of the twentieth century and annual AR counts over the last 600 years. First, we use neural networks and daily precipitation across Western North America to classify the daily occurrence of AR landfalls in three regions along the US west coast during the cold season back to 1916 CE. Then, we reconstruct the annual frequency of AR landfalls in those same regions back to 1400 CE using a gridded, tree‐ring based reconstruction of the standardized precipitation index and a Poisson regression framework. The skillful reconstruction of daily and annual AR occurrences provides previously unavailable estimates of AR landfall variability and highlights new peaks in AR activity and modes of low‐frequency variability prior to the instrumental record. Our reconstructions suggest that the average latitude of AR landfall has varied considerably on multi‐decadal scales over the last 600 years, but without any discernible trends beyond this quasi‐oscillatory behavior.

     
    more » « less
  2. ABSTRACT

    It has long been speculated that jet feedback from accretion on to the companion during a common envelope (CE) event could affect the orbital evolution and envelope unbinding process. We present global 3D hydrodynamical simulations of CE evolution (CEE) that include a jet subgrid model and compare them with an otherwise identical model without a jet. Our binary consists of a 2-M⊙ red giant branch primary and a 1- or 0.5-M⊙ main sequence (MS) or white dwarf (WD) secondary companion modelled as a point particle. We run the simulations for 10 orbits (40 d). Our jet model adds mass at a constant rate $\dot{M}_\mathrm{j}$ of the order of the Eddington rate, with maximum velocity vj of the order of the escape speed, to two spherical sectors with the jet axis perpendicular to the orbital plane. We explore the influence of the jet on orbital evolution, envelope morphology and envelope unbinding, and assess the dependence of the results on the jet mass-loss rate, launch speed, companion mass, opening angle, and accretion rate. In line with our theoretical estimates, jets are choked around the time of first periastron passage and remain choked thereafter. Subsequent to choking, but not before, jets efficiently transfer energy to bound envelope material. This leads to increases in unbound mass of up to $\sim 10{{\ \rm per\ cent}}$, as compared to the simulations without jets. We also estimate the cumulative effects of jets over a full CE phase, finding that jets launched by MS and WD companions are unlikely to dominate envelope unbinding.

     
    more » « less
  3. We study stationary equilibria in a sequential auction setting. A seller runs a sequence of standard first-price or second-price auctions to sell an indivisible object to potential buyers. The seller can commit to the rule of the auction and the reserve price of the current period but not to reserve prices of future periods. We prove the existence of stationary equilibria and establish a uniform Coase conjecture—at any point in time and in any stationary equilibrium, the seller’s profit from running sequential auctions converges to the profit of running an efficient auction as the period length goes to zero. 
    more » « less
  4. We present Descending from Stochastic Clustering Variance Regression (DiSCoVeR) (https://www.github.com/sparks-baird/mat_discover), a Python tool for identifying and assessing high-performing, chemically unique compositions relative to existing compounds using a combination of a chemical distance metric, density-aware dimensionality reduction, clustering, and a regression model. In this work, we create pairwise distance matrices between compounds via Element Mover's Distance (ElMD) and use these to create 2D density-aware embeddings for chemical compositions via Density-preserving Uniform Manifold Approximation and Projection (DensMAP). Because ElMD assigns distances between compounds that are more chemically intuitive than Euclidean-based distances, the compounds can then be clustered into chemically homogeneous clusters via Hierarchical Density-based Spatial Clustering of Applications with Noise (HDBSCAN*). In combination with performance predictions via Compositionally-Restricted Attention-Based Network (CrabNet), we introduce several new metrics for materials discovery and validate DiSCoVeR on Materials Project bulk moduli using compound-wise and cluster-wise validation methods. We visualize these via multi-objective Pareto front plots and assign a weighted score to each composition that encompasses the trade-off between performance and density-based chemical uniqueness. In addition to density-based metrics, we explore an additional uniqueness proxy related to property gradients in DensMAP space. As a validation study, we use DiSCoVeR to screen materials for both performance and uniqueness to extrapolate to new chemical spaces. Top-10 rankings are provided for the compound-wise density and property gradient uniqueness proxies. Top-ranked compounds can be further curated via literature searches, physics-based simulations, and/or experimental synthesis. Finally, we compare DiSCoVeR against the naive baseline of random search for several parameter combinations in an adaptive design scheme. To our knowledge, this is the first time automated screening has been performed with explicit emphasis on discovering high-performing, novel materials. 
    more » « less
  5. Vidick, T. (Ed.)
    We study auctions for carbon licenses, a policy tool used to control the social cost of pollution. Each identical license grants the right to produce a unit of pollution. Each buyer (i.e., firm that pollutes during the manufacturing process) enjoys a decreasing marginal value for licenses, but society suffers an increasing marginal cost for each license distributed. The seller (i.e., the government) can choose a number of licenses to put up for auction, and wishes to maximize the societal welfare: the total economic value of the buyers minus the social cost. Motivated by emission license markets deployed in practice, we focus on uniform price auctions with a price floor and/or price ceiling. The seller has distributional information about the market, and their goal is to tune the auction parameters to maximize expected welfare. The target benchmark is the maximum expected welfare achievable by any such auction under truth-telling behavior. Unfortunately, the uniform price auction is not truthful, and strategic behavior can significantly reduce (even below zero) the welfare of a given auction configuration. We describe a subclass of “safe-price” auctions for which the welfare at any Bayes-Nash equilibrium will approximate the welfare under truth-telling behavior. We then show that the better of a safeprice auction, or a truthful auction that allocates licenses to only a single buyer, will approximate the target benchmark. In particular, we show how to choose a number of licenses and a price floor so that the worst-case welfare, at any equilibrium, is a constant approximation to the best achievable welfare under truth-telling after excluding the welfare contribution of a single buyer. 
    more » « less