Fair and efficient allocation with few agent types, few item types, or small value levels

DOI10.1016/j.artint.2022.103820OpenAlexW4308382757MaRDI QIDQ2680786

Trung Thanh Nguyen, Jörg Rothe

Publication date: 4 January 2023

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2022.103820

zbMATH Keywords

Pareto efficiencyproportionalitymax-min fairnessbi-criteria optimizationmaximin sharefair division of indivisible goods

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed fair allocation of indivisible goods
• Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods
• The efficiency of fair division
• On integer points in polyhedra
• The polynomial-time hierarchy
• Approximation schemes for scheduling on parallel machines
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• The price to pay for forgoing normalization in fair division of indivisible goods
• Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
• A unified framework for designing EPTAS for load balancing on parallel machines
• Optimal bounds on the price of fairness for indivisible goods
• The Santa Claus problem
• The Price of Fairness
• Integer Programming with a Fixed Number of Variables
• Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods
• About the Structure of the Integer Cone and Its Application to Bin Packing
• On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
• Minkowski's Convex Body Theorem and Integer Programming
• The Knapsack Sharing Problem
• A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort
• Fair Enough
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• Faster Algorithms for Integer Programs with Block Structure
• Almost Envy-Freeness with General Valuations
• Fair Allocation of Indivisible Goods
• On Allocating Goods to Maximize Fairness
• MaxMin allocation via degree lower-bounded arborescences
• Polynomiality for Bin Packing with a Constant Number of Item Types
• An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods
• Parameterized Algorithms
• Fairly allocating contiguous blocks of indivisible items
• Algorithms - ESA 2003
• An EPTAS for scheduling on unrelated machines of few different types
• Fairness in routing and load balancing
• Combining fairness with throughput: Online routing with multiple objectives
• Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
• Computing welfare-maximizing fair allocations of indivisible goods