An official website of the United States government
Consider a principal who wants to search through a space of stochastic solutions for one maximizing their utility. If the principal cannot conduct this search on their own, they may instead delegate this problem to an agent with distinct and potentially misaligned utilities. This is called delegated search, and the principal in such problems faces a mechanism design problem in which they must incentivize the agent to find and propose a solution maximizing the principal's expected utility. Following prior work in this area, we consider mechanisms without payments and aim to achieve a multiplicative approximation of the principal's utility when they solve the problem without delegation. In this work, we investigate a natural and recently studied generalization of this model to multiple agents and find nearly tight bounds on the principal's approximation as the number of agents increases. As one might expect, this approximation approaches 1 with increasing numbers of agents, but, somewhat surprisingly, we show that this is largely not due to direct competition among agents.
more »
« less
This content will become publicly available on February 24, 2026
Orders and fibering
In 2018, Kielak gave a virtual fibering criterion for RFRS groups. In this paper, we present a simpler proof of this.
more »
« less
- Award ID(s):
- 2203325
- PAR ID:
- 10591174
- Publisher / Repository:
- EMS Press
- Date Published:
- Journal Name:
- Groups, Geometry, and Dynamics
- ISSN:
- 1661-7207
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A major goal in robotics is to enable intelligent mobile robots to operate smoothly in shared human-robot environments. One of the most fundamental capabilities in service of this goal is competent navigation in this “social” context. As a result, there has been a recent surge of research on social navigation; and especially as it relates to the handling of conflicts between agents during social navigation. These developments introduce a variety of models and algorithms, however as this research area is inherently interdisciplinary, many of the relevant papers are not comparable and there is no shared standard vocabulary. This survey aims at bridging this gap by introducing such a common language, using it to survey existing work, and highlighting open problems. It starts by defining the boundaries of this survey to a limited, yet highly common type of social navigation—conflict avoidance. Within this proposed scope, this survey introduces a detailed taxonomy of the conflict avoidance components. This survey then maps existing work into this taxonomy, while discussing papers using its framing. Finally, this article proposes some future research directions and open problems that are currently on the frontier of social navigation to aid ongoing and future research.more » « less
-
It is well known that the standard greedy algorithm guarantees a worst-case approximation factor of 1 − 1/e when maximizing a monotone submodular function under a cardinality constraint. However, empirical studies show that its performance is substantially better in practice. This raises a natural question of explaining this improved performance of the greedy algorithm. In this work, we define sharpness for submodular functions as a candidate explanation for this phenomenon. We show that the greedy algorithm provably performs better as the sharpness of the submodular function increases. This improvement ties in closely with the faster convergence rates of first order methods for sharp functions in convex optimization.more » « less
-
We define a class of transversal slices in spaces which are quasi-Poisson for the action of a complex semisimple group. This is a multiplicative analogue of Whittaker reduction. One example is the multiplicative universal centralizer, which is equipped with the usual symplectic structure in this way. We construct a smooth relative compactification of this space by taking the closure of each centralizer fiber in the wonderful compactification. By realizing this relative compactification as a transversal in a larger quasi-Poisson variety, we show that it is smooth and log-symplectic.more » « less
-
This work studies mathematics word problems’ use in a classroom of recent immigrants, or newcomers, to a United States public elementary school. I study how word problems foster the recontextualization of mathematical concepts in a lived real- ity experienced by newcomer students in their new cultural and educational setting. In this study’s setting language plays a significant role in the process of meaning-making. I describe how language use in word problems remains intertwined with mathematics instruction. This opens a space for questioning word problems’ purpose and role in multilingual classrooms, and I highlight how the creative process of co-constructing problems’ meaning in this context can expand notions of genre applied to word problems. Throughout I adopt a theorization of translanguaging as a language practice and apply it in problem discussion. This helps probe how language use impacts students’ ways of understanding and utilizing mathematical concepts.more » « less
