PKPooja Kulkarni

Pooja Kulkarni

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Pooja Kulkarni has a total of 5 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Cycle Cancellation for Submodular Fractional Allocations and Applications

    by Chandra Chekuri, Pooja Kulkarni, Ruta Mehta, Jan Vondrak

    We consider discrete allocation problem where $m$ indivisible goods are to be divided among $n$ agents. When agents' valuations are additive, the well-known cycle cancelling lemma by Lenstra, Shmoys, and Tardos plays a key role in design and analysis of rounding algorithms. In this paper, we prove an analogous lemma for the case of submodular valuations. Our algorithm removes cycles in the support graph of a fractional allocation while guaranteeing that each agent's value, measured using the multilinear extension, does not decrease. We demonstrate applications of the cycle-canceling algorithm, along with other ideas, to obtain new algorithms and results for three well-studied allocation objectives: max-min (Santa Claus problem), Nash social welfare (NSW), and maximin-share (MMS). For the submodular NSW problem, we obtain a $\frac{1}{5}$-approximation; for the MMS problem, we obtain a $\frac{1}{2}(1-1/e)$-approximation through new simple algorithms. For various special cases where the goods are "small" valued or the number of agents is constant, we obtain tight/best-known approximation algorithms. All our results are in the value-oracle model.

  • Open Access

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

    by Pooja Kulkarni, Ruta Mehta, Vishnu V. Narayan, Tomasz Ponitka

    We study the problem of fairly allocating $m$ indivisible items arriving online, among $n$ (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 allocations with bounded subsidy. We extend this literature to an online setting where items arrive one at a time and must be immediately and irrevocably allocated. Our contributions are two-fold: 1. 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 $k$-demand and SPLC valuations. 2. 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 $Ω(mn)$, in contrast to the offline setting, where the bound is $O(n)$. On the positive side, we identify valuation classes where the minimum subsidy is small (i.e., does not depend on $m$), including $k$-valued, rank-one, restricted additive, and identical valuations, and we obtain (mostly) tight subsidy bounds for these classes.