3 papers
cs.GT2025
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…
cs.GT2025
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…
cs.GT2025
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…