On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences

DOI10.1007/978-3-642-04428-1_9MaRDI QIDQ3645308zbMATH OpenOpenAlexFDO

Authors Bart de Keijzer, Sylvain Bouveret, Tomas B. Klos, Yingqian Zhang

Publication date 17 November 2009

Published in Algorithmic Decision Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04428-1_9

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
• Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
• The price to pay for forgoing normalization in fair division of indivisible goods
• On the existence of Pareto efficient and envy-free allocations
• Envy-free and Pareto efficient allocations in economies with indivisible goods and money

Cited in

(35)

• On the existence of Pareto efficient and envy-free allocations
• On the complexity of fair house allocation
• Envy-free allocations respecting social networks
• The price to pay for forgoing normalization in fair division of indivisible goods
• Multiagent resource allocation in k-additive domains: preference representation and complexity
• Efficient reallocation under additive and responsive preferences
• Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity
• Existence of efficient envy-free allocations of a heterogeneous divisible commodity with nonadditive utilities
• A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
• When dividing mixed manna is easier than dividing goods: competitive equilibria with a constant number of chores
• Computing fair and efficient allocations with few utility values
• Fair and efficient allocation with few agent types, few item types, or small value levels
• Generalized binary utility functions and fair allocations
• Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
• Distributed fair allocation of indivisible goods
• scientific article; zbMATH DE number 4160481 (Why is no real title available?)
• Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
• Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods
• Competitive equilibrium with indivisible goods and generic budgets
• Efficient Fair Division with Minimal Sharing
• Communication complexity of discrete fair division
• Fair in the Eyes of Others
• Computing welfare-maximizing fair allocations of indivisible goods
• Computational complexity of necessary envy-freeness
• Allocation of indivisible items with individual preference graphs
• Computing fair and efficient allocations with few utility values
• On best-of-both-worlds fair-share allocations
• Diverse fair allocations: complexity and algorithms
• Group Envy Freeness and Group Pareto Efficiency in Fair Division with Indivisible Items
• Diverse fair allocations: complexity and algorithms
• Communication complexity of discrete fair division
• Efficiency in multiple-type housing markets
• Finding fair and efficient allocations of indivisible chores
• Fair division with subjective divisibility
• Fair assignment of indivisible objects under ordinal preferences

This page was built for publication: On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3645308)