Search

We study the classic problem of fairly dividing a set of indivisible items among a set of agents and consider the popular fairness notion of envy-freeness up to one item (EF1). While in reality, the set of agents and items may vary, previous works have studied static settings, where no change can occur in the system. We initiate and develop a formal model to understand fair division under the variable input setting: here, there is an EF1 allocation that gets disrupted because of the loss/deletion of an item, or the arrival of a new agent, resulting in a near-EF1 allocation. The objective is to perform a sequence of transfers of items between agents to regain EF1 fairness by traversing only via near-EF1 allocations. We refer to this as the EF1-Restoration problem. In this work, we present algorithms for the above problem when agents have identical monotone valuations, and items are either all goods or all chores. Both of these algorithms achieve an optimal number of transfers (at most $m/n$, where $m$ and $n$ are the number of items and agents respectively) for identical additive valuations. Next, we consider a valuation class with graphical structure, introduced by Christodoulou et al. (EC'23), where each item is valued by at most two agents, and hence can be seen as an edge between these two agents in a graph. Here, we consider EF1 orientations on (multi)graphs - allocations in which each item is allocated to an agent who values it. While considering EF1 orientations on multi-graphs with additive binary valuations, we present an optimal algorithm for the EF1-Restoration problem. Finally, for monotone binary valuations, we show that the problem of deciding whether EF1-Restoration is possible is PSPACE-complete.

In this paper, we study the problem of finding an envy-free allocation of indivisible goods among multiple agents. EFX, which stands for envy-freeness up to any good, is a well-studied relaxation of the envy-free allocation problem and has been shown to exist for specific scenarios. For instance, EFX is known to exist when there are only three agents [Chaudhury et al, EC 2020], and for any number of agents when there are only two types of valuations [Mahara, Discret. Appl. Math 2023]. We show that EFX allocations exist for any number of agents when there are at most three types of additive valuations., Comment: Changes in the new version: Updated citation styles and added one new definition

We study the fair allocation of indivisible goods and chores under ordinal valuations for agents with unequal entitlements. We show the existence and polynomial time computation of weighted necessarily proportional up to one item (WSD-PROP1) allocations for both goods and chores, by reducing it to a problem of finding perfect matchings in a bipartite graph. We give a complete characterization of these allocations as corner points of a perfect matching polytope. Using this polytope, we can optimize over all allocations to find a min-cost WSD-PROP1 allocation of goods or most efficient WSD-PROP1 allocation of chores. Additionally, we show the existence and computation of sequencible (SEQ) WSD-PROP1 allocations by using rank-maximal perfect matching algorithms and show incompatibility of Pareto optimality under all valuations and WSD-PROP1. We also consider the Best-of-Both-Worlds (BoBW) fairness notion. By using our characterization, we show the existence and polynomial time computation of Ex-ante envy free (WSD-EF) and Ex-post WSD-PROP1 allocations under ordinal valuations for both chores and goods., Comment: Accepted at AAMAS 2024

We consider the stable marriage problem in the presence of ties in preferences and critical vertices. The input to our problem is a bipartite graph G = (A U B, E) where A and B denote sets of vertices which need to be matched. Each vertex has a preference ordering over its neighbours possibly containing ties. In addition, a subset of vertices in A U B are marked as critical and the goal is to output a matching that matches as many critical vertices as possible. Such matchings are called critical matchings in the literature and in our setting, we seek to compute a matching that is critical as well as optimal with respect to the preferences of the vertices. Stability, which is a well-accepted notion of optimality in the presence of two-sided preferences, is generalized to weak-stability in the presence of ties. It is well known that in the presence of critical vertices, a matching that is critical as well as weakly stable may not exist. Popularity is another well-investigated notion of optimality for the two-sided preference list setting, however, in the presence of ties (even with no critical vertices), a popular matching need not exist. We, therefore, consider the notion of relaxed stability which was introduced and studied by Krishnaa et. al. (SAGT 2020). We show that a critical matching which is relaxed stable always exists in our setting although computing a maximum-sized relaxed stable matching turns out to be NP-hard. Our main contribution is a 3/2 approximation to the maximum-sized critical relaxed stable matching for the stable marriage problem with two-sided ties and critical vertices., Comment: 18 pages, 3 figures

Allocation of scarce healthcare resources under limited logistic and infrastructural facilities is a major issue in the modern society. We consider the problem of allocation of healthcare resources like vaccines to people or hospital beds to patients in an online manner. Our model takes into account the arrival of resources on a day-to-day basis, different categories of agents, the possible unavailability of agents on certain days, and the utility associated with each allotment as well as its variation over time. We propose a model where priorities for various categories are modelled in terms of utilities of agents. We give online and offline algorithms to compute an allocation that respects eligibility of agents into different categories, and incentivizes agents not to hide their eligibility for some category. The offline algorithm gives an optimal allocation while the on-line algorithm gives an approximation to the optimal allocation in terms of total utility. Our algorithms are efficient, and maintain fairness among different categories of agents. Our models have applications in other areas like refugee settlement and visa allocation. We evaluate the performance of our algorithms on real-life and synthetic datasets. The experimental results show that the online algorithm is fast and performs better than the given theoretical bound in terms of total utility. Moreover, the experimental results confirm that our utility-based model correctly captures the priorities of categories

In this paper, we address the problem of determining an envy-free allocation of indivisible goods among multiple agents. EFX, which stands for envy-free up to any good, is a well-studied problem that has been shown to exist for specific scenarios, such as when there are only three agents with MMS valuations, as demonstrated by Chaudhury et al(2020), and for any number of agents when there are only two types of valuations as shown by Mahara(2020). Our contribution is to extend these results by showing that EFX exists for four agents with three distinct valuations. We further generalize this to show the existance of EFX allocations for n agents when n-2 of them have identical valuations.

In the popular edge problem, the input is a bipartite graph $G = (A \cup B,E)$ where $A$ and $B$ denote a set of men and a set of women respectively, and each vertex in $A\cup B$ has a strict preference ordering over its neighbours. A matching $M$ in $G$ is said to be {\em popular} if there is no other matching $M'$ such that the number of vertices that prefer $M'$ to $M$ is more than the number of vertices that prefer $M$ to $M'$. The goal is to determine, whether a given edge $e$ belongs to some popular matching in $G$. A polynomial-time algorithm for this problem appears in \cite{CK18}. We consider the popular edge problem when some men or women are prioritized or critical. A matching that matches all the critical nodes is termed as a feasible matching. It follows from \cite{Kavitha14,Kavitha21,NNRS21,NN17} that, when $G$ admits a feasible matching, there always exists a matching that is popular among all feasible matchings. We give a polynomial-time algorithm for the popular edge problem in the presence of critical men or women. We also show that an analogous result does not hold in the many-to-one setting, which is known as the Hospital-Residents Problem in literature, even when there are no critical nodes., Comment: Selected in ISAAC 2022 Conference

Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. Moreover, online matching problems have lots of applications in ad allocations and other e-commerce problems like product recommendation in digital marketing. We study two problems involving assigning {\em items} to {\em platforms}, where items belong to various {\em groups} depending on their attributes; the set of items are available offline and the platforms arrive online. In the first problem, we study online matchings with {\em proportional fairness constraints}. Here, each platform on arrival should either be assigned a set of items in which the fraction of items from each group is within specified bounds or be assigned no items; the goal is to assign items to platforms in order to maximize the number of items assigned to platforms. In the second problem, we study online matchings with {\em diversity constraints}, i.e. for each platform, absolute lower bounds are specified for each group. Each platform on arrival should either be assigned a set of items that satisfy these bounds or be assigned no items; the goal is to maximize the set of platforms that get matched. We study approximation algorithms and hardness results for these problems. The technical core of our proofs is a new connection between these problems and the problem of matchings in hypergraphs. Our experimental evaluation shows the performance of our algorithms on real-world and synthetic datasets exceeds our theoretical guarantees., Comment: 16 pages, Full version of a paper accepted in ECAI 2023

We study the probabilistic assignment of items to platforms that satisfies both group and individual fairness constraints. Each item belongs to specific groups and has a preference ordering over platforms. Each platform enforces group fairness by limiting the number of items per group that can be assigned to it. There could be multiple optimal solutions that satisfy the group fairness constraints, but this alone ignores item preferences. Our approach explores a `best of both worlds fairness' solution to get a randomized matching, which is ex-ante individually fair and ex-post group-fair. Thus, we seek a `probabilistic individually fair' distribution over `group-fair' matchings where each item has a `high' probability of matching to one of its top choices. This distribution is also ex-ante group-fair. Users can customize fairness constraints to suit their requirements. Our first result is a polynomial-time algorithm that computes a distribution over `group-fair' matchings such that the individual fairness constraints are approximately satisfied and the expected size of a matching is close to OPT. We empirically test this on real-world datasets. We present two additional polynomial-time bi-criteria approximation algorithms that users can choose from to balance group fairness and individual fairness trade-offs. For disjoint groups, we provide an exact polynomial-time algorithm adaptable to additional lower `group fairness' bounds. Extending our model, we encompass `maxmin group fairness,' amplifying underrepresented groups, and `mindom group fairness,' reducing the representation of dominant groups.', Comment: 31 pages. To appear in IJCAI'24

We consider the many-to-many bipartite matching problem in the presence of two-sided preferences and two-sided lower quotas. The input to our problem is a bipartite graph G=(A U B, E), where each vertex in A U B specifies a strict preference ordering over its neighbors. Each vertex has an upper quota and a lower quota denoting the maximum and minimum number of vertices that can be assigned to it from its neighborhood. In the many-to-many setting with two-sided lower quotas, informally, a critical matching is a matching which fulfils vertex lower quotas to the maximum possible extent. This is a natural generalization of the definition of critical matching in the one-to-one setting [Kavitha T., FSTTCS 2021]. Our goal in the given problem is to find a popular matching in the set of critical matchings. A matching is popular in a given set of matchings if it remains undefeated in a head-to-head election with any matching in that set. Here, vertices cast votes between pairs of matchings. We show that there always exists a matching that is popular in the set of critical matchings. We present an efficient algorithm to compute such a matching of the largest size. We prove the popularity of our matching using a dual certificate.

We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this paper. Each platform specifies the group fairness constraints through an upper bound on the number of items it can serve from each class. Additionally, each platform also has an upper bound on the total number of items it can serve. The goal is to assign items to platforms so as to maximize the number of items assigned while satisfying the upper bounds of each class. In some cases, there is a revenue associated with matching an item to a platform, then the goal is to maximize the revenue generated. This problem models several important real-world problems like ad-auctions, scheduling, resource allocations, school choice etc.We also show an interesting connection to computing a generalized maximum independent set on hypergraphs and ranking items under group fairness constraints. We show that if the classes are arbitrary, then the problem is NP-hard and has a strong inapproximability. We consider the problem in both online and offline settings under natural restrictions on the classes. Under these restrictions, the problem continues to remain NP-hard but admits approximation algorithms with small approximation factors. We also implement some of the algorithms. Our experiments show that the algorithms work well in practice both in terms of efficiency and the number of items that get assigned to some platform., Comment: 16 pages, to appear in IJCAI 2021

We show that given a SM instance G as input we can find a largest collection of pairwise edge-disjoint stable matchings of G in time linear in the input size. This extends two classical results: 1. The Gale-Shapley algorithm, which can find at most two ("extreme") pairwise edge-disjoint stable matchings of G in linear time, and 2. The polynomial-time algorithm for finding a largest collection of pairwise edge-disjoint perfect matchings (without the stability requirement) in a bipartite graph, obtained by combining K\"{o}nig's characterization with Tutte's f-factor algorithm. Moreover, we also give an algorithm to enumerate all maximum-length chains of disjoint stable matchings in the lattice of stable matchings of a given instance. This algorithm takes time polynomial in the input size for enumerating each chain. We also derive the expected number of such chains in a random instance of Stable Matching., Comment: Conference: International Workshop on Graph-Theoretic Concepts in Computer Science 2021 (https://wg2021.mimuw.edu.pl)

We consider the problem of matchings under two-sided preferences in the presence of maximum as well as minimum quota requirements for the agents. This setting, studied as the Hospital Residents with Lower Quotas (HRLQ) in literature, models important real world problems like assigning medical interns (residents) to hospitals, and teaching assistants to instructors where a minimum guarantee is essential. When there are no minimum quotas, stability is the de-facto notion of optimality. However, in the presence of minimum quotas, ensuring stability and simultaneously satisfying lower quotas is not an attainable goal in many instances. To address this, a relaxation of stability known as envy-freeness, is proposed in literature. In our work, we thoroughly investigate envy-freeness from a computational view point. Our results show that computing envy-free matchings that match maximum number of agents is computationally hard and also hard to approximate up to a constant factor. Additionally, it is known that envy-free matchings satisfying lower-quotas may not exist. To circumvent these drawbacks, we propose a new notion called relaxed stability. We show that relaxed stable matchings are guaranteed to exist even in the presence of lower-quotas. Despite the computational intractability of finding a largest matching that is feasible and relaxed stable, we give efficient algorithms that compute a constant factor approximation to this matching in terms of size., Comment: 31 pages, 12 figures

In this paper, we consider the problem of computing an optimal matching in a bipartite graph where elements of one side of the bipartition specify preferences over the other side, and one or both sides can have capacities and classifications. The input instance is a bipartite graph G=(A U P,E), where A is a set of applicants, P is a set of posts, and each applicant ranks its neighbors in an order of preference, possibly involving ties. Moreover, each vertex v in A U P has a quota q(v) denoting the maximum number of partners it can have in any allocation of applicants to posts - referred to as a {\em matching} in this paper. A classification for a vertex u is a collection of subsets of neighbors of u. Each subset (class) has an upper quota denoting the maximum number of vertices from the class that can be matched to u. The goal is to find a matching that is optimal amongst all the feasible matchings, which are matchings that respect quotas of all the vertices and classes. We consider two well-studied notions of optimality namely popularity and rank-maximality. The notion of rank-maximality involves finding a matching in $G$ with maximum number of rank-$1$ edges, subject to that, maximum number of rank-2 edges and so on. We present an O(|E|^2)-time algorithm for finding a feasible rank-maximal matching, when each classification is a laminar family. We complement this with an NP-hardness result when classes are non-laminar even under strict preference lists, and even when only posts have classifications, and each applicant has a quota of one. We show an analogous dichotomy result for computing a popular matching amongst feasible matchings (if one exists) in a bipartite graph with posts having capacities and classifications and applicants having a quota of one.

In this paper, we consider the Hospital Residents problem (HR) and the Hospital Residents problem with Lower Quotas (HRLQ). In this model with two sided preferences, stability is a well accepted notion of optimality. However, in the presence of lower quotas, a stable and feasible matching need not exist. For the HRLQ problem, our goal therefore is to output a good feasible matching assuming that a feasible matching exists. Computing matchings with minimum number of blocking pairs (MinBP) and minimum number of blocking residents (MinBR) are known to be NP-Complete. The only approximation algorithms for these problems work under severe restrictions on the preference lists. We present an algorithm which circumvents this restriction and computes a popular matching in the HRLQ instance. We show that on data-sets generated using various generators, our algorithm performs very well in terms of blocking pairs and blocking residents. Yokoi (ISAAC 2017) recently studied envy-free matchings for the HRLQ problem. We propose a simple modification to Yokoi's algorithm to output a maximal envy-free matching. We observe that popular matchings outperform envy-free matchings on several parameters of practical importance, like size, number of blocking pairs, number of blocking residents. In the absence of lower quotas, that is, in the Hospital Residents (HR) problem, stable matchings are guaranteed to exist. Even in this case, we show that popularity is a practical alternative to stability. For instance, on synthetic data-sets generated using a particular model, as well as on real world data-sets, a popular matching is on an average 8-10% larger in size, matches more number of residents to their top-choice, and more residents prefer the popular matching as compared to a stable matching. Our comprehensive study reveals the practical appeal of popular matchings for the HR and HRLQ problems.

We consider the well-studied Hospital Residents (HR) problem in the presence of lower quotas (LQ). The input instance consists of a bipartite graph $G = (\mathcal{R} \cup \mathcal{H}, E)$ where $\mathcal{R}$ and $\mathcal{H}$ denote sets of residents and hospitals respectively. Every vertex has a preference list that imposes a strict ordering on its neighbors. In addition, each hospital $h$ has an associated upper-quota $q^+(h)$ and lower-quota $q^-(h)$. A matching $M$ in $G$ is an assignment of residents to hospitals, and $M$ is said to be feasible if every resident is assigned to at most one hospital and a hospital $h$ is assigned at least $q^-(h)$ and at most $q^+(h)$ residents. Stability is a de-facto notion of optimality in a model where both sets of vertices have preferences. A matching is stable if no unassigned pair has an incentive to deviate from it. It is well-known that an instance of the HRLQ problem need not admit a feasible stable matching. In this paper, we consider the notion of popularity for the HRLQ problem. A matching $M$ is popular if no other matching $M'$ gets more votes than $M$ when vertices vote between $M$ and $M'$. When there are no lower quotas, there always exists a stable matching and it is known that every stable matching is popular. We show that in an HRLQ instance, although a feasible stable matching need not exist, there is always a matching that is popular in the set of feasible matchings. We give an efficient algorithm to compute a maximum cardinality matching that is popular amongst all the feasible matchings in an HRLQ instance.

We consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph G = (A U P,E), where A denotes a set of applicants, P is a set of posts, and there are ranks on edges which denote the preferences of applicants over posts. A matching M in G is called rank-maximal if it matches the maximum number of applicants to their rank 1 posts, subject to this the maximum number of applicants to their rank 2 posts, and so on. We consider this problem in a dynamic setting, where vertices and edges can be added and deleted at any point. Let n and m be the number of vertices and edges in an instance G, and r be the maximum rank used by any rank-maximal matching in G. We give a simple O(r(m+n))-time algorithm to update an existing rank-maximal matching under each of these changes. When r = o(n), this is faster than recomputing a rank-maximal matching completely using a known algorithm like that of Irving et al., which takes time O(min((r + n, r*sqrt(n))m).

Let G = (A U P, E) be a bipartite graph where A denotes a set of agents, P denotes a set of posts and ranks on the edges denote preferences of the agents over posts. A matching M in G is rank-maximal if it matches the maximum number of applicants to their top-rank post, subject to this, the maximum number of applicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximal matchings, which is a useful tool that encodes all rank-maximal matchings in an instance. The characterization leads to simple and efficient algorithms for several interesting problems. In particular, we give an efficient algorithm to compute the set of rank-maximal pairs in an instance. We show that the problem of counting the number of rank-maximal matchings is #P-Complete and also give an FPRAS for the problem. Finally, we consider the problem of deciding whether a rank-maximal matching is popular among all the rank-maximal matchings in a given instance, and give an efficient algorithm for the problem.

Let $G =$ be a solvable permutation group of the symmetric group $S_n$ given as input by the generating set $S$. We give a deterministic polynomial-time algorithm that computes an \emph{expanding generating set} of size $\tilde{O}(n^2)$ for $G$. More precisely, the algorithm computes a subset $T\subset G$ of size $\tilde{O}(n^2)(1/\lambda)^{O(1)}$ such that the undirected Cayley graph $Cay(G,T)$ is a $\lambda$-spectral expander (the $\tilde{O}$ notation suppresses $\log ^{O(1)}n$ factors). As a byproduct of our proof, we get a new explicit construction of $\varepsilon$-bias spaces of size $\tilde{O}(n\poly(\log d))(\frac{1}{\varepsilon})^{O(1)}$ for the groups $\Z_d^n$. The earlier known size bound was $O((d+n/\varepsilon^2))^{11/2}$ given by \cite{AMN98}., Comment: 15 pages