10 - 10:10 am | Opening remarks |
10:10 - 10:55 am | Uriel Feige |
10:55 - 11:30 am | Break |
11:30 - 12:15 pm | Sushmita Gupta |
12:15 - 12:45 pm | Govind Sankar |
12:45 - 2 pm | Lunch |
2 - 2:45 pm | Siddharth Barman
Fair Division Under Non-Monotone Valuations and Equitable Graph Cuts |
2:45 - 3:15 pm | Shivika Narang |
3:15 - 4 pm | Break |
4 - 4:45 pm | Swaprava Nath
Incentivize Contribution and Learn Parameters Too: Federated Learning with Strategic Data Owners |
4:45 - 5:30 pm | Open session |
10 - 10:45 am | Sanjukta Roy |
10:45 - 11:30 am | Break |
11:30 - 12:15 pm | Bhaskar Ray Chaudhury |
12:15 - 12:45 pm | Aditi Sethia
Envy-Free and Efficient Allocations for Graphical Valuations |
12:45 - 2 pm | Lunch |
2 - 2:45 pm | Vishwa Prakash |
2:45 - 3:15 pm | Vignesh Viswanathan |
3:15 - 4 pm | Break |
4 - 4:45 pm | Rohit Vaish |
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: TBD Abstract: TBD |
Govind Sankar Title: TBD Abstract: TBD |
Siddharth Barman Title: Fair Division Under Non-Monotone Valuations and Equitable Graph Cuts Abstract: In this talk, I will address discrete fair division under non-monotone valuations. We will show that even under non-monotone valuations (that are normalized and nonnegative), there always exist allocations wherein one can mitigate envy by reassigning at most three goods. As an interesting corollary of this result we obtain the existence of graph cuts that are equitable up to five times the maximum degree of the underlying graph. I will also present an approximation algorithm for efficiently finding such equitable cuts. Joint work with Paritosh Verma. |
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. |
Sanjukta Roy Title: Gerrymandering on Graphs Abstract: The electoral process divides geographical regions into districts, with each district electing one representative. These representatives take legislative decisions, encouraging political parties to capture as many districts as possible. Gerrymandering is the practice of altering district boundaries to benefit a particular candidate or party. Mathematically, the electoral district designer (gerrymanderer) attempts to partition a weighted graph into k connected components (districts) such that its favourite party wins more districts than any other party. We will design FPT algorithms for this problem for paths and general graphs. Next, we will consider the problem where gerrymanderer maximizes the wins of its favorite party. Our focus concerns the realistic case where the graph is planar. We prove that the gerrymandering problem is solvable in polynomial time in λ-outerplanar graphs, when the number of candidates and λ are constants and the vertex weights (voting weights) are polynomially bounded. In contrast, the problem is NP-complete in general planar graphs even with just two candidates. Thus, we will discuss inapproximability and approximation algorithms for gerrymandering planar graphs. |
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. |
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. |
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. |
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. |