5 citations · 10 across the 5 of their papers we have counts for
12 papers
Single-or-Sample: Online Fair Allocation for Combinatorial Agents
Shuchi Chawla, Zhiyi Huang, Pooja Kulkarni +2
We study the problem of fairly allocating indivisible goods among agents who arrive online, under the notion of maximin share (MMS) fairness. Fair allocation with online ar…
Cycle Cancellation for Submodular Fractional Allocations and Applications
Chandra Chekuri, Pooja Kulkarni, Ruta Mehta +1
We consider discrete allocation problem where indivisible goods are to be divided among agents. When agents' valuations are additive, the well-known cycle cancelling lemma…
Online Fair Division With Subsidy: When Do Envy-Free Allocations Exist, and at What Cost?
Pooja Kulkarni, Ruta Mehta, Vishnu V. Narayan +1
We study the problem of fairly allocating indivisible items arriving online, among (offline) agents. Although envy-freeness has emerged as the archetypal fairness notion, e…
Covering a Few Submodular Constraints and Applications
Tanvi Bajpai, Chandra Chekuri, Pooja Kulkarni
We consider the problem of covering multiple submodular constraints. Given a finite ground set , a cost function , monotone submodular functio…
Online Fair Division: Towards Ex-Post Constant MMS Guarantees
Pooja Kulkarni, Ruta Mehta, Parnian Shahkar
We investigate the problem of fairly allocating indivisible items among sequentially arriving agents with additive valuations, under the sought-after fairness notion of max…
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 Maxi…
1/2 Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations
Chandra Chekuri, Pooja Kulkarni, Rucha Kulkarni +1
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 Sh…
Approximation Algorithms for Envy-Free Cake Division with Connected Pieces
Siddharth Barman, Pooja Kulkarni
Cake cutting is a classic model for studying fair division of a heterogeneous, divisible resource among agents with individual preferences. Addressing cake division under a typical…
Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations
Siddharth Barman, Anand Krishna, Pooja Kulkarni +1
We study the problem of allocating indivisible goods among agents with the objective of maximizing Nash social welfare (NSW). This welfare function is defined as the geometric…
On Fair and Efficient Allocations of Indivisible Public Goods
Jugal Garg, Pooja Kulkarni, Aniket Murhekar
We study fair allocation of indivisible public goods subject to cardinality (budget) constraints. In this model, we have n agents and m available public goods, and we want to selec…
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-…
Fair Division of Indivisible Goods Among Strategic Agents
Siddharth Barman, Ganesh Ghalme, Shweta Jain +2
We study fair division of indivisible goods in a single-parameter environment. In particular, we develop truthful social welfare maximizing mechanisms for fairly allocating indivis…