Whoever Said Money Won't Solve All Your Problems?: Weighted Envy-free Allocation with Subsidy

IR (HANDLE) Open Access

Bibliographic Information

Published
2025-02
Resource Type
journal article
Rights Information
  • Creative Commons Attribution 4.0 International
Publisher
Cornell University

Description

We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where each agent deems their allocated portion relative to their entitlement at least as favorable as any other’s relative to their own. Often, achieving WEF necessi- tates monetary transfers, which can be modeled as third-party subsidies. The goal is to attain WEF with bounded subsidies. / Previous work relied on characterizations of unweighted envy-freeness (EF), that fail in the weighted setting. This makes our new setting challenging. We present polynomial-time algorithms that compute WEF allocations with a guaranteed upper bound on total subsidy for monotone valuations and various subclasses thereof. / We also present an efficient algorithm to compute a fair allocation of items and money, when the budget is not enough to make the allocation WEF. This algorithm is new even for the unweighted setting

Journal

Keywords

Details 詳細情報について

  • CRID
    1050587041605629824
  • ISSN
    23318422
  • HANDLE
    2324/7385217
  • Text Lang
    en
  • Article Type
    journal article
  • Data Source
    • IRDB

Report a problem

Back to top