Day 1 (Thursday, December 19th)

10 - 10:10 am Opening remarks
10:10 - 10:55 am Chair: Meghana Nasre Uriel Feige

A bidding game for allocation of indivisible goods

10:55 - 11:30 am Break
11:30 - 12:15 pm Chair: Rohit Vaish Sushmita Gupta

How to influence competition: Algorithms and Complexity of the Tournament Fixing Problem

12:15 - 12:45 pm Govind Sankar

Group Fairness and Multi-criteria Optimization in School Assignment

12:45 - 2 pm Lunch
2 - 2:45 pm Chair: Sanjukta Roy Rucha Kulkarni

1/2-MMS for SPLC valuations

2:45 - 3:15 pm Shivika Narang

Strategyproof Matching of Roommates to Rooms

3:15 - 4 pm Break
4 - 4:45 pm Chair: Siddharth Barman Swaprava Nath

Incentivize Contribution and Learn Parameters Too: Federated Learning with Strategic Data Owners

4:45 - 5:30 Bhaskar Ray Chaudhury

On the Theoretical Foundations of Data Exchange Economies

Day 2 (Friday, December 20th)

10 - 10:45 am Chair: Umang Bhaskar Sanjukta Roy

Fairness in Efficient House allocation

10:45 - 11:30 am Break
11:30 - 12:15 pm Chair: Sushmita Gupta Siddharth Barman

Compatibility of Fairness and Nash Welfare under Subadditive Valuations

12:15 - 12:45 pm Aditi Sethia

Envy-Free and Efficient Allocations for Graphical Valuations

12:45 - 2 pm Lunch
2 - 2:45 pm Chair: Swaprava Nath Vishwa Prakash

EFX Exists for Three Types of Agents

2:45 - 3:30 pm Vignesh Viswanathan

Fair Allocation under Simple Valuations

3:30 - 4 pm Break
4 - 4:45 pm Chair: Swaprava Nath Rohit Vaish

Fair Interval Scheduling of Indivisible Chores

Titles and Abstracts

Uriel Feige

Title: A bidding game for allocation of indivisible goods

Abstract: We consider allocation of indivisible goods to agents with possibly unequal entitlements, in a setting without payments. We shall briefly survey some share-based fairness notions associated with such settings. Thereafter we shall present an allocation mechanism referred to as the bidding game. The mechanism satisfies natural procedural fairness criteria. We ask whether in addition to the procedural fairness, the game has the property that the allocations output by this game (say, in equilibrium), enjoy ex-post fairness properties. To answer this, we design ``safe strategies", that guarantee to players that no matter what strategies other players use, they themselves will receive a bundle of value that matches, or at least approximates, their ``fair share". For additive and submodular classes of valuations, our results imply the existence of allocations that give agents a handsome fraction of their ``fair share" (in some cases, we also show that that this fraction is best possible), and moreover, lead to polynomial time algorithms for finding such allocations.

Sushmita Gupta

Title: How to influence competition: Algorithms and Complexity of the Tournament Fixing Problem

Abstract: Abstract: Over the last decade, extensive research has been conducted on the algorithmic aspects of designing single-elimination (SE) tournaments with varying objectives such as ensuring that a preferred player wins, or maximising the value of the whole tournament, or ensuring that certain subset of matches must take place, and so on.

In the first part of this talk we will discuss the background of this problem and these variants, where we assume that we have perfect information about the outcome of every match involving each pair of players. In the second part we will discuss a new algorithmic result in the setting where we have imperfect information about the various matchups.

Govind Sankar

Title: Group Fairness and Multi-criteria Optimization in School Assignment

Abstract: 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.

Rucha Kulkarni

Title: 1/2-MMS for SPLC valuations

Abstract: We will talk about the MMS problem in the setting of Separable piecewise linear and concave (SPLC) valuation functions. I will show a novel connection of the MMS problem with market equilibria, obtained through concave extensions of the valuation functions and the Any price share (APS) fairness notion. I will then show how this connection allows us to prove the existence and efficient computation of a 1/2-MMS allocation in the SPLC setting.

Shivika Narang

Title: Strategyproof Matching of Roommates to Rooms

Abstract: We initiate the study of matching roommates and rooms wherein the preferences of agents over other agents and rooms are complementary and represented by Leontief utilities. In this setting, 2n agents must be paired up and assigned to n rooms. Each agent has cardinal valuations over the rooms as well as compatibility values over all other agents. Under Leontief preferences, an agent's utility for a matching is the minimum of the two values. We focus on the tradeoff between maximizing utilitarian social welfare and strategyproofness. Our main result shows that—in a stark contrast to the additive case— under binary Leontief utilities, there exist strategyproof mechanisms that maximize the social welfare. We further devise a strategyproof mechanism that implements such a welfare maximizing algorithm and is parameterized by the number of agents. Along the way, we highlight several possibility and impossibility results, and give upper bounds and lower bounds for welfare with or without strategyproofness.

Swaprava Nath

Title: Incentivize Contribution and Learn Parameters Too: Federated Learning with Strategic Data Owners

Abstract: Classical federated learning (FL) assumes that the clients have a limited amount of noisy data with which they voluntarily participate and contribute towards learning a global, more accurate model in a principled manner. The learning happens in a distributed fashion without sharing the data with the center. However, these methods do not consider the incentive of an agent for participating and contributing to the process, given that data collection and running a distributed algorithm is costly for the clients. The question of rationality of contribution has been asked recently in the literature and some results exist that consider this problem. This talk addresses the question of simultaneous parameter learning and incentivizing contribution, which distinguishes it from the extant literature. Our first mechanism incentivizes each client to contribute to the FL process at a Nash equilibrium and simultaneously learn the model parameters. However, this equilibrium outcome can be away from the optimal, where clients contribute with their full data and the algorithm learns the optimal parameters. We propose a second mechanism with monetary transfers that is budget balanced and enables the full data contribution along with optimal parameter learning. Experiments show that these algorithms converge quite fast in practice and yield positive utility for everyone.

Bhaskar Ray Chaudhury

Title: On the Theoretical Foundations of Data Exchange Economies

Abstract: 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 free duplication i.e., there is no concept of limited supply with data as it can be replicated at zero marginal cost, and 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., a setting where agents in possession of datasets exchange data amongst each other 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 own data for profit. In this work, we propose a general framework for data-exchange from first principles. We investigate the existence and computation of a data-exchange satisfying the foregoing principles.

Sanjukta Roy

Title: Fairness in Efficient House allocation

Abstract: The classic house allocation problem is primarily concerned with finding a matching between a set of agents and a set of houses that guarantees some notion of economic efficiency (e.g. utilitarian welfare). While recent works have shifted focus on achieving fairness (e.g. minimizing the number of envious agents), they often come with notable costs on efficiency notions such as utilitarian or egalitarian welfare. We investigate the trade-offs between these welfare measures and several natural fairness measures that rely on the number of envious agents, the total (aggregate) envy of all agents, and maximum total envy of an agent. In particular, by focusing on envy-free allocations, we first show that, should one exist, finding an envy-free allocation with maximum utilitarian or egalitarian welfare is computationally tractable. We highlight a rather stark contrast between utilitarian and egalitarian welfare by showing that finding utilitarian welfare maximizing allocations that minimize the aforementioned fairness measures can be done in polynomial time while their egalitarian counterparts remain intractable (for the most part) even under binary valuations. We complement our theoretical findings by giving insights into the relationship between the different fairness measures and conducting empirical analysis.

Siddharth Barman

Title: Compatibility of Fairness and Nash Welfare under Subadditive Valuations

Abstract: This talk will establish a compatibility between fairness and efficiency, captured via Nash Social Welfare (NSW), under the broad class of subadditive valuations. We will show that, for subadditive valuations, there always exists an allocation that is envy-free up to one good (EF1) and has NSW at least half of the optimal; here, optimality is considered across all allocations, fair or otherwise.

It is known that EF1 and exact Pareto efficiency (PO) are incompatible with subadditive valuations. Hence, complementary to this negative result, the above-mentioned guarantee implies that we regain a compatibility by just considering a factor 1/2 approximation: EF1 can be achieved in conjunction with (1/2)-PO under subadditive valuations.

Joint work with Mashbat Suzuki, on Arxiv.

Aditi Sethia

Title: Envy-Free and Efficient Allocations for Graphical Valuations

Abstract: In this work, we consider the problem of fairly allocating a set of indivisible items among agents having valuations that are represented by a graph – agents appear as the vertices and items as the edges between them and each vertex only values the set of its incident edges. This is a recently introduced class of valuations (Christodoulou et.al. 2023) which is known to admit EFX allocations. We show that for binary graphical valuations, the existence of envy-free allocations can be determined in polynomial time (unlike the known computational hardness even for very special cases: in particular, even for identical valuations with two agents). In contrast, we also show that allowing for even slightly more general utilities {0 , 1, d} leads to intractability even for graphical valuations. This motivates other approaches to tractability, and to that end, we exhibit the fixed-parameter tractability of the problem parameterized by the vertex cover number of the graph. We also show that, all graphical instances that admit EF allocations also admit one that is non-wasteful. Since EFX allocations are possibly wasteful in this context, we also address the question of determining the price of fairness of EFX allocations.

Vishwa Prakash

Title: EFX Exists for Three Types of Agents

Abstract: In this talk, I will present new results on envy-free allocations of indivisible goods among agents with shared valuations. EFX, or envy-freeness up to any good, is a compelling relaxation of envy-freeness, previously known to exist in specific cases - most notably, for three agents [Chaudhury et al., EC 2020], and for any number of agents with just two valuations [Mahara, Discret. Appl. Math 2023]. Our work expands these boundaries, showing that EFX allocations exist for any number of agents with up to three types of agents with additive valuations. Additionally, I will discuss our findings on EFX allocations with charity for k groups of agents.

Vignesh Vishwanathan

Title: Fair Allocation under Simple Valuations

Abstract: My talk will focus on the problem of fairly dividing a set of indivisible items among agents who have preferences over these items. Recently, Babaioff, Ezra and Feige (2021) showed that Lorenz dominating allocations exist and can be efficiently computed when agents have matroid rank valuations. These allocations provide a wide array of fairness guarantees including maximizing Nash welfare, approximately satisfying envy freeness and approximately providing each agent their maximin share. In this talk, I will present a few attempts to generalize this result, both in terms of the valuation classes for which these allocations can be computed as well as the fairness guarantees that can be achieved.

We show that Lorenz dominating allocations exist in the mixed Manna setting when items are valued at -1, 0, or some positive integer c for all agents. These allocations can be efficiently computed even when agents have submodular valuations (for the most part). When all the items are goods and provide positive value, Lorenz dominating allocations may not exist even when each item is valued at 1 or c. However, we show, in this bivalved setting, the existence of allocations that maximize Nash welfare and approximately provide each agent their maximin share. Moving beyond bivalved valuations, we show that finding a max Nash welfare allocation is APX-hard in all settings when agents have trivalued valuations.

This talk is based on results from joint work with Cyrus Cousins, Zack Fitzsimmons, and Yair Zick.

Rohit Vaish

Title: Fair Interval Scheduling of Indivisible Chores

Abstract: We will discuss the problem of fairly assigning a set of discrete tasks, or chores, among a set of agents. Each chore has a designated start and finish time, and each agent can perform at most one chore at any time. We will explore the existence and computation of "fair" (specifically, envy-free up to one chore) and "efficient" (specifically, maximal or Pareto optimal) schedules under various settings. The presentation will cover novel technical ideas, including a color-switching technique and an application of the "cycle-plus-triangles" theorem (originally conjectured by Erdős) for achieving approximate envy-freeness. We will also highlight several open problems and directions for future work.

Joint work with Sarfaraz Equbal, Rohit Gurjar, Yatharth Kumar, Swaprava Nath, and Raghuvansh Saxena.

URL: https://arxiv.org/abs/2402.04353