4 papers
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…