We consider matroid allocation problems under \textit{opportunity fairness} constraints: resources need to be allocated to a set of agents under matroid constraints (which includes classical problems such as bipartite matching). Agents are divided into $C$ groups according to a sensitive attribute, and an allocation is opportunity-fair if each group receives the same share proportional to the maximum feasible allocation it could achieve in isolation. We study the Price of Fairness (PoF), i.e., the ratio between maximum size allocations and maximum size opportunity-fair allocations. We first provide a characterization of the PoF leveraging the underlying polymatroid structure of the allocation problem. Based on this characterization, we prove bounds on the PoF in various settings from fully adversarial (worst-case) to fully random. Notably, one of our main results considers an arbitrary matroid structure with agents randomly divided into groups. In this setting, we prove a PoF bound as a function of the (relative) size of the largest group. Our result implies that, as long as there is no dominant group (i.e., the largest group is not too large), opportunity fairness constraints do not induce any loss of social welfare (defined as the allocation size). Overall, our results give insights into which aspects of the problem's structure affect the trade-off between opportunity fairness and social welfare.

We study matching markets with ties, where workers on one side of the market may have tied preferences over jobs, determined by their matching utilities. Unlike classical two-sided markets with strict preferences, no single stable matching exists that is utility-maximizing for all workers. To address this challenge, we introduce the \emph{Optimal Stable Share} (OSS)-ratio, which measures the ratio of a worker's maximum achievable utility in any stable matching to their utility in a given matching. We prove that distributions over only stable matchings can incur linear utility losses, i.e., an $\Omega (N)$ OSS-ratio, where $N$ is the number of workers. To overcome this, we design an algorithm that efficiently computes a distribution over (possibly non-stable) matchings, achieving an asymptotically tight $O (\log N)$ OSS-ratio. When exact utilities are unknown, our second algorithm guarantees workers a logarithmic approximation of their optimal utility under bounded instability. Finally, we extend our offline approximation results to a bandit learning setting where utilities are only observed for matched pairs. In this setting, we consider worker-optimal stable regret, design an adaptive algorithm that smoothly interpolates between markets with strict preferences and those with statistical ties, and establish a lower bound revealing the fundamental trade-off between strict and tied preference regimes.

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 initiate the study of how auction design affects the division of surplus among bidders. We propose a parsimonious measure for equity and apply it to standard auctions for homogeneous goods. Our surplus-equitable mechanism is efficient, Bayesian-Nash incentive compatible, and achieves surplus parity among winners ex-post. The uniform-price auction is equity-optimal if and only if bidders have a common value. Against intuition, the pay-as-bid auction is not always equity-preferred if bidders have private values. In auctions with price mixing between pay-as-bid and uniform prices, we provide prior-free bounds on the equity-preferred pricing under a common regularity condition on signals. The full paper is available at https://arxiv.org/abs/2403.07799.

A major problem in fair division is how to allocate a set of indivisible resources among agents fairly and efficiently. The goal of this work is to characterize the tradeoffs between two well-studied measures of fairness and efficiency --- envy freeness up to any item (EFX) for fairness, and Nash welfare for efficiency --- by saying, for given constants α and β, whether there exists an α-EFX allocation that guarantees a β-fraction of the maximum Nash welfare (β-MNW). For additive valuations, we show that for any α ∈ [0,1], there exists a partial allocation that is α-EFX and 1/(α+1)-MNW. This tradeoff turns out to be tight (for every α) as demonstrated by an impossibility result that we give. We also show that for α ∈ [0, φ-1 ≃ 0.618] these partial allocations can be turned into complete allocations where all items are assigned. Furthermore, for any α ∈ [0, 1/2], we show that the tight tradeoff of α-EFX and 1/(α+1)-MNW with complete allocations holds for the more general setting of subadditive valuations. Our results improve upon the current state of the art, for both additive and subadditive valuations, and match the best-known approximations of EFX under complete allocations, regardless of Nash welfare guarantees. Notably, our constructions for additive valuations also provide EF1 and constant approximations for maximin share guarantees.

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 best-of-both-worlds guarantees for the fair division of indivisible items among agents with subadditive valuations. Our main result establishes the existence of a random allocation that is simultaneously ex-ante 1/2-envy-free, ex-post 1/2-EFX and ex-post EF1, for every instance with subadditive valuations. We achieve this result by a novel polynomial-time algorithm that randomizes the well-established envy cycles procedure in a way that provides ex-ante fairness. Notably, this is the first best-of-both-worlds fairness guarantee for subadditive valuations, even when considering only EF1 without EFX.

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.

Abstract We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive one by one in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier up to which the celebrated $$e/(e-1)$$ e / ( e - 1 ) competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.

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).

We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multiparameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive online in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier up to which the celebrated e/(e − 1) competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.

Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However, in the single-pass streaming model, where the elements arrive one by one and an algorithm can store only a small fraction of input elements, there is large gap in our knowledge, even though several approximation algorithms have been proposed in the literature. In this work, we present the first lower bound on the approximation ratios for cardinality and matroid constraints that beat $1-\frac{1}{e}$ in the single-pass streaming model. Let $n$ be the number of elements in the stream. Then, we prove that any (randomized) streaming algorithm for a cardinality constraint with approximation ratio $2-\sqrt{2}+\varepsilon$ requires $\Omega(\frac{n}{K^2})$ space for any $\varepsilon>0$, where $K$ is the size limit of the output set. We also prove that any (randomized) streaming algorithm for a (partition) matroid constraint with approximation ratio $\frac{K}{2K-1}+\varepsilon$ requires $\Omega(\frac{n}{K^2})$ space for any $\varepsilon>0$, where $K$ is the rank of the given matroid. In addition, we give streaming algorithms that assume access to the objective function via a weak oracle that can only be used to evaluate function values on feasible sets. Specifically, we show weak-oracle streaming algorithms for cardinality and matroid constraints with approximation ratios $\frac{K}{2K-1}$ and $\frac{1}{2}$, respectively, whose space complexity is exponential in $K$ but is independent of $n$. The former one exactly matches the known inapproximability result for a cardinality constraint in the weak oracle model. The latter one almost matches our lower bound of $\frac{K}{2K-1}$ for a matroid constraint, which almost settles the approximation ratio for a matroid constraint that can be obtained by a streaming algorithm whose space complexity is independent of $n$.

Stable matching in a community consisting of men and women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley, who designed the celebrated ``deferred acceptance'' algorithm for the problem. In the input, each participant ranks participants of the opposite type, so the input consists of a collection of permutations, representing the preference lists. A bipartite matching is unstable if some man-woman pair is blocking: both strictly prefer each other to their partner in the matching. Stability is an important economics concept in matching markets from the viewpoint of manipulability. The unicity of a stable matching implies non-manipulability, and near-unicity implies limited manipulability, thus these are mathematical properties related to the quality of stable matching algorithms. This paper is a theoretical study of the effect of correlations on approximate manipulability of stable matching algorithms. Our approach is to go beyond worst case, assuming that some of the input preference lists are drawn from a distribution. Our model encompasses a discrete probabilistic process inspired by a popularity model introduced by Immorlica and Mahdian, that provides a way to capture correlation between preference lists. Approximate manipulability is approached from several angles : when all stable partners of a person have approximately the same rank; or when most persons have a unique stable partner. Another quantity of interest is a person's number of stable partners. Our results aim to paint a picture of the manipulability of stable matchings in a ``beyond worst case'' setting.

The COVID-19 epidemic has forced most countries to impose contact-limiting restrictions at workplaces, universities, schools, and more broadly in our societies. Yet, the effectiveness of these unprecedented interventions in containing the virus spread remain largely unquantified. Here, we develop a simulation study to analyze COVID-19 outbreaks on three real-life contact networks stemming from a workplace, a primary school and a high school in France. Our study provides a fine-grained analysis of the impact of contact-limiting strategies at workplaces, schools and high schools, including: (1) Rotating strategies, in which workers are evenly split into two shifts that alternate on a daily or weekly basis; and (2) On-Off strategies, where the whole group alternates periods of normal work interactions with complete telecommuting. We model epidemics spread in these different setups using a stochastic discrete-time agent-based transmission model that includes the coronavirus most salient features: super-spreaders, infectious asymptomatic individuals, and pre-symptomatic infectious periods. Our study yields clear results: the ranking of the strategies, based on their ability to mitigate epidemic propagation in the network from a first index case, is the same for all network topologies (workplace, primary school and high school). Namely, from best to worst: Rotating week-by-week, Rotating day-by-day, On-Off week-by-week, and On-Off day-by-day. Moreover, our results show that below a certain threshold for the original local reproduction number [Formula: see text] within the network (< 1.52 for primary schools, < 1.30 for the workplace, < 1.38 for the high school, and < 1.55 for the random graph), all four strategies efficiently control outbreak by decreasing effective local reproduction number to [Formula: see text] < 1. These results can provide guidance for public health decisions related to telecommuting.

Stable matching in a community consisting of N men and N women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley.

A top-list is a possibly incomplete ranking of elements: only a subset of the elements are ranked, with all unranked elements tied for last. Top-list aggregation, a generalization of the well-known rank aggregation problem, takes as input a collection of top-lists and aggregates them into a single complete ranking, aiming to minimize the number of upsets (pairs ranked in opposite order in the input and in the output). In this paper, we give simple approximation algorithms for top-list aggregation. We generalize the footrule algorithm for rank aggregation (which minimizes Spearman's footrule distance), yielding a simple 2-approximation algorithm for top-list aggregation. Ailon's RepeatChoice algorithm for bucket-orders aggregation yields a 2-approximation algorithm for top-list aggregation. Using inspiration from approval voting, we define the score of an element as the frequency with which it is ranked, i.e. appears in an input top-list. We reinterpret RepeatChoice for top-list aggregation as a randomized algorithm using variables whose expectations correspond to score and to the average rank of an element given that it is ranked. Using average ranks, we generalize and analyze Borda's algorithm for rank aggregation. We observe that the natural generalization is not a constant approximation. We design a simple 2-phase variant of the Generalized Borda's algorithm, roughly sorting by scores and breaking ties by average ranks, yielding another simple constant-approximation algorithm for top-list aggregation. We then design another 2-phase variant in which in order to break ties we use, as a black box, the Mathieu-Schudy PTAS for rank aggregation, yielding a PTAS for top-list aggregation. This solves an open problem posed by Ailon. Finally, in the special case in which all input lists have length at most k, we design another simple 2-phase algorithm based on sorting by scores, and prove that it is an EPTAS – the complexity is (n log n) when k = o(log n).

The skip list is an elegant dictionary data structure that is commonly deployed in RAM. A skip list with N elements supports searches, inserts, and deletes in O(log N) operations with high probability (w.h.p.) and range queries returning K elements in O(log N + K) operations w.h.p.