Kamesh Munagala
YOU?
Author Swipe
View article: The Price of Competitive Information Disclosure
The Price of Competitive Information Disclosure Open
In many decision-making scenarios, individuals strategically choose what information to disclose to optimize their own outcomes. It is unclear whether such strategic information disclosure can lead to good societal outcomes. To address thi…
View article: Metric Distortion of Small-group Deliberation
Metric Distortion of Small-group Deliberation Open
We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most $k$, and these outcomes are aggregated by a social choice rule to find the winning alternative. We gr…
View article: Group Fairness and Multi-Criteria Optimization in School Assignment
Group Fairness and Multi-Criteria Optimization in School Assignment Open
We consider the problem of assigning students to schools when students have different utilities for schools and schools have limited capacities. The students belong to demographic groups, and fairness over these groups is captured either b…
View article: Majorized Bayesian Persuasion and Fair Selection
Majorized Bayesian Persuasion and Fair Selection Open
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 val…
View article: Differential Privacy with Multiple Selections
Differential Privacy with Multiple Selections Open
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 recomme…
View article: The Limits of Interval-Regulated Price Discrimination
The Limits of Interval-Regulated Price Discrimination Open
In this paper, we study third-degree price discrimination in a model first presented by Bergemann, Brooks, and Morris [2015]. Since such price discrimination might create market segments with vastly different posted prices, we consider reg…
View article: Individual Fairness in Graph Decomposition
Individual Fairness in Graph Decomposition Open
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.…
View article: Optimal Price Discrimination for Randomized Mechanisms
Optimal Price Discrimination for Randomized Mechanisms Open
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 …
View article: Data Exchange Markets via Utility Balancing
Data Exchange Markets via Utility Balancing Open
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 p…
View article: Classification with Partially Private Features
Classification with Partially Private Features Open
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 co…
View article: Achieving parity with human moderators
Achieving parity with human moderators Open
We describe the design of a video-conferencing platform for online deliberation that is self-moderating in the sense that it works without a human moderator. The platform includes an audio and video conferencing system and incorporates aut…
View article: Fair Price Discrimination
Fair Price Discrimination Open
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…
View article: Fair Multiwinner Elections with Allocation Constraints
Fair Multiwinner Elections with Allocation Constraints Open
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 b…
View article: Fairness in the Assignment Problem with Uncertain Priorities
Fairness in the Assignment Problem with Uncertain Priorities Open
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 prefe…
View article: Online Learning and Bandits with Queried Hints
Online Learning and Bandits with Queried Hints Open
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 choi…
View article: All Politics is Local: Redistricting via Local Fairness
All Politics is Local: Redistricting via Local Fairness Open
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…
View article: Auditing for Core Stability in Participatory Budgeting
Auditing for Core Stability in Participatory Budgeting Open
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 …
View article: Locally Fair Partitioning
Locally Fair Partitioning Open
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 P of the plane int…
View article: Optimal Price Discrimination for Randomized Mechanisms
Optimal Price Discrimination for Randomized Mechanisms Open
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 …
View article: Approximate Core for Committee Selection via Multilinear Extension and Market Clearing
Approximate Core for Committee Selection via Multilinear Extension and Market Clearing Open
Motivated by civic problems such as participatory budgeting and multiwinner elections, we consider the problem of public good allocation: Given a set of indivisible projects (or candidates) of different sizes, and voters with different mon…
View article: Robust Allocations with Diversity Constraints
Robust Allocations with Diversity Constraints Open
We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed to introduce diversity constraints on the items they are allocated. We motivate this via settings where the it…
View article: A Simple Mechanism for a Budget-Constrained Buyer
A Simple Mechanism for a Budget-Constrained Buyer Open
We study a classic Bayesian mechanism design setting of monopoly problem for an additive buyer in the presence of budgets. In this setting, a monopolist seller with m heterogeneous items faces a single buyer and seeks to maximize her reven…
View article: Fair for All: Best-effort Fairness Guarantees for Classification
Fair for All: Best-effort Fairness Guarantees for Classification Open
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 inhe…
View article: The Limits of an Information Intermediary in Auction Design
The Limits of an Information Intermediary in Auction Design Open
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…
View article: Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice
Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice Open
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…
View article: Approximately stable committee selection
Approximately stable committee selection Open
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 ordi…
View article: Predict and Match: Prophet Inequalities with Uncertain Supply
Predict and Match: Prophet Inequalities with Uncertain Supply Open
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…
View article: Advertising for Demographically Fair Outcomes
Advertising for Demographically Fair Outcomes Open
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…
View article: Predict and Match
Predict and Match Open
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…