TL;DR
This paper introduces a novel market mechanism that can support any Pareto efficient allocation of divisible goods, not just those that maximize social welfare. By allowing agents to have unequal budgets of tokens and setting anonymous prices, they demonstrate that any desired fair or efficient outcome can be achieved in a competitive equilibrium. This is a significant generalization of traditional market models and opens the door to supporting a wider range of desirable allocations, including fairness-oriented ones like the Rawlsian max-min.
What Problem Does This Paper Address?
Traditional economic models of competitive equilibrium, like Walrasian or Fisher markets, typically focus on finding allocations that maximize social welfare (i.e., the sum of all agents' utilities). While these models are well-understood and have efficient algorithms, they are limited in the types of outcomes they can support. For instance, they might not naturally lead to allocations that prioritize fairness or specific notions of equity, such as ensuring the worst-off agent is as well-off as possible (the Rawlsian max-min principle). The challenge is to design a market mechanism that can achieve any pre-defined Pareto efficient allocation, even if it's not necessarily the one that maximizes total welfare, while still maintaining the properties of a competitive equilibrium. This requires a more flexible approach to pricing and agent endowments.
Methods
The core of the paper's contribution lies in its constructive proof and algorithms for supporting arbitrary Pareto optimal allocations. The authors first transform the initial allocation into a "cycle-free" allocation using a graph-theoretic approach. This involves iteratively breaking cycles in a bipartite graph representing agent-item allocations, ensuring that agent utilities are preserved.
Next, they develop a pricing mechanism for each "tree" in the resulting forest structure. This involves setting item prices such that agents are indifferent between items they are allocated. Crucially, they then introduce scalar multipliers for each tree, which effectively scale both prices and budgets. These multipliers are determined by solving a fixed-point problem, which can be framed as a linear program. This mechanism allows for deviations between trees to be prevented. The key innovation is the use of unequal budgets for agents, which is essential for supporting arbitrary allocations, unlike traditional models that often assume equal endowments or budgets.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Arbitrary Pareto Optimality is Achievable: The most striking insight is that any Pareto efficient allocation can be supported as a competitive equilibrium. This is a powerful generalization beyond welfare maximization.
- Unequal Budgets are Key: The ability to assign agents unequal budgets of tokens is the critical mechanism that allows for supporting diverse Pareto optimal allocations. This contrasts with models that assume equal incomes or budgets.
- Graph Theory for Allocation Transformation: Using bipartite graphs and cycle elimination provides a systematic way to transform an initial allocation into a more structured form (a forest) without altering agent utilities, which simplifies the subsequent pricing and budgeting steps.
- Tree Multipliers for Inter-Tree Coordination: The introduction of scalar multipliers for each tree in the forest is a clever way to coordinate pricing and budgets across different components of the market, preventing profitable deviations between trees.
- Connection to Fairness: The paper explicitly shows how this framework can support the Rawlsian max-min allocation, demonstrating its utility for achieving fairness goals beyond pure efficiency.
Key Results
The paper's main result is a constructive proof that for any Pareto optimal allocation of divisible goods among agents with additive valuations, there exist anonymous item prices and agent-specific token budgets that support this allocation as a competitive equilibrium. Furthermore, they provide computationally efficient algorithms to find these prices and budgets. They demonstrate this by showing how to support the Rawlsian max-min allocation, a specific type of fair allocation.
Limitations and Future Work
- Divisible Items: The current framework assumes items are divisible. Extending the results to indivisible items is a significant open problem, as Pareto optimal allocations in divisible models may not translate directly to indivisible ones.
- Additive Valuations: The assumption of additive valuations is a simplification. Future work could explore more complex valuation functions like submodular or unit demand valuations.
- Strictly Positive Valuations: The paper assumes all valuations are strictly positive. Relaxing this assumption could be another avenue for future research.
- Number of Agents/Items: While efficient algorithms are provided, it remains an open question whether even faster algorithms exist for specific cases, such as a constant number of agents or items.
- Budget Diversity: The paper highlights the importance of unequal budgets. Further research could explore parameterizing budget diversity and characterizing allocations supported under various budget constraints.
Summary updated