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

機関リポジトリ (HANDLE) オープンアクセス

説明

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

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1050587041605629824
  • ISSN
    23318422
  • HANDLE
    2324/7385217
  • 本文言語コード
    en
  • 資料種別
    journal article
  • データソース種別
    • IRDB

問題の指摘

ページトップへ