BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Kamesh Munagala

Kamesh Munagala contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game TheoryData Structures and AlgorithmsMachine LearningArtificial Intelligencecs.CYDiscrete MathematicsMultiagent SystemsPerformanceSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
13works
0followers
9topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2026arXiv

Auditing for Core Stability in Participatory Budgeting

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.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Balanced Spanning Tree Distributions Have Separation Fairness

Sampling-based methods such as ReCom are widely used to audit redistricting plans for fairness, with the balanced spanning tree distribution playing a central role since it favors compact, contiguous, and population-balanced districts. However, whether such samples are truly representative or exhibit hidden biases remains an open question. In this work, we introduce the notion of separation fairness, which asks whether adjacent geographic units are separated with at most a constant probability (bounded away from one) in sampled redistricting plans. Focusing on grid graphs and two-district partitions, we prove that a smooth variant of the balanced spanning tree distribution satisfies separation fairness. Our results also provide theoretical support for popular MCMC methods like ReCom, suggesting that they maintain fairness at a granular level in the sampling process. Along the way, we develop tools for analyzing loop-erased random walks and partitions that may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Efficient Online Conformal Selection with Limited Feedback

We address the problem of conformal selection, where an agent must select a minimal subset of options to ensure that at least one ``success'' is identified with a pre-specified target probability $φ$. While traditional online conformal prediction focuses on maintaining validity for the observed sequence, minimizing the resource cost (efficiency) of such selections, especially under limited feedback, remains a significant challenge. In this work, we consider settings with the most limited ``bandit'' feedback, and demonstrate that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable, is both adversarially valid, ensuring the success target is met on average for any input sequence (and hence under distribution shifts), and stochastically efficient, achieving sublinear efficiency regret for $i.i.d.$ inputs against an appropriate stochastic benchmark. We show such guarantees under canonical models capturing bandit and semi-bandit feedback to the agent via a unifying algorithmic technique, and analytic framework involving Lyapunov functions. Our approach handles more complex settings than prior work, while requiring significantly less feedback, and our results provide a new theoretical bridge between efficient online learning with limited feedback and distribution-free uncertainty quantification.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Limits of an Information Intermediary in Auction Design

We study the limits of an information intermediary in the classical Bayesian auction, where a revenue-maximizing seller sells one item to $n$ buyers with independent private values. In addition, we have an intermediary who knows the buyers' private values, and can map these to a public signal so as to increase consumer surplus. This model generalizes the single-buyer setting proposed by Bergemann, Brooks, and Morris, who present a signaling scheme that raises the optimal consumer surplus, by guaranteeing that the item is always sold and the seller gets the same revenue as without signaling. Our work aims to understand how this result ports to the setting with multiple buyers. We likewise define the benchmark for the optimal consumer surplus: one where the auction is efficient (i.e., the item is always sold to the highest-valued buyer) and the revenue of the seller is unchanged. We show that no signaling scheme can guarantee this benchmark even for $n=2$ buyers with $2$-point valuation distributions. Indeed, no signaling scheme can be efficient while preserving any non-trivial fraction of the original consumer surplus, and no signaling scheme can guarantee consumer surplus better than a factor of $\frac{1}{2}$ compared to the benchmark. These impossibility results are existential (beyond computational), and provide a sharp separation between the single and multi-buyer settings. In light of this impossibility, we develop signaling schemes with good approximation guarantees to the benchmark. Our main technical result is an $O(1)$-approximation for i.i.d. regular buyers, via signaling schemes that are conceptually simple and computable in polynomial time. We also present an extension to the case of general independent distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Centrality with Diversity

Graph centrality measures use the structure of a network to quantify central or "important" nodes, with applications in web search, social media analysis, and graphical data mining generally. Traditional centrality measures such as the well known PageRank interpret a directed edge as a vote in favor of the importance of the linked node. We study the case where nodes may belong to diverse communities or interests and investigate centrality measures that can identify nodes that are simultaneously important to many such diverse communities. We propose a family of diverse centrality measures formed as fixed point solutions to a generalized nonlinear eigenvalue problem. Our measure can be efficiently computed on large graphs by iterated best response and we study its normative properties on both random graph models and real-world data. We find that we are consistently and efficiently able to identify the most important diverse nodes of a graph, that is, those that are simultaneously central to multiple communities.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Fair for All: Best-effort Fairness Guarantees for Classification

Standard approaches to group-based notions of fairness, such as \emph{parity} and \emph{equalized odds}, try to equalize absolute measures of performance across known groups (based on race, gender, etc.). Consequently, a group that is inherently harder to classify may hold back the performance on other groups; and no guarantees can be provided for unforeseen groups. Instead, we propose a fairness notion whose guarantee, on each group $g$ in a class $\mathcal{G}$, is relative to the performance of the best classifier on $g$. We apply this notion to broad classes of groups, in particular, where (a) $\mathcal{G}$ consists of all possible groups (subsets) in the data, and (b) $\mathcal{G}$ is more streamlined. For the first setting, which is akin to groups being completely unknown, we devise the {\sc PF} (Proportional Fairness) classifier, which guarantees, on any possible group $g$, an accuracy that is proportional to that of the optimal classifier for $g$, scaled by the relative size of $g$ in the data set. Due to including all possible groups, some of which could be too complex to be relevant, the worst-case theoretical guarantees here have to be proportionally weaker for smaller subsets. For the second setting, we devise the {\sc BeFair} (Best-effort Fair) framework which seeks an accuracy, on every $g \in \mathcal{G}$, which approximates that of the optimal classifier on $g$, independent of the size of $g$. Aiming for such a guarantee results in a non-convex problem, and we design novel techniques to get around this difficulty when $\mathcal{G}$ is the set of linear hypotheses. We test our algorithms on real-world data sets, and present interesting comparative insights on their performance.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Advertising for Demographically Fair Outcomes

Online advertising on platforms such as Google or Facebook has become an indispensable outreach tool, including for applications where it is desirable to engage different demographics in an equitable fashion, such as hiring, housing, civic processes, and public health outreach efforts. Somewhat surprisingly, the existing online advertising ecosystem provides very little support for advertising to (and recruiting) a demographically representative cohort. We study the problem of advertising for demographic representativeness from both an empirical and algorithmic perspective. In essence, we seek fairness in the outcome or conversions generated by the advertising campaigns. We first present detailed empirical findings from real-world experiments for recruiting for civic processes, using which we show that methods using Facebook-inferred features are too inaccurate for achieving equity in outcomes, while targeting via custom audiences based on a list of registered voters segmented on known attributes has much superior accuracy. This motivates us to consider the algorithmic question of optimally segmenting the list of individuals with known attributes into a few custom campaigns and allocating budgets to them so that we cost-effectively achieve outcome parity with the population on the maximum possible number of demographics. Under the assumption that a platform can reasonably enforce proportionality in spend across demographics, we present efficient exact and approximation algorithms for this problem. We present simulation results on our datasets to show the efficacy of these algorithms in achieving demographic parity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximately Stable Committee Selection

In the committee selection problem, we are given $m$ candidates, and $n$ voters. Candidates can have different weights. A committee is a subset of candidates, and its weight is the sum of weights of its candidates. Each voter expresses an ordinal ranking over all possible committees. The only assumption we make on preferences is monotonicity: If $S \subseteq S'$ are two committees, then any voter weakly prefers $S'$ to $S$. We study a general notion of group fairness via stability: A committee of given total weight $K$ is stable if no coalition of voters can deviate and choose a committee of proportional weight, so that all these voters strictly prefer the new committee to the existing one. Extending this notion to approximation, for parameter $c \ge 1$, a committee $S$ of weight $K$ is said to be $c$-approximately stable if for any other committee $S'$ of weight $K'$, the fraction of voters that strictly prefer $S'$ to $S$ is strictly less than $\frac{c K'}{K}$. When $c = 1$, this condition is equivalent to classical core stability. The question we ask is: Does a $c$-approximately stable committee of weight at most any given value $K$ always exist for constant $c$? It is relatively easy to show that there exist monotone preferences for which $c \ge 2$. However, even for simple and widely studied preference structures, a non-trivial upper bound on $c$ has been elusive. In this paper, we show that $c = O(1)$ for all monotone preference structures. Our proof proceeds via showing an existence result for a randomized notion of stability, and iteratively rounding the resulting fractional solution.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice

We study higher statistical moments of Distortion for randomized social choice in a metric implicit utilitarian model. The Distortion of a social choice mechanism is the expected approximation factor with respect to the optimal utilitarian social cost (OPT). The $k^{th}$ moment of Distortion is the expected approximation factor with respect to the $k^{th}$ power of OPT. We consider mechanisms that elicit alternatives by randomly sampling voters for their favorite alternative. We design two families of mechanisms that provide constant (with respect to the number of voters and alternatives) $k^{th}$ moment of Distortion using just $k$ samples if all voters can then participate in a vote among the proposed alternatives, or $2k-1$ samples if only the sampled voters can participate. We also show that these numbers of samples are tight. Such mechanisms deviate from a constant approximation to OPT with probability that drops exponentially in the number of samples, independent of the total number of voters and alternatives. We conclude with simulations on real-world Participatory Budgeting data to qualitatively complement our theoretical insights.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Weighted Fairness with Minimal Disruptions

In this paper, we consider the following dynamic fair allocation problem: Given a sequence of job arrivals and departures, the goal is to maintain an approximately fair allocation of the resource against a target fair allocation policy, while minimizing the total number of disruptions, which is the number of times the allocation of any job is changed. We consider a rich class of fair allocation policies that significantly generalize those considered in previous work. We first consider the models where jobs only arrive, or jobs only depart. We present tight upper and lower bounds for the number of disruptions required to maintain a constant approximate fair allocation every time step. In particular, for the canonical case where jobs have weights and the resource allocation is proportional to the job's weight, we show that maintaining a constant approximate fair allocation requires $Θ(\log^* n)$ disruptions per job, almost matching the bounds in prior work for the unit weight case. For the more general setting where the allocation policy only decreases the allocation to a job when new jobs arrive, we show that maintaining a constant approximate fair allocation requires $Θ(\log n)$ disruptions per job. We then consider the model where jobs can both arrive and depart. We first show strong lower bounds on the number of disruptions required to maintain constant approximate fairness for arbitrary instances. In contrast we then show that there there is an algorithm that can maintain constant approximate fairness with $O(1)$ expected disruptions per job if the weights of the jobs are independent of the jobs arrival and departure order. We finally show how our results can be extended to the setting with multiple resources.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Predict and Match: Prophet Inequalities with Uncertain Supply

We consider the problem of selling perishable items to a stream of buyers in order to maximize social welfare. A seller starts with a set of identical items, and each arriving buyer wants any one item, and has a valuation drawn i.i.d. from a known distribution. Each item, however, disappears after an a priori unknown amount of time that we term the horizon for that item. The seller knows the (possibly different) distribution of the horizon for each item, but not its realization till the item actually disappears. As with the classic prophet inequalities, the goal is to design an online pricing scheme that competes with the prophet that knows the horizon and extracts full social surplus (or welfare). Our main results are for the setting where items have independent horizon distributions satisfying the monotone-hazard-rate (MHR) condition. Here, for any number of items, we achieve a constant-competitive bound via a conceptually simple policy that balances the rate at which buyers are accepted with the rate at which items are removed from the system. We implement this policy via a novel technique of matching via probabilistically simulating departures of the items at future times. Moreover, for a single item and MHR horizon distribution with mean $μ$, we show a tight result: There is a fixed pricing scheme that has competitive ratio at most $2 - 1/μ$, and this is the best achievable in this class. We further show that our results are best possible. First, we show that the competitive ratio is unbounded without the MHR assumption even for one item. Further, even when the horizon distributions are i.i.d. MHR and the number of items becomes large, the competitive ratio of any policy is lower bounded by a constant greater than $1$, which is in sharp contrast to the setting with identical deterministic horizons.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice

We study social choice mechanisms in an implicit utilitarian framework with a metric constraint, where the goal is to minimize \textit{Distortion}, the worst case social cost of an ordinal mechanism relative to underlying cardinal utilities. We consider two additional desiderata: Constant sample complexity and Squared Distortion. Constant sample complexity means that the mechanism (potentially randomized) only uses a constant number of ordinal queries regardless of the number of voters and alternatives. Squared Distortion is a measure of variance of the Distortion of a randomized mechanism. Our primary contribution is the first social choice mechanism with constant sample complexity \textit{and} constant Squared Distortion (which also implies constant Distortion). We call the mechanism Random Referee, because it uses a random agent to compare two alternatives that are the favorites of two other random agents. We prove that the use of a comparison query is necessary: no mechanism that only elicits the top-k preferred alternatives of voters (for constant k) can have Squared Distortion that is sublinear in the number of alternatives. We also prove that unlike any top-k only mechanism, the Distortion of Random Referee meaningfully improves on benign metric spaces, using the Euclidean plane as a canonical example. Finally, among top-1 only mechanisms, we introduce Random Oligarchy. The mechanism asks just 3 queries and is essentially optimal among the class of such mechanisms with respect to Distortion. In summary, we demonstrate the surprising power of constant sample complexity mechanisms generally, and just three random voters in particular, to provide some of the best known results in the implicit utilitarian framework.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties

We study social choice rules under the utilitarian distortion framework, with an additional metric assumption on the agents' costs over the alternatives. In this approach, these costs are given by an underlying metric on the set of all agents plus alternatives. Social choice rules have access to only the ordinal preferences of agents but not the latent cardinal costs that induce them. Distortion is then defined as the ratio between the social cost (typically the sum of agent costs) of the alternative chosen by the mechanism at hand, and that of the optimal alternative chosen by an omniscient algorithm. The worst-case distortion of a social choice rule is, therefore, a measure of how close it always gets to the optimal alternative without any knowledge of the underlying costs. Under this model, it has been conjectured that Ranked Pairs, the well-known weighted-tournament rule, achieves a distortion of at most 3 [Anshelevich et al. 2015]. We disprove this conjecture by constructing a sequence of instances which shows that the worst-case distortion of Ranked Pairs is at least 5. Our lower bound on the worst case distortion of Ranked Pairs matches a previously known upper bound for the Copeland rule, proving that in the worst case, the simpler Copeland rule is at least as good as Ranked Pairs. And as long as we are limited to (weighted or unweighted) tournament rules, we demonstrate that randomization cannot help achieve an expected worst-case distortion of less than 3. Using the concept of approximate majorization within the distortion framework, we prove that Copeland and Randomized Dictatorship achieve low constant factor fairness-ratios (5 and 3 respectively), which is a considerable generalization of similar results for the sum of costs and single largest cost objectives. In addition to all of the above, we outline several interesting directions for further research in this space.

0 citations0 reviewsNo code linkedOpen access