The frontier of intractability for EFX with two agents

DOI10.1007/978-3-031-43254-5_17MaRDI QIDQ6546301zbMATH OpenFDO

Authors Paul W. Goldberg, Kasper Høgh, Alexandros Hollender

Publication date 29 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-43254-5_17

Mathematics Subject Classification ID

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

Recommendations

• Existence of EFX for two additive valuations
• Almost envy-freeness with general valuations
• Almost envy-freeness with general valuations
• Computing fair and efficient allocations with few utility values
• Computing fair and efficient allocations with few utility values

Cites work

• A discrete and bounded envy-free cake cutting protocol for four agents
• A Little Charity Guarantees Almost Envy-Freeness
• Almost envy-freeness with general valuations
• Closing gaps in asymptotic fair division
• Combinatorial auctions with decreasing marginal utilities
• Dividing a cake fairly
• Fair division of indivisible goods: recent progress and open questions
• Gross substitutability: an algorithmic survey
• How easy is local search?
• How to Cut a Cake Fairly
• scientific article; zbMATH DE number 3136641 (Why is no real title available?)
• Matroids and the greedy algorithm
• Maximum Nash welfare and other stories about EFX
• Near fairness in matroids
• Note on Independence Functions
• On total functions, existence theorems and computational complexity
• Optimal assignments in an ordered set: An application of matroid theory
• Rental Harmony: Sperner's Lemma in Fair Division
• Sur la division pragmatique
• Walrasian equilibrium with gross substitutes

Cited in

(2)

• Note on constrained long choice with multiple beginning elements
• On the complexity of some restricted variants of \textsc{Quotient Pigeon} and a weak variant of \textsc{Kőnig}

This page was built for publication: The frontier of intractability for EFX with two agents

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