Cover Image

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Andersen, Martin Jupakkal, Caragiannis, Ioannis, Ipsen, Anders Bo, Søltoft, Alexander
Format:	Preprint
Published:	2025
Subjects:	Computer Science and Game Theory Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods
by: Kawase, Yasushi, et al.
Published: (2023)

Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings
by: V., Vishwa Prakash H., et al.
Published: (2023)

Approximately Envy-free and Equitable Allocations of Indivisible Items for Non-monotone Valuations
by: Bilò, Vittorio, et al.
Published: (2025)

Position Fair Mechanisms Allocating Indivisible Goods
by: Mahara, Ryoga, et al.
Published: (2024)

Beyond the worst case: Distortion in impartial culture electorates
by: Caragiannis, Ioannis, et al.
Published: (2023)

On Interim Envy-Free Allocation Lotteries
by: Caragiannis, Ioannis, et al.
Published: (2021)

The Distortion of Prior-Independent b-Matching Mechanisms
by: Caragiannis, Ioannis, et al.
Published: (2026)

Minimum Envy Graphical House Allocation Beyond Identical Valuations
by: Inamdar, Tanmay, et al.
Published: (2026)

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
by: Feng, Yuda, et al.
Published: (2024)

The Complexity of Extending Fair Allocations of Indivisible Goods
by: Deligkas, Argyrios, et al.
Published: (2025)

Welfare Approximation in Additively Separable Hedonic Games
by: Bullinger, Martin, et al.
Published: (2025)

Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
by: Feng, Yuda, et al.
Published: (2024)

Revisiting Fair and Efficient Allocations for Bivalued Goods
by: Liu, Hui, et al.
Published: (2026)

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
by: Bei, Xiaohui, et al.
Published: (2025)

An FPTAS for 7/9-Approximation to Maximin Share Allocations
by: Huang, Xin, et al.
Published: (2025)

The Secretary Problem with Predicted Additive Gap
by: Braun, Alexander, et al.
Published: (2024)

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
by: Borst, Sander, et al.
Published: (2026)

Posted Price Mechanisms for Online Allocation with Diseconomies of Scale
by: Jazi, Hossein Nekouyan, et al.
Published: (2025)

Non-Monotonicity in Fair Division of Graphs
by: Hosseini, Hadi, et al.
Published: (2025)

Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
by: Eden, Alon, et al.
Published: (2024)

Online Allocation with Multi-Class Arrivals: Group Fairness vs Individual Welfare
by: Zargari, Faraz, et al.
Published: (2025)

Additively Competitive Secretaries
by: Mahdian, Mohammad, et al.
Published: (2026)

Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
by: Bullinger, Martin, et al.
Published: (2025)

The Landscape of Almost Equitable Allocations
by: Hosseini, Hadi, et al.
Published: (2025)

Online Resource Allocation with Cancellations
by: Ekbatani, Farbod, et al.
Published: (2022)

The Average-Value Allocation Problem
by: Bhawalkar, Kshipra, et al.
Published: (2024)

Conflict and Fairness in Resource Allocation
by: Bandopadhyay, Susobhan, et al.
Published: (2024)

Lipschitz Continuous Allocations for Optimization Games
by: Kumabe, Soh, et al.
Published: (2024)

Online Combinatorial Allocation with Interdependent Values
by: Feldman, Michal, et al.
Published: (2025)

Robust Optimality of Bundling Goods Beyond Finite Variance
by: van Eck, Tim S. G., et al.
Published: (2025)

Online Proportional Apportionment
by: Cembrano, Javier, et al.
Published: (2025)

Pairwise Exchanges of Freely Replicable Goods with Negative Externalities
by: Yang, Shangyuan, et al.
Published: (2026)

Best of Both Worlds Guarantees for Equitable Allocations
by: Bhaskar, Umang, et al.
Published: (2025)

Budget-feasible Egalitarian Allocation of Conflicting Jobs
by: Gupta, Sushmita, et al.
Published: (2024)

Improved Parallel Algorithms for EF1 Allocations
by: Gowda, Kishen N, et al.
Published: (2026)

Cycle Cancellation for Submodular Fractional Allocations and Applications
by: Chekuri, Chandra, et al.
Published: (2025)

Public Goods Games in Directed Networks with Constraints on Sharing
by: Deligkas, Argyrios, et al.
Published: (2025)

A Reduction from Chores Allocation to Job Scheduling
by: Huang, Xin, et al.
Published: (2023)

EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
by: Afshinmehr, Mahyar, et al.
Published: (2024)

The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization
by: Huang, Zhiyi, et al.
Published: (2025)