27 Search Results for "Procaccia, Ariel D."

Document
DOI: 10.4230/LIPIcs.SWAT.2026.8
Submodular Max-Min Allocation Under Identical Valuations

Authors: Kimon Boehmer

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In the problem of Submodular Max-Min Allocation, we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a 0.4-approximation, improving the previously best factor of 10/27 ≈ 0.37 by Uziahu and Feige. Furthermore, we study the integrality gap of the configuration LP when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players' allocations must be independent in k given matroids, we derive a 𝒪(k)-estimation algorithm for max-min allocation subject to k matroid constraints under identical valuations.
Cite as

Kimon Boehmer. Submodular Max-Min Allocation Under Identical Valuations. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{boehmer:LIPIcs.SWAT.2026.8,
  author =	{Boehmer, Kimon},
  title =	{{Submodular Max-Min Allocation Under Identical Valuations}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.8},
  URN =		{urn:nbn:de:0030-drops-260446},
  doi =		{10.4230/LIPIcs.SWAT.2026.8},
  annote =	{Keywords: Submodularity, Approximation algorithms, Allocation, Configuration LP}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.15
Incentivizing High-Quality Content in Online Recommender Systems

Authors: Xinyan Hu, Meena Jagadeesan, Michael I. Jordan, and Jacob Steinhardt

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
In content recommender systems such as TikTok and YouTube, the platform’s recommendation algorithm shapes content producer incentives. Many platforms employ online learning, which generates intertemporal incentives, since content produced today affects recommendations of future content. We study the game between producers and analyze the content created at equilibrium. We prove that standard online learning algorithms, such as Hedge and EXP3, unfortunately incentivize producers to create low-quality content, where producers' effort approaches zero in the long run for typical learning rate schedules. Motivated by this negative result, we design learning algorithms that incentivize producers to invest high effort and achieve high user welfare. At a conceptual level, our work illustrates the unintended impact that a platform’s learning algorithm can have on content quality and introduces algorithmic approaches to mitigating these effects.
Cite as

Xinyan Hu, Meena Jagadeesan, Michael I. Jordan, and Jacob Steinhardt. Incentivizing High-Quality Content in Online Recommender Systems. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.FORC.2026.15,
  author =	{Hu, Xinyan and Jagadeesan, Meena and Jordan, Michael I. and Steinhardt, Jacob},
  title =	{{Incentivizing High-Quality Content in Online Recommender Systems}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.15},
  URN =		{urn:nbn:de:0030-drops-259887},
  doi =		{10.4230/LIPIcs.FORC.2026.15},
  annote =	{Keywords: recommender systems, content quality, producer incentives, online learning, algorithmic game theory, Stackelberg games}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.10
Packing Compact Subgraphs with Applications to Districting

Authors: Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs [Prathamesh Dharangutte et al., 2025]. In particular, we improve the approximation factor from O(log n) to O(1) for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an O(1) approximation for packing radius-k districts (with a constant k) in planar and apex-minor-free graphs. In order to get a (1+ε) approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to 1), for bounded radius-k districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types.
Cite as

Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu. Packing Compact Subgraphs with Applications to Districting. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.FORC.2026.10,
  author =	{Chen, Ho-Lin and Chou, Po-Yu and Dharangutte, Prathamesh and Gao, Jie and Huang, Shang-En and Yu, Fang-Yi},
  title =	{{Packing Compact Subgraphs with Applications to Districting}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{10:1--10:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.10},
  URN =		{urn:nbn:de:0030-drops-259820},
  doi =		{10.4230/LIPIcs.FORC.2026.10},
  annote =	{Keywords: Approximation algorithms, algorithmic fairness}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.7
When to Ask a Question: Understanding Communication Strategies in Generative AI Tools

Authors: Charlotte Park, Kate Donahue, and Manish Raghavan

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Generative AI models differ from traditional machine learning tools in that they allow users to provide as much or as little information as they choose in their inputs. This flexibility often leads users to omit certain details, relying on the models to infer and fill in under-specified information based on distributional knowledge of user preferences. Such inferences may privilege majority viewpoints and disadvantage users with atypical preferences, raising concerns about fairness. Unlike more traditional recommender systems, LLMs can explicitly solicit more information from users through natural language. However, while directly eliciting user preferences could increase personalization and mitigate inequality, excessive querying places a burden on users who value efficiency. We develop a stylized model of user-LLM interaction and develop an objective that captures tradeoff between user burden and preference representation. Building on the observation that individual preferences are often correlated, we analyze how AI systems should balance inference and elicitation, characterizing the optimal amount of information to solicit before content generation. Ultimately, we show that information elicitation can mitigate the systematic biases of preference inference, enabling the design of generative tools that better incorporate diverse user perspectives while maintaining efficiency. We complement this theoretical analysis with an empirical evaluation illustrating the model’s predictions and exploring their practical implications.
Cite as

Charlotte Park, Kate Donahue, and Manish Raghavan. When to Ask a Question: Understanding Communication Strategies in Generative AI Tools. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{park_et_al:LIPIcs.FORC.2026.7,
  author =	{Park, Charlotte and Donahue, Kate and Raghavan, Manish},
  title =	{{When to Ask a Question: Understanding Communication Strategies in Generative AI Tools}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{7:1--7:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.7},
  URN =		{urn:nbn:de:0030-drops-259782},
  doi =		{10.4230/LIPIcs.FORC.2026.7},
  annote =	{Keywords: human-AI interaction, user modeling, personalization}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2026.7
The Importance of Parameters in Ranking Functions

Authors: Christoph Standke, Nikolaos Tziavelis, Wolfgang Gatterbauer, and Benny Kimelfeld

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
How important is the weight of a given column in determining the ranking of tuples in a table? To address such an explanation question about a ranking function, we investigate the computation of SHAP scores for column weights, adopting a recent framework by Grohe et al. [ICDT'24]. The exact definition of this score depends on three key components: (1) the ranking function in use, (2) an effect function that quantifies the impact of using alternative weights on the ranking, and (3) an underlying weight distribution. We analyze the computational complexity of different instantiations of this framework for a range of fundamental ranking and effect functions, focusing on probabilistically independent finite distributions for individual columns. For the ranking functions, we examine lexicographic orders and score-based orders defined by the summation, minimum, and maximum functions. For the effect functions, we consider global, top-k, and local perspectives: global measures quantify the divergence between the perturbed and original rankings, top-k measures inspect the change in the set of top-k answers, and local measures capture the impact on an individual tuple of interest. Although all cases admit an additive fully polynomial-time randomized approximation scheme (FPRAS), we establish the complexity of exact computation, identifying which cases are solvable in polynomial time and which are #P-hard. We further show that all complexity results, lower bounds and upper bounds, extend to a related task of computing the Shapley value of whole columns (regardless of their weight).
Cite as

Christoph Standke, Nikolaos Tziavelis, Wolfgang Gatterbauer, and Benny Kimelfeld. The Importance of Parameters in Ranking Functions. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{standke_et_al:LIPIcs.ICDT.2026.7,
  author =	{Standke, Christoph and Tziavelis, Nikolaos and Gatterbauer, Wolfgang and Kimelfeld, Benny},
  title =	{{The Importance of Parameters in Ranking Functions}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.7},
  URN =		{urn:nbn:de:0030-drops-256217},
  doi =		{10.4230/LIPIcs.ICDT.2026.7},
  annote =	{Keywords: Ranking, Explanation, Shapley value, SHAP scores}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2026.19
Dynamic Necklace Splitting

Authors: Rishi Advani, Abolfazl Asudeh, Mohsen Dehghankar, and Stavros Sintos

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
The necklace splitting problem is a classic problem in fair division with many applications, including data-informed fair hash maps. We extend necklace splitting to a dynamic setting, allowing for relocation, insertion, and deletion of beads. We present linear-time, optimal algorithms for the two-color case that support all dynamic updates. For more than two colors, we give linear-time, optimal algorithms for relocation subject to a restriction on the number of agents. Finally, we propose a randomized algorithm for the two-color case that handles all dynamic updates, guarantees approximate fairness with high probability, and runs in polylogarithmic time when the number of agents is small.
Cite as

Rishi Advani, Abolfazl Asudeh, Mohsen Dehghankar, and Stavros Sintos. Dynamic Necklace Splitting. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{advani_et_al:LIPIcs.ICDT.2026.19,
  author =	{Advani, Rishi and Asudeh, Abolfazl and Dehghankar, Mohsen and Sintos, Stavros},
  title =	{{Dynamic Necklace Splitting}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.19},
  URN =		{urn:nbn:de:0030-drops-256332},
  doi =		{10.4230/LIPIcs.ICDT.2026.19},
  annote =	{Keywords: Necklace splitting, dynamic algorithms, fair division}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.51
Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems

Authors: Shaddin Dughmi, Yusuf Hakan Kalayci, and Xinyu Liu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
When uncertainty meets costly information gathering, a fundamental question emerges: which data points should we probe to unlock near-optimal solutions? Sparsification of stochastic packing problems addresses this trade-off. The existing notions of sparsification measure the level of sparsity, called degree, as the ratio of queried items to the optimal solution size. While effective for matching and matroid-type problems with uniform structures, this cardinality-based approach fails for knapsack-type constraints where feasible sets exhibit dramatic structural variation. We introduce a polyhedral sparsification framework that measures the degree as the smallest scalar needed to embed the query set within a scaled feasibility polytope, naturally capturing redundancy without relying on cardinality. Our main contribution establishes that knapsack, multiple knapsack, and generalized assignment problems admit (1-ε)-approximate sparsifiers with degree polynomial in 1/p and 1/ε - where p denotes the independent activation probability of each element - remarkably independent of problem dimensions. The key insight involves grouping items with similar weights and deploying a charging argument: when our query set misses an optimal item, we either substitute it directly with a queried item from the same group or leverage that group’s excess contribution to compensate for the loss. This reveals an intriguing complexity-theoretic separation - while the multiple knapsack problem lacks an FPTAS and generalized assignment is APX-hard, their sparsification counterparts admit efficient (1-ε)-approximation algorithms that identify polynomial degree query sets. Finally, we raise an open question: can such sparsification extend to general integer linear programs with degree independent of problem dimensions?
Cite as

Shaddin Dughmi, Yusuf Hakan Kalayci, and Xinyu Liu. Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dughmi_et_al:LIPIcs.ITCS.2026.51,
  author =	{Dughmi, Shaddin and Kalayci, Yusuf Hakan and Liu, Xinyu},
  title =	{{Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{51:1--51:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.51},
  URN =		{urn:nbn:de:0030-drops-253386},
  doi =		{10.4230/LIPIcs.ITCS.2026.51},
  annote =	{Keywords: Packing Problems, Assignment Problems, Stochastic Selection, Sparsification}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.9
An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange

Authors: Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph G and integers d and k, the standard problem asks whether G contains a packing of vertex-disjoint cycles, each of length ≤ d, covering at least k vertices in total. In the multi-agent setting we consider, the vertex set is partitioned over several agents who reject a cycle packing as solution if it can be modified into an alternative packing that covers more of their own vertices. A cycle packing is called rejection-proof if no agent rejects it and the problem asks whether such a packing exists that covers at least k vertices. We exploit the sunflower lemma on a set packing formulation of the problem to give a kernel for this Σ₂^P-complete problem that is polynomial in k for all constant values of d. We also provide a 2^𝒪(k log k) + n^𝒪(1) algorithm based on it and show that this FPT algorithm is asymptotically optimal under the ETH. Further, we generalize the problem by including an additional positive integer c in the input that naturally captures how much agents can modify a given cycle packing to reject it. For every constant c, the resulting problem simplifies from being Σ₂^P-complete to NP-complete. The super-exponential lower bound already holds for c = 2, though. We present an ad-hoc single-exponential algorithm for c = 1. These results reveal an interesting discrepancy between the classical and parameterized complexity of the problem and give a good view of what makes it hard.
Cite as

Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh. An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2025.9,
  author =	{Jansen, Bart M. P. and Lamme, Jeroen S. K. and Verhaegh, Ruben F. A.},
  title =	{{An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.9},
  URN =		{urn:nbn:de:0030-drops-251414},
  doi =		{10.4230/LIPIcs.IPEC.2025.9},
  annote =	{Keywords: Parameterized complexity, Multi-agent kidney exchange, Kernelization, Set packing}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.15
Extending EFX Allocations to Further Multi-Graph Classes

Authors: Umang Bhaskar and Yeshwant Pandit

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
The existence of EFX allocations is one of the most significant open questions in fair division. Recent work by Christodoulou, Fiat, Koutsoupias, and Sgouritsa ("Fair allocation in graphs," EC 2023) establishes the existence of EFX allocations for graphical valuations, when agents are vertices in a graph, items are edges, and each item has zero value for all agents other than those at its endpoints. Thus, in this setting, each good has non-zero value for at most two agents, and there is at most one good valued by any pair of agents. This marks one of the few cases when an exact and complete EFX allocation is known to exist for more than three agents. In this work, we partially extend these results to multi-graphs, when each pair of vertices can have more than one edge between them. The existence of EFX allocations in multi-graphs is a natural open question given their existence in simple graphs. We show that EFX allocations exist, and can be computed in polynomial time, for agents with cancelable valuations in the following cases: (i) bipartite multi-graphs, (ii) multi-trees with monotone valuations, and (iii) multi-graphs with girth (2t-1), where t is the chromatic number of the multi-graph. The existence of EFX in cycle multi-graphs follows from (i), (iii), and the known existence of EFX for three agents.
Cite as

Umang Bhaskar and Yeshwant Pandit. Extending EFX Allocations to Further Multi-Graph Classes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.FSTTCS.2025.15,
  author =	{Bhaskar, Umang and Pandit, Yeshwant},
  title =	{{Extending EFX Allocations to Further Multi-Graph Classes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.15},
  URN =		{urn:nbn:de:0030-drops-250958},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.15},
  annote =	{Keywords: Fair Division, EFX, Multi-graphs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.29
Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division

Authors: Ajaykrishnan E S and Daniel Lokshtanov

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the problem of Envy-Free Incomplete Connected Fair Division, where exactly p vertices of an undirected graph must be allocated to agents such that each agent receives a connected share and does not envy another agent’s share. Focusing on agents with additive valuations, we show that the problem remains computationally hard when parameterized by p and the number of agents. This result holds even for star graphs and with the input numbers given in unary representation, thereby resolving an open problem posed by Gahlawat and Zehavi (FSTTCS 2023). In stark contrast, we show that if one is willing to tolerate even the slightest amount of envy, then the problem becomes efficient with respect to the natural parameters. Specifically, we design an Efficient Parameterized Approximation Scheme parameterized by p and the number of agent types. Our algorithm works on general graphs and remains efficient even when the input numbers are provided in binary representation.
Cite as

Ajaykrishnan E S and Daniel Lokshtanov. Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{es_et_al:LIPIcs.FSTTCS.2025.29,
  author =	{E S, Ajaykrishnan and Lokshtanov, Daniel},
  title =	{{Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.29},
  URN =		{urn:nbn:de:0030-drops-251101},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.29},
  annote =	{Keywords: Envy-Free Incomplete Connected Fair Division, Efficient Parameterized Approximation Scheme, W\lbrack1\rbrack-hardness}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.32
Fair Rent Division: New Budget and Rent Constraints

Authors: Rohith Reddy Gangam, Shayan Taherijam, and Vijay V. Vazirani

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the classical rent division problem, where n agents must allocate n indivisible rooms and split a fixed total rent R. The goal is to compute an envy-free (EF) allocation, where no agent prefers another agent’s room and rent to their own. This problem has been extensively studied under standard assumptions, where efficient algorithms for computing EF allocations are known. We extend this framework by introducing two practically motivated constraints: (i) lower and upper bounds on room rents, and (ii) room-specific budget for agents. We develop efficient combinatorial algorithms that either compute a feasible EF allocation or certify infeasibility. We further design algorithms to optimize over EF allocations using natural fairness objectives such as maximin utility, leximin utility, and minimum utility spread. Our approach unifies both constraint types within a single algorithmic framework, advancing the applicability of fair division methods in real-world platforms such as Spliddit.
Cite as

Rohith Reddy Gangam, Shayan Taherijam, and Vijay V. Vazirani. Fair Rent Division: New Budget and Rent Constraints. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gangam_et_al:LIPIcs.FSTTCS.2025.32,
  author =	{Gangam, Rohith Reddy and Taherijam, Shayan and Vazirani, Vijay V.},
  title =	{{Fair Rent Division: New Budget and Rent Constraints}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.32},
  URN =		{urn:nbn:de:0030-drops-251136},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.32},
  annote =	{Keywords: Rent Division, Envy‑Free, Fair Division}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.54
Reforming an Unfair Allocation by Exchanging Goods

Authors: Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Fairly allocating indivisible goods is a frequently occurring task in everyday life. Given an initial allocation of the goods, we consider the problem of reforming it via a sequence of exchanges to attain fairness in the form of envy-freeness up to one good (EF1). We present a vast array of results on the complexity of determining whether it is possible to reach an EF1 allocation from the initial allocation and, if so, the minimum number of exchanges required. In particular, we uncover several distinctions based on the number of agents involved and their utility functions. Furthermore, we derive essentially tight bounds on the worst-case number of exchanges needed to achieve EF1.
Cite as

Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong. Reforming an Unfair Allocation by Exchanging Goods. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 54:1-54:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{yuen_et_al:LIPIcs.ISAAC.2025.54,
  author =	{Yuen, Sheung Man and Igarashi, Ayumi and Kamiyama, Naoyuki and Suksompong, Warut},
  title =	{{Reforming an Unfair Allocation by Exchanging Goods}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{54:1--54:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.54},
  URN =		{urn:nbn:de:0030-drops-249626},
  doi =		{10.4230/LIPIcs.ISAAC.2025.54},
  annote =	{Keywords: fair division, indivisible goods, envy-freeness, exchanges}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.44
Approximation Schemes for k-Subset Sum Ratio and k-Way Number Partitioning Ratio

Authors: Sotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos, Nikos Leonardos, Aris Pagourtzis, Christos Pergaminelis, Stavros Petsalakis, and Kanellos Tsitouras

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Subset Sum Ratio problem (SSR) asks, given a multiset A of positive integers, to find two disjoint subsets of A such that the largest-to-smallest ratio of their sums is minimized. In this paper we study the k-version of SSR, namely k-Subset Sum Ratio (k-SSR), which asks to minimize the largest-to-smallest ratio of sums of k disjoint subsets of A. We develop an approximation scheme for k-SSR running in O(n^{2k}/ε^{k-1}) time, where n = |A| and ε is the error parameter. To the best of our knowledge, this is the first FPTAS for k-SSR for fixed k > 2. We also study the k-way Number Partitioning Ratio (k-PART) problem, which differs from k-SSR in that the k subsets must constitute a partition of A; this problem in fact corresponds to the objective of minimizing the largest-to-smallest sum ratio in the family of Multiway Number Partitioning problems. We present a more involved FPTAS for k-PART, also achieving O(n^{2k}/ε^{k-1}) time complexity. Notably, k-PART is also equivalent to the Minimum Envy-Ratio problem with identical valuation functions, which has been studied in the context of fair division of indivisible goods. Thus, for the case of identical valuations, our FPTAS represents a significant improvement over the O(n^{4k²+1}/ε^{2k²}) bound obtained by Nguyen and Rothe’s FPTAS [Trung Thanh Nguyen and Jörg Rothe, 2014] for Minimum Envy-Ratio with general additive valuations. Lastly, we propose a second FPTAS for k-SSR, which employs carefully designed calls to the first one; the new scheme has a time complexity of Õ(n/ε^{3k-1}), thus being much faster when n≫ 1/ ε.
Cite as

Sotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos, Nikos Leonardos, Aris Pagourtzis, Christos Pergaminelis, Stavros Petsalakis, and Kanellos Tsitouras. Approximation Schemes for k-Subset Sum Ratio and k-Way Number Partitioning Ratio. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 44:1-44:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kanellopoulos_et_al:LIPIcs.ISAAC.2025.44,
  author =	{Kanellopoulos, Sotiris and Mitropoulos, Giorgos and Antonopoulos, Antonis and Leonardos, Nikos and Pagourtzis, Aris and Pergaminelis, Christos and Petsalakis, Stavros and Tsitouras, Kanellos},
  title =	{{Approximation Schemes for k-Subset Sum Ratio and k-Way Number Partitioning Ratio}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{44:1--44:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.44},
  URN =		{urn:nbn:de:0030-drops-249521},
  doi =		{10.4230/LIPIcs.ISAAC.2025.44},
  annote =	{Keywords: Fully polynomial-time approximation schemes, Subset Sum Ratio, Number Partitioning, Fair division, Envy minimization, Pseudo-polynomial time algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.13
Optimal Online Bipartite Matching in Degree-2 Graphs

Authors: Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Online bipartite matching is a classical problem in online algorithms and we know that both the deterministic fractional and randomized integral online matchings achieve the same competitive ratio of 1-1/e. In this work, we study classes of graphs where the online degree is restricted to 2. As expected, one can achieve a competitive ratio of better than 1-1/e in both the deterministic fractional and randomized integral cases, but surprisingly, these ratios are not the same. It was already known that for fractional matching, a 0.75 competitive ratio algorithm is optimal. We show that the folklore Half-Half algorithm achieves a competitive ratio of η ≈ 0.717772… and more surprisingly, show that this is optimal by giving a matching lower-bound. This yields a separation between the two problems: deterministic fractional and randomized integral, showing that it is impossible to obtain a perfect rounding scheme.
Cite as

Amey Bhangale, Arghya Chakraborty, and Prahladh Harsha. Optimal Online Bipartite Matching in Degree-2 Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ISAAC.2025.13,
  author =	{Bhangale, Amey and Chakraborty, Arghya and Harsha, Prahladh},
  title =	{{Optimal Online Bipartite Matching in Degree-2 Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.13},
  URN =		{urn:nbn:de:0030-drops-249216},
  doi =		{10.4230/LIPIcs.ISAAC.2025.13},
  annote =	{Keywords: Online Algorithm, Bipartite matching}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.21
Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing

Authors: Aggelos Kiayias, Elias Koutsoupias, Evangelos Markakis, and Panagiotis Tsamopoulos

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
We study a game-theoretic model for pool formation in Proof of Stake blockchain protocols. In such systems, stakeholders can form pools as a means of obtaining regular rewards from participation in ledger maintenance, with the power of each pool being dependent on its collective stake. The question we are interested in is the design of mechanisms, i.e., "reward sharing schemes," that suitably split rewards among pool members and achieve favorable properties in the resulting pool configuration. With this in mind, we initiate a non-cooperative game-theoretic analysis of the well known Shapley value scheme from cooperative game theory into the context of blockchains. In particular, we focus on the oceanic model of games, proposed by Milnor and Shapley (1978), which is suitable for populations where a small set of large players coexists with a big mass of rather small, negligible players. This provides an appropriate level of abstraction for pool formation processes that occur among the stakeholders of a blockchain. We provide comparisons between the Shapley mechanism and the more standard proportional scheme, in terms of attained decentralization, via a Price of Stability analysis and in terms of susceptibility to Sybil attacks, i.e., the strategic splitting of a players' stake with the intention of participating in multiple pools for increased profit. Interestingly, while the widely deployed proportional scheme appears to have certain advantages, the Shapley value scheme, which rewards higher the most pivotal players, emerges as a competitive alternative, by being able to bypass some of the downsides of proportional sharing in terms of Sybil attack susceptibility, while also not being far from optimal guarantees w.r.t. decentralization. Finally, we also complement our study with some variations of proportional sharing, where the profit is split in proportion to a superadditive or a subadditive function of the stake, showing that our results for the Shapley value scheme are maintained in comparison to these functions as well.
Cite as

Aggelos Kiayias, Elias Koutsoupias, Evangelos Markakis, and Panagiotis Tsamopoulos. Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kiayias_et_al:LIPIcs.AFT.2025.21,
  author =	{Kiayias, Aggelos and Koutsoupias, Elias and Markakis, Evangelos and Tsamopoulos, Panagiotis},
  title =	{{Pool Formation in Oceanic Games: Shapley Value and Proportional Sharing}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.21},
  URN =		{urn:nbn:de:0030-drops-247409},
  doi =		{10.4230/LIPIcs.AFT.2025.21},
  annote =	{Keywords: Shapley value, Nash equilibria, Price of Stability, Reward sharing schemes, Proof of Stake blockchains}
}
  • Refine by Type
  • 27 Document/PDF
  • 23 Document/HTML

  • Refine by Publication Year
  • 7 2026
  • 16 2025
  • 1 2020
  • 1 2016
  • 1 2010
  • Show More...

  • Refine by Author
  • 4 Procaccia, Ariel D.
  • 2 Derakhshan, Mahsa
  • 2 Dharangutte, Prathamesh
  • 2 Gao, Jie
  • 2 Huang, Shang-En
  • Show More...

  • Refine by Series/Journal
  • 24 LIPIcs
  • 1 DagRep
  • 2 DagSemProc

  • Refine by Classification
  • 5 Theory of computation → Algorithmic game theory
  • 4 Theory of computation → Approximation algorithms analysis
  • 3 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Algorithmic game theory and mechanism design
  • 2 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 3 Approximation algorithms
  • 3 Fair Division
  • 3 fair division
  • 2 Shapley value
  • 2 Sublinear algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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