Author name cluster

Pooja 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.

7 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Online Fair Division With Subsidy: When Do Envy-Free Allocations Exist, and at What Cost?

Pooja Kulkarni
Ruta Mehta
Vishnu V. Narayan
Tomasz Ponitka

We study the problem of fairly allocating 𝑚 indivisible items arriving online, among 𝑛 (offline) agents. Although envy-freeness has emerged as the archetypal fairness notion, envy-free (EF) allocations need not exist with indivisible items. To bypass this, a prominent line of research demonstrates that there exist allocations that can be made envy-free by allowing a subsidy. Extensive work in the offline setting has focused on finding such envy-freeable allocationswithboundedsubsidy. Weextendthisliteraturetoanonline setting where items arrive one at a time and must be immediately and irrevocably allocated. Our contributions are two-fold: • Maintaining EF Online: We show that envy-freeability cannot always be preserved online when the valuations are submodular or supermodular, even with binary marginals. In contrast, we design online algorithms that maintain envy-freeability at every step for the class of additive valuations, and for its superclasses including 𝑘-demand valuations and SPLC valuations. • Ensuring Low Subsidy: We investigate the quantity of subsidy required to guarantee envy-freeness online. Surprisingly, even for additive valuations, the minimum subsidy may be as large as Ω(𝑚𝑛), incontrasttotheofflinesetting, wheretheboundis𝑂(𝑛). On the positive side, we identify valuation classes where the minimum subsidy is small (i. e. , does not depend on𝑚), including 𝑘-valued, rank-one, restricted additive, and identical valuations, and we obtain (mostly) tight subsidy bounds for these classes.

PDF

NeurIPS Conference 2025 Conference Paper

On the Existence and Complexity of Core-Stable Data Exchanges

Jiaxin Song
Pooja Kulkarni
Parnian Shahkar
Bhaskar Ray Chaudhury

The rapid growth of data-driven technologies and the emergence of various data-sharing paradigms have underscored the need for efficient and stable data exchange protocols. In any such exchange, agents must carefully balance the benefit of acquiring valuable data against the cost of sharing their own. Ensuring stability in these exchanges is essential to prevent agents—or groups of agents—from departing and conducting local (and potentially more favorable) exchanges among themselves. To address this, we study a model where $n$ agents participate in a data exchange. Each agent has an associated payoff for the data acquired from other agents and a cost incurred during sharing its own data. The net utility of an agent is payoff minus the cost. We adapt the classical notion of *core-stability* from cooperative game theory to data exchange. A data exchange is core-stable if no subset of agents has any incentive to deviate to a different exchange. We show that a core-stable data exchange is guaranteed to exist when agents have concave payoff functions and convex cost functions-- a setting typical in domains like PAC learning and random discovery models. We show that relaxing either of the foregoing conditions may result in the nonexistence of core-stable data exchanges. Then, we prove that finding a core-stable exchange is *PPAD-hard*, even when the potential blocking coalitions are restricted to constant size. To the best of our knowledge, this provides the first known PPAD-hardness result for core-like guarantees in data economics. Finally, we show that data exchange can be modelled as a *balanced* $n$-person game. This immediately gives a pivoting algorithm via Scarf's theorem [Scarf1967core]. We show that the pivoting algorithm works well in practice through our empirical results.

PDF Details

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

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

AAMAS Conference 2019 Conference Paper

Fair Division of Indivisible Goods Among Strategic Agents

Siddharth Barman
Ganesh Ghalme
Shweta Jain
Pooja Kulkarni
Shivika Narang

We study fair division of indivisible goods among strategic agents in a single-parameter environment. This work specifically considers fairness in terms of envy freeness up to one good (EF1) and maximin share guarantee (MMS). We show that (in a single-parameter environment) the problem of maximizing welfare, subject to the constraint that the allocation of the indivisible goods is EF1, admits a polynomial-time, 1/2-approximate, truthful auction. Under MMS setup, we develop a truthful auction which efficiently finds an allocation wherein each agent gets a bundle of value at least (1/2 − ε) times her maximin share and the welfare of the computed allocation is at least the optimal, here ε > 0 is a fixed constant. Our results for EF1 and MMS are based on establishing interesting majorization inequalities.

PDF