Search Results

Documents authored by Kulkarni, Pooja

Document
DOI: 10.4230/LIPIcs.ITCS.2024.8
Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations

Authors: Siddharth Barman, Anand Krishna, Pooja Kulkarni, and Shivika Narang

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We study the problem of allocating indivisible goods among n agents with the objective of maximizing Nash social welfare (NSW). This welfare function is defined as the geometric mean of the agents' valuations and, hence, it strikes a balance between the extremes of social welfare (arithmetic mean) and egalitarian welfare (max-min value). Nash social welfare has been extensively studied in recent years for various valuation classes. In particular, a notable negative result is known when the agents' valuations are complement-free and are specified via value queries: for XOS valuations, one necessarily requires exponentially many value queries to find any sublinear (in n) approximation for NSW. Indeed, this lower bound implies that stronger query models are needed for finding better approximations. Towards this, we utilize demand oracles and XOS oracles; both of these query models are standard and have been used in prior work on social welfare maximization with XOS valuations. We develop the first sublinear approximation algorithm for maximizing Nash social welfare under XOS valuations, specified via demand and XOS oracles. Hence, this work breaks the O(n)-approximation barrier for NSW maximization under XOS valuations. We obtain this result by developing a novel connection between NSW and social welfare under a capped version of the agents' valuations. In addition to this insight, which might be of independent interest, this work relies on an intricate combination of multiple technical ideas, including the use of repeated matchings and the discrete moving knife method. In addition, we partially complement the algorithmic result by showing that, under XOS valuations, an exponential number of demand and XOS queries are necessarily required to approximate NSW within a factor of (1 - 1/e).
Cite as

Siddharth Barman, Anand Krishna, Pooja Kulkarni, and Shivika Narang. Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{barman_et_al:LIPIcs.ITCS.2024.8,
  author =	{Barman, Siddharth and Krishna, Anand and Kulkarni, Pooja and Narang, Shivika},
  title =	{{Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.8},
  URN =		{urn:nbn:de:0030-drops-195366},
  doi =		{10.4230/LIPIcs.ITCS.2024.8},
  annote =	{Keywords: Discrete Fair Division, Nash Social Welfare, XOS Valuations}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.16
Approximation Algorithms for Envy-Free Cake Division with Connected Pieces

Authors: Siddharth Barman and Pooja Kulkarni

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
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 requirement that each agent must receive a connected piece of the cake, we develop approximation algorithms for finding envy-free (fair) cake divisions. In particular, this work improves the state-of-the-art additive approximation bound for this fundamental problem. Our results hold for general cake division instances in which the agents' valuations satisfy basic assumptions and are normalized (to have value 1 for the cake). Furthermore, the developed algorithms execute in polynomial time under the standard Robertson-Webb query model. Prior work has shown that one can efficiently compute a cake division (with connected pieces) in which the additive envy of any agent is at most 1/3. An efficient algorithm is also known for finding connected cake divisions that are (almost) 1/2-multiplicatively envy-free. Improving the additive approximation guarantee and maintaining the multiplicative one, we develop a polynomial-time algorithm that computes a connected cake division that is both (1/4 +o(1))-additively envy-free and (1/2 - o(1))-multiplicatively envy-free. Our algorithm is based on the ideas of interval growing and envy-cycle elimination. In addition, we study cake division instances in which the number of distinct valuations across the agents is parametrically bounded. We show that such cake division instances admit a fully polynomial-time approximation scheme for connected envy-free cake division.
Cite as

Siddharth Barman and Pooja Kulkarni. Approximation Algorithms for Envy-Free Cake Division with Connected Pieces. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{barman_et_al:LIPIcs.ICALP.2023.16,
  author =	{Barman, Siddharth and Kulkarni, Pooja},
  title =	{{Approximation Algorithms for Envy-Free Cake Division with Connected Pieces}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.16},
  URN =		{urn:nbn:de:0030-drops-180685},
  doi =		{10.4230/LIPIcs.ICALP.2023.16},
  annote =	{Keywords: Fair Division, Envy-Freeness, Envy-Cycle Elimination}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.22
On Fair and Efficient Allocations of Indivisible Public Goods

Authors: Jugal Garg, Pooja Kulkarni, and Aniket Murhekar

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
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 select k ≤ m goods in a fair and efficient manner. We first establish fundamental connections between the models of private goods, public goods, and public decision making by presenting polynomial-time reductions for the popular solution concepts of maximum Nash welfare (MNW) and leximin. These mechanisms are known to provide remarkable fairness and efficiency guarantees in private goods and public decision making settings. We show that they retain these desirable properties even in the public goods case. We prove that MNW allocations provide fairness guarantees of Proportionality up to one good (Prop1), 1/n approximation to Round Robin Share (RRS), and the efficiency guarantee of Pareto Optimality (PO). Further, we show that the problems of finding MNW or leximin-optimal allocations are NP-hard, even in the case of constantly many agents, or binary valuations. This is in sharp contrast to the private goods setting that admits polynomial-time algorithms under binary valuations. We also design pseudo-polynomial time algorithms for computing an exact MNW or leximin-optimal allocation for the cases of (i) constantly many agents, and (ii) constantly many goods with additive valuations. We also present an O(n)-factor approximation algorithm for MNW which also satisfies RRS, Prop1, and 1/2-Prop.
Cite as

Jugal Garg, Pooja Kulkarni, and Aniket Murhekar. On Fair and Efficient Allocations of Indivisible Public Goods. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.FSTTCS.2021.22,
  author =	{Garg, Jugal and Kulkarni, Pooja and Murhekar, Aniket},
  title =	{{On Fair and Efficient Allocations of Indivisible Public Goods}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.22},
  URN =		{urn:nbn:de:0030-drops-155331},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.22},
  annote =	{Keywords: Public goods, Nash welfare, Leximin, Proportionality}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact