Scholarlink

<p>We study the problem of allocating indivisible objects to a set of rational players where each player’s final utility depends on the intrinsic valuation of the allocated item as well as the allocation within the player’s local neighbourhood. We specify players’ local neighbourhood in terms of a weighted graph. This extends the model of one-sided markets to incorporate neighbourhood externalities. We consider the solution concept of stability and show that, unlike in the case of one-sided markets, stable allocations may not always exist. When the underlying local neighbourhood graph is symmetric, a 2-stable allocation is guaranteed to exist and any decentralised mechanism where pairs of rational players agree to exchange objects terminates in such an allocation. We show that computing a 2-stable allocation is PLS-complete and further identify tractable subclasses. In the case of asymmetric neighbourhood structures, we show that it is NP-complete to check if a <i>k</i>-stable allocation exists for every fixed <i>k</i>. We then identify structural restrictions where stable allocations always exist and can be computed efficiently. Finally, we study the notion of envy-freeness in this framework.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

One-Sided Markets with Externalities

  • 期刊论文

  • 发表日期：

    2025年1月14日

查看全文
  • Sagar Massand,
  • Sunil Simon

摘要

We study the problem of allocating indivisible objects to a set of rational players where each player’s final utility depends on the intrinsic valuation of the allocated item as well as the allocation within the player’s local neighbourhood. We specify players’ local neighbourhood in terms of a weighted graph. This extends the model of one-sided markets to incorporate neighbourhood externalities. We consider the solution concept of stability and show that, unlike in the case of one-sided markets, stable allocations may not always exist. When the underlying local neighbourhood graph is symmetric, a 2-stable allocation is guaranteed to exist and any decentralised mechanism where pairs of rational players agree to exchange objects terminates in such an allocation. We show that computing a 2-stable allocation is PLS-complete and further identify tractable subclasses. In the case of asymmetric neighbourhood structures, we show that it is NP-complete to check if a k-stable allocation exists for every fixed k. We then identify structural restrictions where stable allocations always exist and can be computed efficiently. Finally, we study the notion of envy-freeness in this framework.