TL;DR
This paper introduces two novel cost allocation methods based on ordered player contributions, offering efficient and symmetric solutions applicable to diverse scenarios like risk management and environmental taxation. Crucially, these methods work even with less-behaved risk measures like Value-at-Risk, providing incentives for cost reduction.
What Problem Does This Paper Address?
Allocating costs or risks among multiple contributing entities is a common challenge in finance, environmental policy, and beyond. Traditional methods often rely on specific properties of the cost or risk measure (like coherency or convexity), limiting their applicability. For instance, in financial risk management, widely used measures like Value-at-Risk (VaR) lack these desirable properties, making it difficult to fairly distribute the aggregate risk among individual assets or portfolios. Similarly, designing effective environmental taxes that incentivize emission reduction requires robust allocation mechanisms. This paper aims to bridge this gap by proposing general cost allocation methods that are efficient, symmetric, and adaptable to various cost structures and risk measures, including those without strong theoretical guarantees.
Methods
The authors propose two general cost allocation methods, both rooted in the concept of an "ordered partition" of players. An ordered partition groups players based on a predefined order, creating sequential "level sets."
- Ordered Contribution Allocation (Definition 2.1): This method allocates the cost of each level set to its members. Specifically, for a player i in level set σ<sub>l</sub>, their share is calculated as the cost of the union of all preceding level sets up to σ<sub>l</sub> minus the cost of the union of all preceding level sets up to σ<sub>l-1</sub>, divided by the number of players in σ<sub>l</sub>. This method is computationally efficient if the cost function can be evaluated for subsets.
- Average Ordered Contribution Allocation (Definition 2.4): This method is a refinement that always satisfies the "dummy player property" (meaning a player who contributes nothing to a coalition receives nothing). It calculates each player's allocation by averaging their contribution across all possible permutations of players that respect the ordered partition. This method can be computationally more intensive, especially for larger numbers of players.
The paper also defines and explores various ways to generate these ordered partitions, such as "minimal increments ordering," "last contribution ordering," and "individual cost ordering," each with different properties and computational implications.
Datasets
Not discussed in the paper. The paper focuses on theoretical frameworks and general applications rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Generality Beyond Coherency: The most significant insight is the development of cost allocation methods that do not require risk measures to be coherent, convex, or differentiable. This opens up applications for widely used but theoretically weaker measures like Value-at-Risk.
- Incentive Compatibility: The proposed methods, particularly when applied to risk allocation, naturally incentivize players to reduce their contributions to the overall cost or risk, as their individual allocation is directly tied to their role in the ordered contribution.
- Flexibility in Ordering: The paper demonstrates that the choice of how players are ordered within the partition significantly impacts the allocation and its properties, offering flexibility to tailor the method to specific problem contexts.
- Trade-off Between Properties and Complexity: A clear trade-off is established: the first method is computationally simpler but may not always satisfy the dummy player property, while the second method guarantees the dummy player property but can be more complex to compute.
Key Results
- Both proposed allocation methods (2.1 and 2.2) are proven to be efficient (the sum of individual allocations equals the total cost).
- The allocations are symmetric if the underlying ordered partition is symmetric with respect to the cost function.
- The average ordered contribution allocation (2.2) always satisfies the dummy player property.
- The ordered contribution allocation (2.1) satisfies a weaker version of the dummy player property under certain conditions (e.g., if the risk measure has the translation property and p(0)=0).
- The paper provides concrete examples of how these methods can be applied to risk allocation for financial positions and nonlinear tax schemes for pollution emissions, demonstrating their practical relevance.
- For the minimal increments ordering, the dummy player property is satisfied if each level set in the partition contains at most two players.
Limitations and Future Work
- Computational Complexity: While the first method is efficient for large n if cost evaluation is easy, the second method (average ordered contribution allocation) can become computationally intractable (NP-complete) in the worst case (e.g., when it reduces to the Shapley value). The paper suggests that sampling-based approximation methods, similar to those for the Shapley value, could be used for approximation.
- Specific Ordering Properties: The paper explores several ordering principles but acknowledges that the choice of ordering can be crucial and might require further investigation for specific applications.
- Future Work: The paper implicitly suggests further research into more efficient computational methods for the average ordered contribution allocation, as well as exploring the application of these methods to a broader range of economic and financial problems. The potential for designing more sophisticated environmental tax schemes based on these principles is also highlighted.
Summary updated