Search for: All records

Award ID contains: 1901403

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. We develop a versatile methodology for multidimensional mechanism design that incorporates side information about agents to generate high welfare and high revenue simultaneously. Side information sources include advice from domain experts, predictions from machine learning models, and even the mechanism designer’s gut instinct. We design a tunable mechanism that integrates side information with an improved Vickrey–Clarke–Groves–like mechanism based on weakest types, which are agent types that generate the least welfare. We show that our mechanism, when its side information is of high quality, generates welfare and revenue competitive with the prior-free total social surplus, and its performance decays gracefully as the side information quality decreases. We consider a number of side information formats including distribution-free predictions, predictions that express uncertainty, agent types constrained to low-dimensional subspaces of the ambient type space, and the traditional setting with known priors over agent types. In each setting, we design mechanisms based on weakest types and prove performance guarantees. History: This paper has been accepted for the Mathematics of Operations Research Special Issue on Market Design. Funding: This work was supported by Office of Naval Research and the Vannevar Bush Faculty Fellowship [Grant ONR N00014-23-1-2876], the Army Research Office [Award W911NF2210266], the Simons Foundation [Award MPS-SICS-00826333], the National Science Foundation [Grants CCF-1733556, CCF-1910321, IIS-1901403, RI-1901403, RI-2312342, and SES-1919453], the National Institutes of Health [Grant A240108S001], and the Defense Advanced Research Projects Agency [Grant HR00112020003]. 
    more » « less
    Free, publicly-accessible full text available May 12, 2027
  2. We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). We make two primary contributions. First, we introduce a new algorithm for computing optimal equilibria in all three notions. Its runtime depends exponentially only on a parameter related to the information structure of the game. We also prove a fundamental complexity gap between NFCCE and the other two concepts. Second, we propose a two-sided column generation approach for use when the runtime or memory usage of the previous algorithm is prohibitive. Our algorithm improves upon an earlier one-sided approach by means of a new decomposition of correlated strategies which allows players to reoptimize their sequence-form strategies with respect to correlation plans which were previously added to the support. Experiments show that our techniques outperform the prior state of the art for computing optimal general-sum correlated equilibria. Funding: This work was supported by National Institutes of Health [Grant A240108S001]; Vannevar Bush Faculty Fellowship [Grant ONR N00014-23-1-2876]; National Science Foundation [Grants CCF-173355, IIS-190140, RI-1901403, RI-2312342]; and Army Research Office [Grants W911NF2010081, W911NF2210266]. 
    more » « less
    Free, publicly-accessible full text available January 1, 2027
  3. We consider the problem of computing stationary points in min-max optimization, with a focus on the special case of Nash equilibria in (two-)team zero-sum games. We first show that computing ϵ-Nash equilibria in 3-player adversarial team games—wherein a team of 2 players competes against a single adversary— is CLS-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from symmetric ϵ-Nash equilibria in symmetric, identical-payoff, two-player games, by suitably leveraging the adversarial player so as to enforce symmetry—without disturbing the structure of the game. In particular, the class of instances we construct comprises solely polymatrix games, thereby also settling a question left open by Hollender, Maystre, and Nagarajan (2024). Moreover, we establish that computing symmetric (first-order) equilibria in symmetric min-max optimization is PPAD-complete, even for quadratic functions. Building on this reduction, we show that computing symmetric ϵ-Nash equilibria in symmetric, 6-player (3 vs. 3) team zero-sum games is also PPAD-complete, even for ϵ = poly(1/n). As a corollary, this precludes the existence of symmetric dynamics—which includes many of the algorithms considered in the literature— converging to stationary points. Finally, we prove that computing a non-symmetric poly(1/n)-equilibrium in symmetric min-max optimization is FNP-hard. 
    more » « less
    Free, publicly-accessible full text available December 1, 2026
  4. Introduction:The current US adult heart allocation policy has several limitations, including being heavily focused on device utilization rather than individual patient illness severity, high number of exceptions, not considering donor-patient match quality, and not incorporating individualized predicted waitlist and post-transplant survival for prioritization. Research question:The hypothesis of this study is that using artificial intelligence and operations research techniques, a better optimized heart allocation policy can be developed that would result in an increase in aggregate number of years of life gained on a national level compared to the current policy. Approach:This study utilizes national data from UNOS. A new simulator was developed that resamples that data, enabling the evaluation and comparison of various allocation policies. The current allocation policy was evaluated using the simulator. A myopic policy was then developed that allocates each incoming heart to the patient who maximizes the number of predicted years gained by the transplant. This gain was computed as the difference between predicted survival years with the transplant and the predicted survival years without it. These predictors were trained using Cox regression. Two more sophisticated policies were developed. One accounts for the dynamic nature of the allocation process through the use of potentials, where each patient's potential is the patient's expected contribution to life year gains in the future, and is learned via simulations. The other considers batching together a small number of donors to patients that maximize life years gained to further reduce myopia. Results:The myopic policy increases life years gained by (an average of) 50.4% over thestatus quopolicy. The use of potentials further increases the gain by 1.6% compared to the myopic policy. The use of batching (even just batches of size 5 within a maximum duration of 48 hours) further increases the gain by 2.2% compared to the myopic policy (Table 1). Also, gains in life years would increase by 22.9% if centers would not reject offers (Figure 1, left). Furthermore, up to 33.2% gain in life years would be achieved if the maximum allowable geographic distance increased from 500 to 2,500 nautical miles (NM), with diminishing returns (Figure 1, right). Conclusions:These artificial intelligence techniques can lead to considerable improvements in years of life gained with heart transplants on a national scale. 
    more » « less
  5. Sequence-independent lifting is a procedure for strengthening valid inequalities of an integer program. We generalize the sequence-independent lifting method of Gu, Nemhauser, and Savelsbergh (GNS lifting) for cover inequalities and correct an error in their proposed generalization. We obtain a new sequence-independent lifting technique---piecewise-constant (PC) lifting---with a number of important properties. We derive a broad set of sufficient conditions under which PC lifting yields facets---the first characterization of facet-defining sequence-independent liftings that are efficiently computable from the underlying cover. Finally, we demonstrate via experiments that PC lifting can be a useful alternative to GNS lifting. We test PC lifting atop a number of novel cover inequality generation routines, which prove to be effective in experiments with CPLEX. PC lifting delivers strong numerical properties making it practically relevant for integer programming solvers. 
    more » « less
  6. The paper studies the application of first-order methods to the problem of computing equilibria of large-scale extensive-form games. It introduces a new weighted entropy-based distance-generating function for instantiating first-order methods. The new function achieves significantly better strong-convexity properties than existing weight schemes for the dilated entropy while maintaining the same easily implemented closed-form proximal mapping as the prior state of the art. The paper then generalizes our new entropy distance function, as well as the whole class of dilated distance functions, to the scaled extension operator. This yields the first efficiently computable distance-generating function for the decision polytopes capturing correlated and team solution concepts for extensive-form games. By instantiating first-order methods with these regularizers, several new results are achieved, such as the first method for computing ex ante correlated team equilibria with a guaranteed 1/T rate of convergence and efficient proximal updates. 
    more » « less
  7. We study the problem of computing an approximate Nash equilibrium of a game whose strategy space is continuous without access to gradients of the utility function.Lack of access to gradients is common in reinforcement learning settings, where the environment is treated as a black box, as well as equilibrium finding in mechanisms such as auctions, where the mechanism's payoffs are discontinuous in the players' actions.To tackle this problem, we turn to zeroth-order optimization techniques that combine pseudo-gradients with equilibrium-finding dynamics.Specifically, we introduce a new technique that requires a number of utility function evaluations per iteration that is constant rather than linear in the number of players.It achieves this by performing a single joint perturbation on all players' strategies, rather than perturbing each one individually.This is very important for many-player games, especially when the utility function is expensive to compute in terms of wall time, memory, money, or other resources.We evaluate our approach on various games, including auctions, which have important real-world applications.Our approach yields a dramatic improvement in performance in terms of the wall time required to reach an approximate Nash equilibrium. 
    more » « less
  8. Φ-equilibria—and the associated notion of Φ-regret—are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of deviations Φ begets stronger notions of rationality. Recently, Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC ’24) settled the existence of efficient algorithms when Φ contains only linear maps under a general, 𝑑-dimensional convex constraint set X. In this paper, we significantly extend their work by resolving the case where Φ is 𝑘-dimensional; degree-ℓ polynomials constitute a canonical such example with 𝑘 = 𝑑 𝑂 (ℓ) . In particular, we obtain two main positive results: i) a poly(𝑛, 𝑑, 𝑘, log(1/𝜖))-time algorithm for computing 𝜖-approximate Φ-equilibria in 𝑛-player multilinear games, and ii) an efficient online algorithm that incurs average Φ-regret at most 𝜖 using poly(𝑑, 𝑘)/𝜖 2 rounds. We also show nearly matching—up to constant factors in the exponents—lower bounds parameterized by 𝑘 in the online learning setting. We thus obtain for the first time a family of deviations that captures the learnability of Φ-regret. At the heart of our approach is a polynomial-time algorithm for computing an expected fixed point of any 𝜙 : X → X—that is, a distribution 𝜇 ∈ Δ(X) such that E𝒙∼𝜇 [𝜙 (𝒙) − 𝒙] ≈ 0—based on the seminal ellipsoid against hope (EAH) algorithm of Papadimitriou and Roughgarden (JACM ’08). In particular, our algorithm for computing Φ-equilibria is based on executing EAH in a nested fashion—each step of EAH itself being implemented by invoking a separate EAH call. The full version of the paper is available at arxiv.org/pdf/2502.18582. 
    more » « less
  9. Planning at execution time has been shown to dramatically improve performance for AI agents. A well-known family of approaches to planning at execution time in single-agent settings and twoplayer zero-sum games are AlphaZero and its variants, which use Monte Carlo Tree Search together with a neural network that guides the search by predicting state values and action probabilities. AlphaZero trains these networks by minimizing a planning loss that makes the value prediction match the episode return, and the policy prediction at the root of the search tree match the output of the full tree expansion. AlphaZero has been applied to various single-agent environments that require careful planning, with great success. In this paper, we explore an intriguing question: can we outperform it by directly maximizing the episode score instead of minimizing this planning loss, while leaving the MCTS algorithm and neural architecture unchanged? To directly maximize the episode score, we use evolution strategies, a family of algorithms for zeroth-order blackbox optimization. Our experiments indicate that, across all the tested single-agent environments, directly maximizing the episode score instead of minimizing the planning loss yields a dramatic improvement in performance. 
    more » « less