Search

In this paper, we consider the classic fair division problem of allocating $m$ divisible items to $n$ agents with linear valuations over the items. We define novel notions of fair shares from the perspective of individual agents via the cake-cutting process. These shares generalize the notion of proportionality by taking into account the valuations of other agents via constraints capturing envy. We study what fraction (approximation) of these shares are achievable in the worst case, and present tight and non-trivial approximation bounds as a function of $n$ and $m$. In particular, we show a tight approximation bound of $\Theta(\sqrt{n})$ for various notions of such shares. We show this bound via a novel application of dual fitting, which may be of independent interest. We also present a bound of $O(m^{2/3})$ for a strict notion of share, with an almost matching lower bound. We further develop weaker notions of shares whose approximation bounds interpolate smoothly between proportionality and the shares described above. We finally present empirical results showing that our definitions lead to more reasonable shares than the standard fair share notion of proportionality.

We address the fundamental problem of selection under uncertainty by modeling it from the perspective of Bayesian persuasion. In our model, a decision maker with imperfect information always selects the option with the highest expected value. We seek to achieve fairness among the options by revealing additional information to the decision maker and hence influencing its subsequent selection. To measure fairness, we adopt the notion of majorization, aiming at simultaneously approximately maximizing all symmetric, monotone, concave functions over the utilities of the options. As our main result, we design a novel information revelation policy that achieves a logarithmic-approximation to majorization in polynomial time. On the other hand, no policy, regardless of its running time, can achieve a constant-approximation to majorization. Our work is the first non-trivial majorization result in the Bayesian persuasion literature with multi-dimensional information sets., Comment: Conference version of this paper appears in SODA 2025

We consider the setting where a user with sensitive features wishes to obtain a recommendation from a server in a differentially private fashion. We propose a ``multi-selection'' architecture where the server can send back multiple recommendations and the user chooses one from these that matches best with their private features. When the user feature is one-dimensional -- on an infinite line -- and the accuracy measure is defined w.r.t some increasing function $\mathfrak{h}(.)$ of the distance on the line, we precisely characterize the optimal mechanism that satisfies differential privacy. The specification of the optimal mechanism includes both the distribution of the noise that the user adds to its private value, and the algorithm used by the server to determine the set of results to send back as a response and further show that Laplace is an optimal noise distribution. We further show that this optimal mechanism results in an error that is inversely proportional to the number of results returned when the function $\mathfrak{h}(.)$ is the identity function.

In this paper, we study third-degree price discrimination in a model first presented in Bergemann, Brooks, and Morris [2015]. Since such price discrimination might create market segments with vastly different posted prices, we consider regulating these prices, specifically, via restricting them to lie within an interval. Given a price interval, we consider segmentations of the market where a seller, who is oblivious to the existence of such regulation, still posts prices within the price interval. We show the following surprising result: For any market and price interval where such segmentation is feasible, there is always a different segmentation that optimally transfers all excess surplus to the consumers. In addition, we characterize the entire space of buyer and seller surplus that are achievable by such segmentation, including maximizing seller surplus, and simultaneously minimizing buyer and seller surplus.

In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters which are cohesive in that close-by pairs of nodes are assigned to the same cluster with high probability. We require the additional aspect of individual fairness - pairs of nodes at comparable distances should be separated with comparable probability. We show that classic decomposition procedures do not satisfy this property. We present novel algorithms that achieve various trade-offs between this property and additional desiderata of connectivity of the clusters and optimality in the number of clusters. We show that our individual fairness bounds may be difficult to improve by tying the improvement to resolving a major open question in metric embeddings. We finally show the efficacy of our algorithms on real planar networks modeling congressional redistricting., Comment: To appear in ICML 2024

We consider the problem of assigning students to schools, when students have different utilities for schools and schools have capacity. There are additional group fairness considerations over students that can be captured either by concave objectives, or additional constraints on the groups. We present approximation algorithms for this problem via convex program rounding that achieve various trade-offs between utility violation, capacity violation, and running time. We also show that our techniques easily extend to the setting where there are arbitrary covering constraints on the feasible assignment, capturing multi-criteria and ranking optimization.

This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from other agents. The goal of the marketplace is to encourage participation for data sharing in the presence of such heterogeneity. Our market design approach for data sharing focuses on interim utility balance, where participants contribute and receive equitable utility from refinement of their models. We present such a market model for which we study computational complexity, solution existence, and approximation algorithms for welfare maximization and core stability. We finally support our theoretical insights with simulations on a mean estimation task inspired by road traffic delay estimation., Comment: To appear in WWW 2024

In this paper, we consider differentially private classification when some features are sensitive, while the rest of the features and the label are not. We adapt the definition of differential privacy naturally to this setting. Our main contribution is a novel adaptation of AdaBoost that is not only provably differentially private, but also significantly outperforms a natural benchmark that assumes the entire data of the individual is sensitive in the experiments. As a surprising observation, we show that boosting randomly generated classifiers suffices to achieve high accuracy. Our approach easily adapts to the classical setting where all the features are sensitive, providing an alternate algorithm for differentially private linear classification with a much simpler privacy proof and comparable or higher accuracy than differentially private logistic regression on real-world datasets.

A seller is pricing identical copies of a good to a stream of unit-demand buyers. Each buyer has a value on the good as his private information. The seller only knows the empirical value distribution of the buyer population and chooses the revenue-optimal price. We consider a widely studied third-degree price discrimination model where an information intermediary with perfect knowledge of the arriving buyer's value sends a signal to the seller, hence changing the seller's posterior and inducing the seller to set a personalized posted price. Prior work of Bergemann, Brooks, and Morris (American Economic Review, 2015) has shown the existence of a signaling scheme that preserves seller revenue, while always selling the item, hence maximizing consumer surplus. In a departure from prior work, we ask whether the consumer surplus generated is fairly distributed among buyers with different values. To this end, we aim to maximize welfare functions that reward more balanced surplus allocations. Our main result is the surprising existence of a novel signaling scheme that simultaneously $8$-approximates all welfare functions that are non-negative, monotonically increasing, symmetric, and concave, compared with any other signaling scheme. Classical examples of such welfare functions include the utilitarian social welfare, the Nash welfare, and the max-min welfare. Such a guarantee cannot be given by any consumer-surplus-maximizing scheme -- which are the ones typically studied in the literature. In addition, our scheme is socially efficient, and has the fairness property that buyers with higher values enjoy higher expected surplus, which is not always the case for existing schemes.

We consider the multiwinner election problem where the goal is to choose a committee of $k$ candidates given the voters' utility functions. We allow arbitrary additional constraints on the chosen committee, and the utilities of voters to belong to a very general class of set functions called $\beta$-self bounding. When $\beta=1$, this class includes XOS (and hence, submodular and additive) utilities. We define a novel generalization of core stability called restrained core to handle constraints and consider multiplicative approximations on the utility under this notion. Our main result is the following: If a smooth version of Nash Welfare is globally optimized over committees within the constraints, the resulting committee lies in the $e^{\beta}$-approximate restrained core for $\beta$-self bounding utilities and arbitrary constraints. As a result, we obtain the first constant approximation for stability with arbitrary additional constraints even for additive utilities (factor of $e$), and the first analysis of the stability of Nash Welfare with XOS functions even with no constraints. We complement this positive result by showing that the $c$-approximate restrained core can be empty for $c<16/15$ even for approval utilities and one additional constraint. Furthermore, the exponential dependence on $\beta$ in the approximation is unavoidable for $\beta$-self bounding functions even with no constraints. We next present improved and tight approximation results for simpler classes of utility functions and simpler types of constraints. We also present an extension of restrained core to extended justified representation with constraints and show an existence result for matroid constraints. We finally generalize our results to the setting with arbitrary-size candidates and no additional constraints. Our techniques are different from previous analyses and are of independent interest., Comment: accepted by the 24th ACM Conference on Economics and Computation (EC'23)

In the assignment problem, a set of items must be allocated to unit-demand agents who express ordinal preferences (rankings) over the items. In the assignment problem with priorities, agents with higher priority are entitled to their preferred goods with respect to lower priority agents. A priority can be naturally represented as a ranking and an uncertain priority as a distribution over rankings. For example, this models the problem of assigning student applicants to university seats or job applicants to job openings when the admitting body is uncertain about the true priority over applicants. This uncertainty can express the possibility of bias in the generation of the priority ranking. We believe we are the first to explicitly formulate and study the assignment problem with uncertain priorities. We introduce two natural notions of fairness in this problem: stochastic envy-freeness (SEF) and likelihood envy-freeness (LEF). We show that SEF and LEF are incompatible and that LEF is incompatible with ordinal efficiency. We describe two algorithms, Cycle Elimination (CE) and Unit-Time Eating (UTE) that satisfy ordinal efficiency (a form of ex-ante Pareto optimality) and SEF; the well known random serial dictatorship algorithm satisfies LEF and the weaker efficiency guarantee of ex-post Pareto optimality. We also show that CE satisfies a relaxation of LEF that we term 1-LEF which applies only to certain comparisons of priority, while UTE satisfies a version of proportional allocations with ranks. We conclude by demonstrating how a mediator can model a problem of school admission in the face of bias as an assignment problem with uncertain priority., Comment: Accepted to AAMAS 2023

We consider the classic online learning and stochastic multi-armed bandit (MAB) problems, when at each step, the online policy can probe and find out which of a small number ($k$) of choices has better reward (or loss) before making its choice. In this model, we derive algorithms whose regret bounds have exponentially better dependence on the time horizon compared to the classic regret bounds. In particular, we show that probing with $k=2$ suffices to achieve time-independent regret bounds for online linear and convex optimization. The same number of probes improve the regret bound of stochastic MAB with independent arms from $O(\sqrt{nT})$ to $O(n^2 \log T)$, where $n$ is the number of arms and $T$ is the horizon length. For stochastic MAB, we also consider a stronger model where a probe reveals the reward values of the probed arms, and show that in this case, $k=3$ probes suffice to achieve parameter-independent constant regret, $O(n^2)$. Such regret bounds cannot be achieved even with full feedback after the play, showcasing the power of limited ``advice'' via probing before making the play. We also present extensions to the setting where the hints can be imperfect, and to the case of stochastic MAB where the rewards of the arms can be correlated., Comment: To appear in ITCS 2023

In this paper, we propose to use the concept of local fairness for auditing and ranking redistricting plans. Given a redistricting plan, a deviating group is a population-balanced contiguous region in which a majority of individuals are of the same interest and in the minority of their respective districts; such a set of individuals have a justified complaint with how the redistricting plan was drawn. A redistricting plan with no deviating groups is called locally fair. We show that the problem of auditing a given plan for local fairness is NP-complete. We present an MCMC approach for auditing as well as ranking redistricting plans. We also present a dynamic programming based algorithm for the auditing problem that we use to demonstrate the efficacy of our MCMC approach. Using these tools, we test local fairness on real-world election data, showing that it is indeed possible to find plans that are almost or exactly locally fair. Further, we show that such plans can be generated while sacrificing very little in terms of compactness and existing fairness measures such as competitiveness of the districts or seat shares of the plans.

We consider the participatory budgeting problem where each of $n$ voters specifies additive utilities over $m$ candidate projects with given sizes, and the goal is to choose a subset of projects (i.e., a committee) with total size at most $k$. Participatory budgeting mathematically generalizes multiwinner elections, and both have received great attention in computational social choice recently. A well-studied notion of group fairness in this setting is core stability: Each voter is assigned an "entitlement" of $\frac{k}{n}$, so that a subset $S$ of voters can pay for a committee of size at most $|S| \cdot \frac{k}{n}$. A given committee is in the core if no subset of voters can pay for another committee that provides each of them strictly larger utility. This provides proportional representation to all voters in a strong sense. In this paper, we study the following auditing question: Given a committee computed by some preference aggregation method, how close is it to the core? Concretely, how much does the entitlement of each voter need to be scaled down by, so that the core property subsequently holds? As our main contribution, we present computational hardness results for this problem, as well as a logarithmic approximation algorithm via linear program rounding. We show that our analysis is tight against the linear programming bound. Additionally, we consider two related notions of group fairness that have similar audit properties. The first is Lindahl priceability, which audits the closeness of a committee to a market clearing solution. We show that this is related to the linear programming relaxation of auditing the core, leading to efficient exact and approximation algorithms for auditing. The second is a novel weakening of the core that we term the sub-core, and we present computational results for auditing this notion as well., Comment: accepted by the 18th Conference on Web and Internet Economics (WINE 2022)

We study the power of price discrimination via an intermediary in bilateral trade, when there is a revenue-maximizing seller selling an item to a buyer with a private value drawn from a prior. Between the seller and the buyer, there is an intermediary that can segment the market by releasing information about the true values to the seller. This is termed signaling, and enables the seller to price discriminate. In this setting, Bergemann et al. showed the existence of a signaling scheme that simultaneously raises the optimal consumer surplus, guarantees the item always sells, and ensures the seller's revenue does not increase. Our work extends the positive result of Bergemann et al. to settings where the type space is larger, and where optimal auction is randomized, possibly over a menu that can be exponentially large. In particular, we consider two settings motivated by budgets: The first is when there is a publicly known budget constraint on the price the seller can charge and the second is the FedEx problem where the buyer has a private deadline or service level (equivalently, a private budget that is guaranteed to never bind). For both settings, we present a novel signaling scheme and its analysis via a continuous construction process that recreates the optimal consumer surplus guarantee of Bergemann et al. The settings we consider are special cases of the more general problem where the buyer has a private budget constraint in addition to a private value. We finally show that our positive results do not extend to this more general setting. Here, we show that any efficient signaling scheme necessarily transfers almost all the surplus to the seller instead of the buyer., Comment: Appears in ACM EC 2022

We model the societal task of redistricting political districts as a partitioning problem: Given a set of $n$ points in the plane, each belonging to one of two parties, and a parameter $k$, our goal is to compute a partition $\Pi$ of the plane into regions so that each region contains roughly $\sigma = n/k$ points. $\Pi$ should satisfy a notion of ''local'' fairness, which is related to the notion of core, a well-studied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in $\Pi$ if it belongs to the minority party. A group $D$ of roughly $\sigma$ contiguous points is called a deviating group with respect to $\Pi$ if majority of points in $D$ are unhappy in $\Pi$. The partition $\Pi$ is locally fair if there is no deviating group with respect to $\Pi$. This paper focuses on a restricted case when points lie in $1$D. The problem is non-trivial even in this case. We consider both adversarial and ''beyond worst-case" settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are ''runs'' of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of $\sigma$, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomial-time algorithm for computing a locally fair partition if one exists.