OpenAlex ·
Almost Envy-Freeness for Additive Mixed Manna with Entitlements: Deterministic and Randomized Guarantees
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.02724
- Original
- Read it at the publisher
- Topics
Abstract
We investigate the fair allocation of indivisible items among agents with asymmetric entitlements in mixed manna settings, where the items consist of both goods and chores. For additive valuations, we establish that weighted envy-free up to one item (WEF1) allocations always exist and can be computed in polynomial time. We also study fair and efficient allocation and show that weighted envy-freeness up to one transfer (WEF1T) is compatible with fractional Pareto optimality (fPO) for every mixed-manna instance. This relaxation from WEF1 to WEF1T is tight, as demonstrated by our impossibility result. We further show a best-of-both-worlds result via a finite lottery that guarantees weighted envy-freeness (WEF) in expectation, with every realized allocation satisfying WEF1T and achieving the tight characterization complemented by the existing impossibility result.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
Approximately Efficient Multidimensional Bilateral Trade
Unified Pitch Graphs for Diagnosing Pitching Strategy
The Complexity of Justified Representation with Additive Utilities
Auditing Contextual Bias in Human Ball-Strike Calls Using KBO's Automated Umpiring Transition
Otter: A Provably MEV-Resilient Automated Market Maker via Surplus Redistribution
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.