Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913182755323904 |
|---|---|
| author | V., Vishwa Prakash H. Nimbhorkar, Prajakta |
| author_facet | V., Vishwa Prakash H. Nimbhorkar, Prajakta |
| contents | We study the fair allocation of indivisible goods and chores under ordinal valuations for agents with unequal entitlements. We show the existence and polynomial time computation of weighted necessarily proportional up to one item (WSD-PROP1) allocations for both goods and chores, by reducing it to a problem of finding perfect matchings in a bipartite graph. We give a complete characterization of these allocations as corner points of a perfect matching polytope. Using this polytope, we can optimize over all allocations to find a min-cost WSD-PROP1 allocation of goods or most efficient WSD-PROP1 allocation of chores. Additionally, we show the existence and computation of sequencible (SEQ) WSD-PROP1 allocations by using rank-maximal perfect matching algorithms and show incompatibility of Pareto optimality under all valuations and WSD-PROP1.
We also consider the Best-of-Both-Worlds (BoBW) fairness notion. By using our characterization, we show the existence and polynomial time computation of Ex-ante envy free (WSD-EF) and Ex-post WSD-PROP1 allocations under ordinal valuations for both chores and goods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15479 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings V., Vishwa Prakash H. Nimbhorkar, Prajakta Computer Science and Game Theory Data Structures and Algorithms We study the fair allocation of indivisible goods and chores under ordinal valuations for agents with unequal entitlements. We show the existence and polynomial time computation of weighted necessarily proportional up to one item (WSD-PROP1) allocations for both goods and chores, by reducing it to a problem of finding perfect matchings in a bipartite graph. We give a complete characterization of these allocations as corner points of a perfect matching polytope. Using this polytope, we can optimize over all allocations to find a min-cost WSD-PROP1 allocation of goods or most efficient WSD-PROP1 allocation of chores. Additionally, we show the existence and computation of sequencible (SEQ) WSD-PROP1 allocations by using rank-maximal perfect matching algorithms and show incompatibility of Pareto optimality under all valuations and WSD-PROP1. We also consider the Best-of-Both-Worlds (BoBW) fairness notion. By using our characterization, we show the existence and polynomial time computation of Ex-ante envy free (WSD-EF) and Ex-post WSD-PROP1 allocations under ordinal valuations for both chores and goods. |
| title | Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.15479 |