Author name cluster

Rucha Kulkarni

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

AAAI Conference 2024 Conference Paper

1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations

Chandra Chekuri
Pooja Kulkarni
Rucha Kulkarni
Ruta Mehta

We study fair distribution of a collection of m indivisible goods among a group of n agents, using the widely recognized fairness principles of Maximin Share (MMS) and Any Price Share (APS). These principles have undergone thorough investigation within the context of additive valuations. We explore these notions for valuations that extend beyond additivity. First, we study approximate MMS under the separable (piecewise-linear) concave (SPLC) valuations, an important class generalizing additive, where the best known factor was 1/3-MMS. We show that 1/2-MMS allocation exists and can be computed in polynomial time, significantly improving the state-of-the-art. We note that SPLC valuations introduce an elevated level of intricacy in contrast to additive. For instance, the MMS value of an agent can be as high as her value for the entire set of items. We use a relax-and-round paradigm that goes through competitive equilibrium and LP relaxation. Our result extends to give (symmetric) 1/2-APS, a stronger guarantee than MMS. APS is a stronger notion that generalizes MMS by allowing agents with arbitrary entitlements. We study the approximation of APS under submodular valuation functions. We design and analyze a simple greedy algorithm using concave extensions of submodular functions. We prove that the algorithm gives a 1/3-APS allocation which matches the best-known factor. Concave extensions are hard to compute in polynomial time and are, therefore, generally not used in approximation algorithms. Our approach shows a way to utilize it within analysis (while bypassing its computation), and hence might be of independent interest.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Approximating APS Under Submodular and XOS Valuations with Binary Marginals

Pooja Kulkarni
Rucha Kulkarni
Ruta Mehta

We study the problem of fairly dividing indivisible goods among a set of agents under the fairness notion of Any Price Share (APS). APS is known to dominate the widely studied Maximin share (MMS). Since an exact APS allocation may not exist, the focus has traditionally been on the computation of approximate APS allocations. [4] studied the problem under additive valuations, and asked (𝑖) how large can the APS value be compared to the MMS value? and (𝑖𝑖) what guarantees can one achieve beyond additive functions. We partly answer these questions by considering valuations beyond additive, namely submodular and XOS functions, with binary marginals. For the submodular functions with binary marginals, also known as matroid rank functions (MRFs), we show that APS is exactly equal to MMS. Consequently, following [5] we show that an exact APS allocation exists and can be computed efficiently while maximizing the social welfare. Complementing this result, we show that it is NP-hard to compute the APS value within a factor of 5/6 for submodular valuations with three distinct marginals of {0, 1 2, 1}. We then consider binary XOS functions, which are immediate generalizations of binary submodular functions in the complement free hierarchy. In contrast to the MRFs setting, MMS and APS values are not equal under this case. Nevertheless, we can show that they are only a constant factor apart. In particular, we show that under binary XOS valuations, MMS ≤ APS ≤ 2 · MMS + 1. Further, we show that this is almost the tightest bound we can get using MMS, by giving an instance where APS ≥ 2 · MMS. The upper bound on APS, combined with [17], implies a 0. 1222-approximation for APS under binary XOS valuations. And the lower bound implies the nonexistence of better than 0. 5-APS even when agents have identical valuations, which is in sharp contrast to the guaranteed existence of exact MMS allocation when agent valuations are identical.

PDF

AAMAS Conference 2023 Conference Paper

Maximin Share Allocations for Assignment Valuations

Pooja Kulkarni
Rucha Kulkarni
Ruta Mehta

In this paper, we initiate the study of fairly dividing a set of indivisible resources under the fairness notion of Maximin share (MMS), for the setting where the agents have assignment or OXS valuation functions. These are a popular subclass of functions that lie between the well-studied submodular and additive function classes.

PDF

AAAI Conference 2021 Conference Paper

On the PTAS for Maximin Shares in an Indivisible Mixed Manna

Rucha Kulkarni
Ruta Mehta
Setareh Taki

We study fair allocation of indivisible items, both goods and chores, under the popular fairness notion of maximin share (MMS). The problem is well-studied when there are only goods (or chores), where a PTAS to compute the MMS values of agents is well-known. In contrast, for the mixed manna, a recent result showed that finding even an approximate MMS value of an agent up to any approximation factor in (0, 1] is NP-Hard for general instances. In this paper, we complement the hardness result by obtaining a PTAS to compute the MMS value, when its absolute value is at least 1/p times either the total value of all the goods or total cost of all the chores, for some constant p valued at least 1.

PDF Details

SODA Conference 2020 Conference Paper

Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings

Jugal Garg
Pooja Kulkarni
Rucha Kulkarni

We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For special cases of the problem with symmetric agents and additive(-like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with factor independent of m is known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations. In this paper, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations respectively. Both algorithms are simple to understand and involve non-trivial modifications of a greedy repeated matchings approach. Allocations of high valued items are done separately by un-matching certain items and re-matching them, by processes that are different in both algorithms. We show that these approaches achieve approximation factors of O ( n ) and O ( n log n ) for additive and submodular case respectively, which is independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envy-free up to one item (EF1). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of, hence resolving it completely.

Details