Approximately fair and population consistent budget division via simple payment schemes

• 成果类型: Article
• 署名作者: Aziz, Haris; Lederer, Patrick; Lu, Xinhang; Suzuki, Mashbat; Vollen, Jeremy
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2025.09.001
• 发表日期: 2025
• 关键词: social choice theory; Budget division; fairness

摘要

In approval-based budget division, a budget needs to be distributed to some candidates based on the voters' approval ballots over these candidates. In the pursuit of a simple, consistent, and approximately fair rule for this setting, we introduce the maximum payment rule (MP). Under this rule, each voter controls a part of the budget and, in each step, the corresponding voters allocate their entire budget to the candidate approved by the largest number of voters with nonzero budget. We show that MP meets our criteria as it satisfies monotonicity and a demanding population consistency condition and gives a 2-approximation to a fairness notion called average fair share (AFS). Moreover, we generalize MP to the class of sequential payment rules and prove that it is the most desirable rule within this class: nearly all other sequential payment rules fail monotonicity while offering only small improvements in the approximation ratio to AFS.