We study revenue maximization for agents with additive preferences, subject to downward-closed constraints on the set of feasible allocations. In seminal work,~\citet{alaei2014bayesian} introduced a powerful multi-to-single agent reduction based on an ex-ante relaxation of the multi-agent problem. This reduction employs a rounding procedure which is an online contention resolution scheme (OCRS) in disguise, a now widely-used method for rounding fractional solutions in online Bayesian and stochastic optimization problems. In this paper, we leverage our vantage point, 10 years after the work of Alaei, with a rich OCRS toolkit and modern approaches to analyzing multi-agent mechanisms; we introduce a general framework for designing non-sequential and sequential multi-agent, revenue-maximizing mechanisms, capturing a wide variety of problems Alaei's framework could not address. Our framework uses an \emph{interim} relaxation, that is rounded to a feasible mechanism using what we call a two-level OCRS, which allows for some structured dependence between the activation of its input elements. For a wide family of constraints, we can construct such schemes using existing OCRSs as a black box; for other constraints, such as knapsack, we construct such schemes from scratch. We demonstrate numerous applications of our framework, including a sequential mechanism that guarantees a $\frac{2e}{e-1} \approx 3.16$ approximation to the optimal revenue for the case of additive agents subject to matroid feasibility constraints. Finally, we show how our framework can be easily extended to multi-parameter procurement auctions, where we provide an OCRS for Stochastic Knapsack that might be of independent interest.

We study online combinatorial allocation problems in the secretary setting, under interdependent values. In the interdependent model, introduced by Milgrom and Weber (1982), each agent possesses a private signal that captures her information about an item for sale, and the value of every agent depends on the signals held by all agents. Mauras, Mohan, and Reiffenhäuser (2024) were the first to study interdependent values in online settings, providing constant-approximation guarantees for secretary settings, where agents arrive online along with their signals and values, and the goal is to select the agent with the highest value.

We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is "correct" with probability $\frac{1}{2}+δ$ for some $δ> 0$. At each round, a node is selected uniformly at random to update their public opinion to match the majority of their neighbours (breaking ties in favour of their initial private signal). Our main result shows that for sparse and connected binomial random graphs $\mathcal G(n,p)$ the process stabilizes in a "correct" consensus in $\mathcal O(n\log^2 n/\log\log n)$ steps with high probability. In fact, when $\log n/n \ll p = o(1)$ the process terminates at time $\hat T = (1+o(1))n\log n$, where $\hat T$ is the first time when all nodes have been selected at least once. However, in dense binomial random graphs with $p=Ω(1)$, there is an information cascade where the process terminates in the "incorrect" consensus with probability bounded away from zero.

We study a communication game between a sender and receiver. The sender chooses one of her signals about the state of the world (i.e., an anecdote) and communicates it to the receiver who takes an action affecting both players. The sender and receiver both care about the state of the world but are also influenced by personal preferences, so their ideal actions can differ. We characterize perfect Bayesian equilibria. The sender faces a temptation to persuade: she wants to select a biased anecdote to influence the receiver’s action. Anecdotes are still informative to the receiver (who will debias at equilibrium) but the attempt to persuade comes at the cost of precision. This gives rise to informational homophily where the receiver prefers to listen to like-minded senders because they provide higher-precision signals. Communication becomes polarized when the sender is an expert with access to many signals, with the sender choosing extreme outlier anecdotes at equilibrium (unless preferences are perfectly aligned). This polarization dissipates all the gains from communication with an increasingly well-informed sender when the anecdote distribution is heavy-tailed. Experts therefore face a curse of informedness: receivers will prefer to listen to less-informed senders who cannot pick biased signals as easily.

We study auction design within the widely acclaimed model of interdependent values, introduced by Milgrom and Weber [1982]. In this model, every bidder i has a private signal si for the item for sale, and a public valuation function υi (s1, ..., sn) which maps every vector of private signals (of all bidders) into a real value. A recent line of work established the existence of approximately-optimal mechanisms within this framework, even in the more challenging scenario where each bidder's valuation function υi is also private. This body of work has primarily focused on single-item auctions with two natural classes of valuations: those exhibiting submodularity over signals (SOS) and d-critical valuations.

We study online selection problems in both the prophet and secretary settings, when arriving agents have interdependent values. In the interdependent values model, introduced in the seminal work of Milgrom and Weber [1982], each agent has a private signal and the value of an agent is a function of the signals held by all agents. Results in online selection crucially rely on some degree of independence of values, which is conceptually at odds with the interdependent values model. For prophet and secretary models under the standard independent values assumption, prior works provide constant factor approximations to the welfare. On the other hand, when agents have interdependent values, prior works in Economics and Computer Science provide truthful mechanisms that obtain optimal and approximately optimal welfare under certain assumptions on the valuation functions.

The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $s_{1}, \ldots, s_{n}$ of the n bidders and public valuation functions $v_{i}\left(s_{1}, \ldots, s_{n}\right)$. Recent work in TCS has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and private valuations, and established $O\left(\log ^{2} n\right)$-approximation for SOS valuations. In this paper we show that this setting admits a constant factor approximation, settling the open question raised by Eden et al. (2022).

In the interdependent values (IDV) model introduced by Milgrom and Weber [1982], agents have private signals that capture their information about different social alternatives, and the valuation of every agent is a function of all agent signals. While interdependence has been mainly studied for auctions, it is extremely relevant for a large variety of social choice settings, including the canonical and practically important setting of public projects. The IDV model is much more realistic but also very challenging relative to the standard independent private values model. Welfare guarantees for IDV have been achieved mainly through two alternative conditions known as single-crossing and submodularity over signals (SOS). In either case, the existing theory falls short of solving the public projects setting. Our contribution is twofold: (i) We give a useful characterization of truthfulness for IDV public projects, parallel to the known characterization for independent private values, and identify the domain frontier for which this characterization applies; (ii) Using this characterization, we provide possibility and impossibility results for welfare approximation in public projects with SOS valuations. Our main impossibility result is that, in contrast to auctions, no universally truthful mechanism performs better for public projects with SOS valuations than choosing a project at random. Our main positive result applies to excludable public projects with SOS, for which we establish a constant factor approximation similar to auctions. Our results suggest that exclusion may be a key tool for achieving welfare guarantees in the IDV model. * The full version of the paper can be accessed at https://arxiv.org/abs/2204.08044. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement no. 866132), by the Israel Science Foundation (ISF grant nos. 317/17 and 336/18), by an Amazon Research Award, and by the NSF-BSF (grant no. 2020788).

Internet ad auctions have evolved from a few lines of text to richer informational layouts that include images, sitelinks, videos, etc. Ads in these new formats occupy varying amounts of space, and an advertiser can provide multiple formats, only one of which can be shown.The seller is now faced with a multi-parameter mechanism design problem.Computing an efficient allocation is computationally intractable, and therefore the standard Vickrey-Clarke-Groves (VCG) auction, while truthful and welfare-optimal, is impractical. In this paper, we tackle a fundamental problem in the design of modern ad auctions. We adopt a ``Myersonian'' approach and study allocation rules that are monotone both in the bid and set of rich ads. We show that such rules can be paired with a payment function to give a truthful auction. Our main technical challenge is designing a monotone rule that yields a good approximation to the optimal welfare. Monotonicity doesn't hold for standard algorithms, e.g. the incremental bang-per-buck order, that give good approximations to ``knapsack-like'' problems such as ours. In fact, we show that no deterministic monotone rule can approximate the optimal welfare within a factor better than $2$ (while there is a non-monotone FPTAS). Our main result is a new, simple, greedy and monotone allocation rule that guarantees a $3$ approximation. In ad auctions in practice, monotone allocation rules are often paired with the so-called \emph{Generalized Second Price (GSP)} payment rule, which charges the minimum threshold price below which the allocation changes. We prove that, even though our monotone allocation rule paired with GSP is not truthful, its Price of Anarchy (PoA) is bounded. Under standard no-overbidding assumptions, we prove bounds on the a pure and Bayes-Nash PoA. Finally, we experimentally test our algorithms on real-world data.

We study information aggregation in networks where agents make binary decisions (labeled incorrect or correct). Agents initially form independent private beliefs about the better decision, which is correct with probability $1/2+δ$. The dynamics we consider are asynchronous (each round, a single agent updates their announced decision) and non-Bayesian (agents simply copy the majority announcements among their neighbors, tie-breaking in favor of their private signal). Our main result proves that when the network is a tree formed according to the preferential attachment model \cite{BarabasiA99}, with high probability, the process stabilizes in a correct majority within $O(n \log n/ \log\log n)$ rounds. We extend our results to other tree structures, including balanced $M$-ary trees for any $M$.

We consider a revenue-maximizing seller with n items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distinct options the buyer may purchase, up to permutations of the items. Our main result is that a mechanism of quasi-polynomial symmetric menu complexity suffices to guarantee a (1 - epsilon )-approximation when the buyer is unit-demand over independent items, even when the value distribution is unbounded, and that this mechanism can be found in quasi-polynomial time. Our key technical result is a polynomial-time, (symmetric) menu-complexity-preserving black-box reduction from achieving a (1 - epsilon )-approximation for unbounded valuations that are subadditive over independent items to achieving a (1 - O(epsilon ))-approximation when the values are bounded (and still subadditive over independent items). We further apply this reduction to deduce approximation schemes for a suite of valuation classes beyond our main result. Finally, we show that selling separately (which has exponential menu complexity) can be approximated up to a (1 - epsilon ) factor with a menu of efficient-linear (f (epsilon) · n) symmetric menu complexity.

Recently there has been extensive work on maintaining (approximate) maximum matchings in dynamic graphs. We consider a generalisation of this problem known as the maximum b-matching: Every node v has a positive integral capacity b_v, and the goal is to maintain an (approximate) maximum-cardinality subset of edges that contains at most b_v edges incident on every node v. The maximum matching problem is a special case of this problem where b_v = 1 for every node v. Bhattacharya, Henzinger and Italiano [ICALP 2015] showed how to maintain a O(1) approximate maximum b-matching in a graph in O(log^3 n) amortised update time. Their approximation ratio was a large (double digit) constant. We significantly improve their result both in terms of approximation ratio as well as update time. Specifically, we design a randomised dynamic algorithm that maintains a (2+epsilon)-approximate maximum $b$-matching in expected amortised O(1/epsilon^4) update time. Thus, for every constant epsilon in (0, 1), we get expected amortised O(1) update time. Our algorithm generalises the framework of Baswana, Gupta, Sen [FOCS 2011] and Solomon [FOCS 2016] for maintaining a maximal matching in a dynamic graph.