.png){kind=icon}
.png){kind=icon}
Return
Matroid and Knapsack House Allocation
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ic.2026.105459.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We explore two extensions of house allocation (HA) by enabling the allocation of each object (with limited or unlimited copies) to multiple agents. One extension is associated with matroid constraints, called the Matroid House Allocation Problem (MHA), while the other is associated with knapsack constraints, and is called the Knapsack House Allocation Problem (KHA). We investigate the highly general setting for both problems, where agents possess weights or priorities and can express indifference towards objects. Our focus is on designing (universally) truthful and Pareto optimal mechanisms to compute a maximum weighted matching. We propose a tight 2-approximate deterministic mechanism that is both truthful and Pareto optimal for the Matroid House Allocation Problem (MHA). Additionally, we develop a randomized mechanism that is universally truthful and Pareto optimal, with an approximation ratio of e-1 for the same problem. This ratio of e e e-1 is the best achievable among universally truthful and Pareto optimal mechanisms, assuming the mechanism is also non-bossy. These results represent significant advancements over previous findings and are achieved through different techniques. Furthermore, we apply our MHA mechanisms to the Online Bipartite Matching Problem and Job Recruitment Problems by incorporating matroid constraints, resulting in optimal algorithms for both problems. For the Knapsack House Allocation Problem (KHA), we design a (4, 2)-approximate mechanism that is universally truthful and Pareto optimal for cases with equal capacities. Additionally, we provide a universally truthful mechanism with a constant approximation for KHA. Moreover, we develop a 4-approximate mechanism for equal capacity KHA with strict preferences.
Keywords:
Algorithmic mechanism design
Approximation algorithms
Matching under preferences
Indifference or tie
Matroid and knapsack constraints
Journal
I
IF:
1
Papers:
79
Citations:
2.8K