A bidding game for allocation of indivisible goods

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

Group Fairness and Multi-criteria Optimization in School Assignment

1/2-MMS for SPLC valuations

Strategyproof Matching of Roommates to Rooms

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

On the Theoretical Foundations of Data Exchange Economies

Fairness in Efficient House allocation

Compatibility of Fairness and Nash Welfare under Subadditive Valuations

Envy-Free and Efficient Allocations for Graphical Valuations

EFX Exists for Three Types of Agents

Fair Allocation under Simple Valuations

Fair Interval Scheduling of Indivisible Chores

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.

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.

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.

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.

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.

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.

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.

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.

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.

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