Source-linked AI summary
Negotiating Socially Optimal Allocations of Resources
U. Endriss, N. Maudet, F. Sadri, F. Toni
TL;DR
The paper asks how negotiation over indivisible resources affects social welfare under different welfare interpretations. It develops a framework for connecting deal classes and local agent acceptability to socially optimal allocations, and shows that suitable classes can guarantee convergence, with complexity depending on utility assumptions. The results also expose limits involving large deal spaces and local criteria for envy reduction.
Problem
Existing multiagent negotiation work often focuses on local mechanisms and incentives, while this paper studies how local resource exchanges affect society-wide welfare under different welfare interpretations.
Method
The paper analyzes an abstract distributed resource-allocation framework across welfare notions, deal structures, rationality criteria, and restricted utility-function classes.
Results
Suitable deal classes can guarantee socially optimal outcomes, including utilitarian, egalitarian, and other welfare-specific optima, while required deal complexity depends on utility restrictions.
Takeaways & Limitations
Negotiation design can be evaluated by choosing welfare definitions and deal classes that align local agent behaviour with desired society-wide outcomes.
Takeaways & Limitations
The framework can require deals of any complexity, and local criteria cannot always detect whether a deal improves society-wide welfare such as minimum utility or envy.
Abstract
from arXiv · showhide
A multiagent system may be thought of as an artificial society of autonomous software agents and we can apply concepts borrowed from welfare economics and social choice theory to assess the social welfare of such an agent society. In this paper, we study an abstract negotiation framework where agents can agree on multilateral deals to exchange bundles of indivisible resources. We then analyse how these deals affect social welfare for different instances of the basic framework and different interpretations of the concept of social welfare itself. In particular, we show how certain classes of deals are both sufficient and necessary to guarantee that a socially optimal allocation of resources will be reached eventually.
1. Introduction
The paper studies how local negotiation over indivisible resources affects society-wide welfare under multiple welfare interpretations. It identifies deal classes that guarantee socially optimal allocations, with required deal complexity depending on preference restrictions.
- Motivation: The paper evaluates resource negotiation using welfare economics and social choice tools rather than focusing on specific negotiation strategies.Its perspective is global: it examines how local agent actions affect the society as a whole.
- Main contribution: Certain deal classes are sufficient and necessary to guarantee eventual convergence to socially optimal resource allocations.The convergence results connect local acceptability rules with emergent global behaviour.
- Deal complexity: Multilateral deals involving arbitrary numbers of agents and resources may be necessary under arbitrary utility functions.General preferences can therefore require deals with high structural complexity.
- Deal complexity: With additive utility functions, 1-deals can be sufficient for negotiating socially optimal allocations, whereas dichotomous preferences do not reduce structural complexity.Thus, preference restrictions affect which deal structures can guarantee optimal outcomes.
- Negotiation variants: With side payments, rational negotiation can maximise utilitarian social welfare; without side payments, it can still reach Pareto optimal allocations.Sections 3 and 4 also examine how restrictions on utility functions affect these convergence results.
- Welfare interpretations: The paper extends the analysis beyond utilitarian welfare to egalitarian and combined welfare interpretations.Its conclusion discusses tailoring welfare definitions and agent behaviour to different applications.
2. Preliminaries
The framework models distributed negotiation over indivisible resources, where deals transform allocations and admissibility depends on deal structure and local utility changes. Social welfare is evaluated through utility-based orderings, including utilitarian and egalitarian perspectives.
- Basic definitions: An allocation partitions a finite set of indivisible, non-sharable resources among at least two agents.Each agent initially holds a bundle, and negotiation reallocates resources between agents.
- Basic definitions: A deal is a pair of distinct allocations, and its involved agents are those whose bundles change.Deals can be composed, and independently decomposable deals combine changes affecting disjoint agent sets.
- Deal types: A 1-deal reallocates exactly one resource, while cluster, swap, and multiagent deals allow progressively broader exchange structures.The deal ontology distinguishes structural complexity by the numbers of agents and resources involved.
- Rationality criteria: Local rationality criteria classify deals using only the before-and-after utilities of agents whose bundles change.Conditions involving the globally poorest agent cannot be characterised locally because they require inspecting all agents.
- Social welfare: Social welfare compares allocations using utility vectors, including utilitarian aggregation and orderings based on the weakest agents.The ordered utility vector supports finer comparisons such as leximin and Lorenz comparisons.
- Scope: The framework’s deal-type ontology is not exhaustive and could be extended to bilateral deals involving two agents and any number of items.This is identified as an open scope boundary in the preliminaries.
- Social welfare: One example shows that utilitarian and leximin preferences can select different allocations, even when both allocations are Pareto optimal.The example also reports a Lorenz improvement produced by swapping two agents’ bundles.
3. Rational Negotiation with Side Payments
With side payments, agents negotiate resource reallocations using payment functions and individual rationality, where every accepted deal increases utilitarian social welfare. Any sequence of individually rational deals reaches a welfare-maximizing allocation, although unrestricted deal complexity may be necessary in general.
- Negotiation model: Side payments compensate agents for utility losses while preserving total money in the system through a payment function.Positive payments represent money paid; negative payments represent money received, and all payments sum to zero.
- Negotiation model: Individual rationality requires a payment function making every affected agent prefer the deal, while unaffected agents may receive no payment.An agent accepts when its payment is smaller than its utility gain or exceeds its utility loss.
- Welfare criterion: An individually rational deal occurs exactly when it strictly increases utilitarian social welfare.Thus, utilitarian welfare functions as the relevant measure of social well-being for this negotiation model.
- Sufficiency: Any sequence of individually rational deals eventually reaches an allocation with maximal utilitarian social welfare.Finitely many allocations ensure termination, while every welfare-improving deal remains available until an optimum is reached.
- Necessary deal complexity: Any non-independently decomposable deal may be necessary for guaranteed optimal negotiation, even with monotonic or dichotomous utility functions.Therefore, structurally restricted protocols cannot generally guarantee optimal outcomes, despite unlimited time or computational resources.
- Additive scenarios: Additive utility functions reduce the sufficient deal class: any sequence of individually rational 1-deals reaches maximal utilitarian social welfare.This restriction applies when combining resources creates no synergy effects.
4. Rational Negotiation without Side Payments
Without monetary side payments, maximal utilitarian welfare cannot always be guaranteed, so the framework targets Pareto optimality using cooperatively rational deals. General utility classes may still require complex deals, while 0-1 additive scenarios permit welfare maximization with 1-deals.
- Motivation: Unlimited money is an implicit assumption of the side-payment framework, but its availability is questionable for resource allocation.Agents may need substantial payments to complete welfare-improving reallocations.
- Limits of utilitarian optimization: Without money, negotiation may terminate at a non-optimal allocation even when transferring a resource would increase utilitarian social welfare.With utilities 4 and 7 for the same resource, the welfare gain is 3, but no individually rational deal exists without compensation.
- Cooperative rationality: Cooperative rationality permits deals that leave every agent no worse off while requiring at least one agent to become strictly better off.This weakened criterion replaces strict individual improvement for money-free negotiation.
- Pareto optimality: Any sequence of cooperatively rational deals eventually reaches a Pareto optimal allocation.Each deal strictly increases utilitarian welfare, and the finite allocation space guarantees termination.
- Necessary deal complexity: Any non-independently decomposable deal may be necessary to guarantee Pareto optimality, even with monotonic or dichotomous utility functions.Thus, general money-free negotiation cannot guarantee optimal outcomes using only structurally simple deals.
- 0-1 scenarios: In 0-1 scenarios, any sequence of cooperatively rational 1-deals reaches an allocation with maximal utilitarian social welfare.A resource held by an agent valuing it at 0 can be passed to an agent valuing it at 1.
5. Egalitarian Agent Societies
The egalitarian framework studies local deal criteria aimed at maximizing the welfare of the weakest agents. Equitable deals guarantee convergence to maximal egalitarian social welfare, but structurally simple deal classes are generally insufficient.
- Egalitarian negotiation applies the paper’s methodology to convergence toward allocations with maximal egalitarian social welfare.
- Pigou-Dalton Transfers and Equitable Deals: Pigou-Dalton transfers involve two agents and preserve their combined utility, but they are not sufficient to guarantee egalitarian optima.In the example, no inequality-reducing deal is available from the initial allocation, although exchanging the resources raises egalitarian welfare from 3 to 5.
- Pigou-Dalton Transfers and Equitable Deals: Equitable deals improve the welfare of the weakest involved agent, and every Pigou-Dalton transfer is equitable, but the converse does not hold.An equitable deal may increase inequality among the agents involved when the happier agent gains more utility than the weaker agent.
- Local Actions and their Global Effects: A rise in egalitarian social welfare implies an equitable deal, while every equitable deal implies a strict leximin rise.These implications support a convergence proof based on the finite number of allocations and the transitivity of the leximin ordering.
- Maximising Egalitarian Social Welfare: Any sequence of equitable deals eventually reaches an allocation with maximal egalitarian social welfare.
- Maximising Egalitarian Social Welfare: No structurally simple deal class is sufficient for optimal egalitarian outcomes: every non-decomposable deal may be necessary, even with dichotomous utilities.Equitable deals can remain possible after a social-welfare maximum has been reached, and detecting that condition requires a non-local criterion.
6. Negotiating Lorenz Optimal Allocations
The Lorenz analysis examines whether existing local rationality criteria can generate Lorenz improvements in indivisible-resource domains. General composition fails, but in 0-1 scenarios simple Pareto-Pigou-Dalton deals guarantee convergence to Lorenz-optimal allocations.
- Lorenz domination is separable, but existing local rationality criteria do not generally compose into a class capturing all Lorenz improvements.The framework’s finite indivisible-resource domain prevents arbitrary utility transfers assumed in more general results.
- Lorenz Domination and Existing Rationality Criteria: Cooperatively rational deals and Pigou-Dalton transfers always produce Lorenz improvements, whereas equitable deals may fail to do so.
- Simple Pareto-Pigou-Dalton Deals and 0-1 Scenarios: In 0-1 scenarios, simple Pareto-Pigou-Dalton deals are 1-deals that are either cooperatively rational or Pigou-Dalton transfers.
- Simple Pareto-Pigou-Dalton Deals and 0-1 Scenarios: Any sequence of simple Pareto-Pigou-Dalton deals eventually reaches a Lorenz-optimal allocation in 0-1 scenarios.Each deal yields a Lorenz improvement, and finiteness of the allocation space ensures termination.
- Simple Pareto-Pigou-Dalton Deals and 0-1 Scenarios: The convergence result means agents need not choose among admissible simple Pareto-Pigou-Dalton deals to guarantee a global optimum.
7. Further Variations
The paper examines elitist and envy-free interpretations of social welfare, showing both their negotiation implications and limits. Elitist welfare supports champion-focused cooperation, whereas envy-freeness can conflict with Pareto optimality and resist local deal criteria.
- 7.1 Elitist Agent Societies: Elitist social welfare is tied to the welfare of the currently best-off agent, so agents cooperate to support their champion.This may suit systems designed so that at least one agent achieves a goal, even when the eventual champion is unknown.
- 7.1 Elitist Agent Societies: Local elitist deal acceptance would require increasing the maximal individual welfare among the agents involved in the deal.The paper notes that this criterion is technically analogous to the egalitarian case.
- 7.1 Elitist Agent Societies: With monotonic utility functions, assigning all resources to the agent valuing the full bundle most highly yields an elitist optimum.More generally, an elitist optimum can be found by checking which utility function has the highest peak.
- 7.2 Reducing Envy amongst Agents: Envy-freeness requires every agent to value its own bundle at least as highly as every other agent’s bundle.It is motivated by longer-term collaboration, where perceived unfairness may encourage an agent to leave the coalition.
- 7.2 Reducing Envy amongst Agents: In the two-agent example, allocations that are envy-free are not Pareto optimal, while Pareto-optimal one-resource allocations are not envy-free.The conflict arises because both agents have identical preferences and prefer the second resource to the first.
- 7.2 Reducing Envy amongst Agents: No local deal criterion based only on participating agents can determine whether a deal reduces envy, because nonparticipants’ envy may also change.A deal can give a participant a bundle preferred by an uninvolved agent, altering that agent’s envy.
8. Conclusion
The paper establishes which deal classes guarantee socially optimal outcomes under several welfare orderings and utility restrictions, and identifies corresponding necessity results. It concludes by advocating welfare engineering: choosing welfare criteria and designing negotiation mechanisms around them.
- Conclusion: The framework studies multilateral exchanges of indivisible-resource bundles and evaluates their effects under different social welfare orderings.The paper’s convergence results concern reaching optimal allocations through negotiation.
- Conclusion: Individually rational deals suffice for maximal utilitarian welfare, while additive domains allow individually rational 1-deals to suffice.These are Theorems 1 and 3, respectively.
- Conclusion: Cooperatively rational deals suffice for Pareto optimality, and cooperatively rational 1-deals suffice for maximal utilitarian welfare in 0-1 domains.These results are Theorems 4 and 6.
- Conclusion: Equitable deals suffice for maximal egalitarian welfare, while simple Pareto-Pigou-Dalton 1-deals suffice for Lorenz-optimal allocations in 0-1 domains.These results are Theorems 7 and 9.
- Conclusion: For unrestricted deals, necessity theorems show that every independently non-decomposable deal may be required to negotiate an optimal allocation under the relevant rationality criterion.Thus, protocols excluding such deals cannot guarantee all corresponding optimal outcomes.
- Conclusion: The paper proposes welfare engineering: selecting application-appropriate social welfare orderings and designing agent behaviours and negotiation mechanisms that permit or guarantee optimal outcomes.The approach is compatible with autonomous agents and also applies to centralized mechanisms such as combinatorial auctions.
- Conclusion: Future work includes additional welfare orderings, complexity analysis, and practical mechanisms for multilateral negotiation.The authors specifically identify protocols and strategies for agents agreeing on multilateral deals as an open direction.