The Schedule

9:30 - 10:15

Ariel Procaccia

Generative Social Choice

The mathematical study of voting, social choice theory, has traditionally only been applicable to choices among a few predetermined alternatives, but not to open-ended decisions such as collectively selecting a textual statement. This limitation is addressed by generative social choice, a design methodology for open-ended democratic processes that combines the rigor of social choice theory with the capability of large language models to generate text and extrapolate preferences. I’ll introduce a framework that divides the design of AI-augmented democratic processes into two components: first, proving that the process satisfies representation guarantees when given access to oracle queries; second, empirically validating that these queries can be approximately implemented using a large language model. I’ll also discuss the application of this framework to the problem of summarizing free-form opinions into a proportionally representative slate of opinion statements. By providing rigorous guarantees, generative social choice could alleviate concerns about AI-driven democratic innovation and help unlock its potential.

10:45 - 11:30

Ian Kash

Fair AI for Rich Decisions

We have substantial theory about what fairness means and how to achieve it in classification settings.  However, in richer settings, such as resource allocation, clustering, and reinforcement learning, how to apply this is less clear.  I'll discuss a general approach to extending the notion of group fairness to such richer settings and examine some specific challenges in the context of resource allocation.

1:30 - 2:30

Lightning session 

1:30 - 1:50

Sean R. Sinclair

Envy-Efficiency Tradeoffs in Dynamic Fair Allocation

In many societal settings, decision-makers are tasked with allocating a scarce resource in a way that balances fairness and efficiency.  To handle these competing objectives, practitioners often resort to ad-hoc rules of thumb or optimize a weighted combination. The tradeoff between these two desiderata, on the other hand, is often not well understood or difficult to formally characterize.  In this talk we introduce a line a work that seeks to provide tight characterizations of envy-efficiency tradeoffs in dynamic fair allocation, for a variety of practically motivated settings.  We first consider a classical setting in which the decision-maker is faced with a stochastic number of arrivals to which they must allocated a fixed budget of resources throughout the horizon, and illustrate the impact of demand uncertainty on the envy-efficiency tradeoff.   However, this ignores a practical reality of many real-world settings, such as food banks, in which resources are perishable.  We demonstrate that perishability significantly modifies the envy-efficiency trade-off in this latter setting, and requires the development of new algorithmic tools. Simulations calibrated to a real-world dataset demonstrate the robustness of our algorithmic framework across a variety of perishing regimes.

1:50 - 2:10

Pooja R. Kulkarni

Approximating Nash Social Welfare and Beyond Additive Valuations

Given a set of agents and a set of resources (goods), we want to divide the goods fairly among the agents. The agents have preferences over the set of goods that are captured via cardinal functions i.e., given a set of goods, we get a single number describing the value of the agent for the good. These are called the valuation functions. There are two aspects of the problem that determine its complexity (1) What fairness notion is used (2) What structure do we have on the valuation functions. For the fairness notion, in this talk, I will focus on the notion of Nash social welfare. For the valuation functions, I will focus on XOS valuation function and also touch on submodular valuation functions. Both these classes belong in the complement-free hierarchy and significantly generalize the class of additive valuations. Neither of these classes admit polynomial sized representations and therefore must be queried through oracle accesses. While it was known in a previous work that under value oracles (where one can query the value of any set), we cannot get any approximation to NSW that is better than linear in number of agents, we show using stronger oracles to the valuation functions a sublinear approximation algorithm.

2:10 - 2:30

Stavros Sintos

Improved Approximation Algorithms for (Fair) Relational Clustering

Clustering is one of the most important analytical tools used in various applications like data summarization, unsupervised learning, classification, anomaly detection, and recommendation systems. In relational databases, where data is distributed across multiple tables, efficient clustering is essential yet challenging due to the computational complexity of joining tables. We tackle this challenge by developing efficient approximation algorithms for k-center, k-median, and k-means clustering on relational data, eliminating the need to compute all join query results. We also define the notion of group fairness in relational data and extend our methods to fair relational clustering.

3:00 - 3:45

Kamesh Munagala

Majorized Bayesian Persuasion and Fair Selection

Selection under uncertainty is a fundamental problem arising in various domains such as college admissions, hiring decisions, and public resource allocation. We model this problem 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, we show that 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.

4:00 - 4:45

Bhaskar Ray Chowdhury

Fair and Stable Data Exchange Economies

The immense success of ML systems relies heavily on large-scale high-quality data. The high demand for data has led to several paradigms that involve selling, exchanging, and sharing data. This naturally motivates studying economic processes that involve data as an asset. However, data differs from classical economic assets in terms of (i) free duplication i.e., there is no concept of limited supply with data as it can be replicated at zero marginal cost, and (ii) ex-ante unverifiable, i.e., it is difficult to estimate the utility of the data to an agent apriori, without using it. These distinctions cause fundamental differences between economic processes involving data and those involving other assets.

We investigate the parallel of exchange markets (Arrow-Debreu markets) in settings where data is the asset, i.e., where agents in possession of datasets exchange data fairly and voluntarily for mutual benefit without any monetary compensation. This is relevant in settings involving non-profit organizations that are seeking to improve their ML models through data-exchange with other organizations and are not allowed to sell their data for profit. This work proposes a general framework for data-exchange from first principles. We investigate the existence and computation of a data-exchange satisfying the foregoing principles.

9:30 - 10:15

Aravind Srinivasan

Fairness, Randomization, and Approximation Algorithms

We discuss approaches to fair allocations/service in combinatorial optimization, wherein approximation and randomization will both be crucial. Clustering problems will be among those studied through the lens of fairness; specifically, we will show how randomized-rounding algorithms for linear-programming relaxations can lead to useful (per-user) probabilistic guarantees for a range of problems. 

10:30 - 11:15

Edith Elkind

Towards Fair and Efficient Public Transportation: A Bus Stop Model

We consider a stylized formal model of public transportation, where a set of agents need to travel along a given road, and there is a bus that runs the length of this road. Each agent has a left terminal and a right terminal between which they wish to travel; they can walk all the way, or walk to/from the nearest stop and use the bus for the rest of their journey. The bus can make a fixed number of stops, and the planner needs to select locations for these stops. We study notions of efficiency and fairness for this setting. First, we give a polynomial-time algorithm for computing a solution that minimizes the total travel time; our approach can capture further extensions of the base model, such as more general cost functions or existing infrastructure. Second, we develop a polynomial-time algorithm that outputs solutions with provable fairness guarantees (such as a variant of the justified representation axiom or $2$-approximate core) as long as the agents' costs only depend on the distance they need to walk. Our simulations indicate that our algorithm almost always outputs fair solutions, even for parameter regimes that do not admit theoretical guarantees.

11:30 - 12:15

Arpita Biswas

Fair Allocation of Conflicting Indivisible Resources

The problem of fair allocation of indivisible items becomes more challenging when certain item pairs conflict with each other, rendering those pairs incompatible while allocating them to the same agent. This problem setting finds its relevance in scenarios such as course allocation, where students (the agents) express preferences for courses (the items), and courses may possess conflicting schedules which is represented by an interval conflict graph. Additionally, courses have finite seat capacities, and students may have constraints on the number of courses they can enroll in. The goal is to obtain a fair and feasible allocation of items among the agents while ensuring that each allocated bundle constitutes an independent set within the interval conflict graph. While the problem is NP-hard for a general conflict graph, we devise efficient solutions when items are represented as intervals, that is, considering an interval conflict graph. In this talk, I’ll discuss various fairness notions, such as maximin fairness and almost envy freeness, that are pertinent to this problem setting and present solutions using a number of interesting techniques that are tailored to different assumptions on the agents’ preferences over a bundle of items.

1:15 - 2:00

Ali Vakilian

Exploring Fairness in Clustering: Definitions, Techniques, and Applications

Clustering is a fundamental task in machine learning with applications ranging from data partitioning (e.g., in loan approval processes) and summarization (e.g., for search queries) to facility location planning (e.g., opening polling stations). Given this wide range of applications, ensuring fairness in clustering is essential, and further each application often requires a distinct fairness notion.

In this talk, I will discuss several well-studied definitions and algorithmic techniques for fair clustering, focusing on fair representation, min-max fairness, and briefly, individual fairness.

The presentation is based on several collaborations [BIOSVW'ICML19, DMV'FAccT22, HMV'ICML23, MV'COLT21, CMV'SODA22, MV'ICML21, VY'AISTATS24, AAKKMSV'ICML22, ACLSSV'NeurIPS'23, MV'AISTATS24].

2:15 - 3:15

Lightning session 

2:15 - 2:35

Shirley Zhang

Honor Among Bandits: No-Regret Learning for Online Fair Division

We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize social welfare subject to allocating the goods fairly in expectation. When a player’s value for an item is unknown at the time of allocation, we show that this problem reduces to a variant of (stochastic) multi-armed bandits, where there exists an arm for each player’s value for each type of good. At each time step, we choose a distribution over arms which determines how the next item is allocated. We consider two sets of fairness constraints for this problem: envy-freeness in expectation and proportionality in expectation. Our main result is the design of an explore-then-commit algorithm that achieves O˜(T^2/3) regret while maintaining either fairness constraint. This result relies on unique properties fundamental to fair-division constraints that allow faster rates of learning, despite the restricted action space. We also prove a lower bound of Ω˜(T^2/3) regret for our setting, showing that our results are tight. Joint work with Ben Schiffer and Ariel Procaccia.

2:35 - 2:55

Marina Knittel

Individually Fair Rank Aggregation and Pivot Algorithm

The centerpiece of this work focuses on the pivot algorithm, a famous algorithmic technique that lends itself to simple and efficient algorithms for many applications including correlation clustering, consensus clustering, feedback arc set, and rank aggregation. Our main results show that the pivot algorithm: 1) guarantees O(k\log n)-individual fairness on adversarial data and O(\log^2(kn))-individual fairness on Mallows-generated data, 2) cannot guarantee better than \Theta(k)-individual fairness on adversarial data, and 3) cannot ensure any demographic fairness even on O(1) rankings and groups. Experimentally, we see that the pivot algorithm may actually improve with k in practical settings. We believe the analysis of the pivot algorithm will play a vital role in the further development of this field.

2:55 - 3:15

Aleksandra Korolova

Analyzing Meta's Implementation for Ensuring Fairness in Ad Delivery

Ad delivery algorithms play an important role in shaping access to information and economic opportunities. Concerns of bias and discrimination in these algorithms have led to a first of its kind settlement between the Department of Justice and Meta in 2022, requiring Meta to change its ad delivery system. In this talk, I will present our understanding of key aspects of the settlement and Meta's implementation of it, and raise questions about optimality and sufficiency of the implementation to address discrimination.