Eklavya Sharma

Jugal Garg, Eklavya Sharma

We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and $2/3$-MMS allocation can be obtained using the Envy-Cycle-Elimination (ECE) algorithm. In this work, we explore whether this algorithm can be randomized to also ensure ex-ante proportionality. For two agents, we show that a randomized variant of ECE can compute an ex-post EFX and ex-ante envy-free allocation in near-linear time. However, for three agents, we show that several natural randomization methods for ECE fail to achieve ex-ante proportionality.

Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma et al.

We study revenue-optimal pricing in data markets with rational, budget-constrained buyers. Such a market offers multiple datasets for sale, and buyers aim to improve the accuracy of their prediction tasks by acquiring data bundles. The market's objective is to price datasets to maximize total revenue, considering that buyers with quasi-linear utilities choose their bundles optimally under budget constraints. We allow the buyers to purchase fractions of datasets, and the amount they pay is proportional to the fraction they receive. Although competitive equilibrium gives revenue-optimal pricing in rivalrous markets with quasi-linear buyers, we show that revenue maximization in data markets is APX-hard. Despite the hardness, we design a 2-approximation algorithm when datasets arrive online, and a $(1-1/e)^{-1}$-approximation algorithm for the offline setting.