On the Allocation of Multiple Divisible Assets to Players with Different Utilities

Ephraim Zehavi, Amir LeshemComputational 2017 · DOI

TL;DR

This paper extends existing bargaining solutions (Raiffa and Talmud rules) to a multi-asset scenario where players have differing utilities for each asset and these utilities are non-transferable. The authors propose a novel game model and algorithms that allow for the fair division of multiple divisible assets, addressing a gap in previous models that assumed transferable utilities or single-asset scenarios.

What Problem Does This Paper Address?

The core problem this paper tackles is how to fairly divide multiple divisible assets among several players, each having unique preferences (utilities) for each asset, and crucially, where these utilities cannot be traded or transferred between players. Traditional bargaining and bankruptcy solutions often assume either transferable utilities (meaning a dollar is worth the same to everyone) or focus on single-asset divisions. This paper addresses the more complex and realistic scenario of multiple assets with non-transferable, heterogeneous utilities, extending established solutions like the Raiffa bargaining solution and the Talmud rule to this multi-asset, non-transferable utility context.

Methods

The authors introduce a multi-asset game model where each player has a vector of claims for each asset and a utility function for each asset. The key innovation lies in extending the Raiffa Bargaining Solution (RBS) and the Talmud Rule (TR) to this multi-asset, non-transferable utility setting.

For the Raiffa Bargaining Solution, the paper proposes a step-by-step iterative process. Each step involves finding "ideal points" for each player (maximizing their utility given others' disagreement points) using a Restricted Ideal Point (RIP) rule, which is solved via linear programming. Then, a Midpoint (MP) rule is applied to determine the new disagreement point for the next step. This process continues until the solution is arbitrarily close to the Pareto frontier.

For the Talmud Rule, the paper adapts its bankruptcy solution origins to the multi-asset bargaining context. It utilizes a "water-filling" interpretation, where assets are metaphorically poured into containers representing players' claims. The allocation is determined by either a Constrained Equal-Awards (CEA) rule or a Constrained Equal-Losses (CEL) rule, depending on the water level relative to players' claims and disagreement points. This involves solving a series of linear programming problems and binary searches to find the optimal allocation.

Datasets

Not discussed in the paper. The paper uses hypothetical scenarios and examples to illustrate its proposed methods.

Key Insights and Ideas

  • Non-transferable utilities are crucial: The paper highlights that assuming utilities are transferable oversimplifies real-world bargaining scenarios where players have distinct preferences that cannot be easily exchanged.
  • Iterative refinement for fairness: Both the extended Raiffa and Talmud solutions rely on iterative processes to converge towards a Pareto optimal and fair allocation, gradually reducing the "unallocated utility" or surplus.
  • Linear programming as a core tool: The paper demonstrates the power of linear programming in solving complex bargaining problems, particularly for finding ideal points and determining optimal asset allocations.
  • Generalization of existing rules: The work successfully extends established bargaining and bankruptcy rules to a more complex, multi-asset, non-transferable utility environment, bridging a gap in the literature.
  • Water-filling analogy for Talmud rule: The use of the water-filling analogy provides an intuitive way to understand how the Talmud rule distributes assets based on claims and potential losses.

Key Results

The paper presents algorithms for extending the Raiffa and Talmud bargaining solutions to multi-asset games with non-transferable utilities. The proposed methods are shown to converge to e-Pareto optimal solutions. The paper provides detailed examples and tables (Table IV and V) illustrating the application of these algorithms to scenarios with three players and seven assets, showing how the allocations differ between the Raiffa and Talmud rule solutions based on player utilities. The complexity analysis suggests that the RBS has a complexity of O(JK^6N^6) and the TR solution is O(K^6N^5), where J is the number of iterations, K is the number of assets, and N is the number of players. For the two-player case, a simplified O(K log K) algorithm is presented.

Limitations and Future Work

  • Computational Complexity: While the algorithms are presented, the worst-case complexity for the multi-player, multi-asset case can be high. The paper notes that in practice, algorithms converge faster than the worst-case bound.
  • Assumptions: The model assumes utilities are additively separable across assets and that players' utility functions are convex.
  • Future Work: The paper suggests that global bargaining solutions can be obtained by solving a sequence of linear programming problems. Further exploration of the properties of these solutions and their application to more complex scenarios could be future directions. The paper also mentions that the Talmud rule can be extended to the TAL-family rules for multi-asset bargaining problems.

Summary updated

BibTeX
@inproceedings{zehavi2017allocation,
  author = {Ephraim Zehavi and Amir Leshem},
  title = {{On the Allocation of Multiple Divisible Assets to Players with Different Utilities}},
  booktitle = {Computational},
  year = {2017},
  doi = {10.1007/s10614-017-9673-9},
}
Figure