We study a distributed learning problem in which learning agents are embedded in a directed acyclic graph (DAG). There is a fixed and arbitrary distribution over feature/label pairs, and each agent or vertex in the graph is able to directly observe only a subset of the features — potentially a different subset for every agent. The agents learn sequentially in some order consistent with a topological sort of the DAG, committing to a model mapping observations to predictions of the real-valued label. Each agent observes the predictions of their parents in the DAG, and trains their model using both the features of the instance that they directly observe, and the predictions of their parents as additional features. We ask when this process is sufficient to achieve information aggregation, in the sense that some agent in the DAG is able to learn a model whose error is competitive with the best model that could have been learned (in some hypothesis class) with direct access to all features, despite the fact that no single agent in the network has such access. We give upper and lower bounds for this problem for both linear and general hypothesis classes. Our results identify the depth of the DAG as the key parameter: information aggregation can occur over sufficiently long paths in the DAG, assuming that all of the relevant features are well represented along the path, and there are distributions over which information aggregation cannot occur even in the linear case, and even in arbitrarily large DAGs that do not have sufficient depth (such as a hub-and-spokes topology in which the spoke vertices collectively see all the features). We complement our theoretical results with a comprehensive set of experiments.

The competition complexity of an auction setting is the number of additional bidders needed such that the simple mechanism of selling items separately (with additional bidders) achieves greater revenue than the optimal but complex (randomized, prior-dependent, Bayesian-truthful) optimal mechanism without the additional bidders. Our main result settles the competition complexity of n bidders with additive values over m < n independent items at [EQUATION]. The [EQUATION] upper bound is due to [Beyhaghi and Weinberg, 2019], and our main result improves the prior lower bound of Ω (ln n) to [EQUATION].

A fundamental component in the growing theoretical literature on school choice is the problem a student faces in deciding which schools to apply to. Recent models have considered a setting with a set of schools of different selectiveness, and a student who is unsure of their strength as an applicant and can apply to at most k schools [Ali and Shorrer, 2023]. Such models assume that the student cares solely about maximizing the quality of the school that they will attend. However, experience suggests that students' decisions are additionally influenced by a set of crucial behavioral biases based on reputational effects: they experience a subjective reputational benefit when they are admitted to a selective school, whether or not they attend; and a subjective loss based on disappointment when they are rejected. Guided by these observations, and inspired by recent behavioral economics work on loss aversion relative to expectations [Dreyfuss et al., 2022, Kőszegi and Rabin, 2006, 2007, 2009, Meisner and von Wangenheim, 2023], we propose a behavioral model by which a student chooses schools in a way that balances these subjective behavioral effects with the quality of the school they eventually attend.