Abstract
In multi-agent systems, agents often need to form coalitions to achieve complex goals. However, traditional models assume common knowledge of rewards, which is rarely the case in real-world scenarios. This paper introduces a decentralized mechanism for agents to form coalitions when they disagree on potential rewards. By utilizing a "Two Agent Auction," the system determines leadership and profit distribution, ensuring that the most optimistic agent assumes the risk while providing a guaranteed payout to their partner.
Introduction: The Challenge of Asymmetric Rewards
Traditional game theory, including concepts like the Shapley Value, typically relies on the assumption of "common knowledge"—the idea that every agent knows exactly how much a coalition is worth. In practice, agents often have different private estimates of the total utility a group will produce. For instance, in a merger between two startups, one may be optimistic about the joint product's value while the other remains skeptical. If they cannot agree on the partnership's value, determining a fair distribution of rewards becomes a significant hurdle. This research addresses coalition formation under these conditions of uncertain and asymmetric rewards.
The Decentralized Mechanism
The proposed approach consists of two primary stages: a greedy coalition formation algorithm and a specialized auction mechanism.
1. Coalition Formation Algorithm
Rather than relying on a centralized matchmaker, agents use a decentralized, greedy algorithm to rank potential partners and extend offers. This process is modeled as a variation of the "Stable Roommate Problem." Agents pair off into "proto-coalitions" of size two. This process repeats iteratively to build larger groups, where the head of each proto-coalition acts as a single entity in subsequent rounds.
2. The Two Agent Auction
Once two entities agree to pair up, they must resolve their differing valuations through an auction. This process assigns roles:
- The Manager: The agent who takes the risk, pays the other agent a fixed salary, and retains the remainder of the actual reward.
- The Contractor: The agent who receives a guaranteed payment regardless of the final outcome.
If both agents are optimistic and wish to manage, they enter an ascending auction, bidding up the salary they are willing to pay. Conversely, if both are pessimistic, they enter a descending auction to determine who will accept the lower guaranteed payout.
Key Insights and Analysis
The mechanism effectively turns "risk-bearing" into a negotiable commodity. By consolidating the uncertainty of the reward into the Manager role, the bargaining process is simplified.
One of the paper's central findings is Theorem 1, which proves that the agent with the higher private estimate of the coalition's value ($v(AB)$) will always win the managing role. This is intuitive: the agent who believes the reward is larger is naturally willing to pay a higher "rent" to their partner to secure the surplus.
Furthermore, while agents could theoretically reveal their private estimates to calculate a price instantly, the iterative auction allows them to reach a deterministic agreement without making their internal valuations public knowledge. As shown in the table below, the expected values for both agents converge as the number of negotiation rounds ($k$) increases.
Key Results
- Agreement Price (Theorem 2): The final agreement price (AP) is approximately the average of the manager's initial offer and the non-manager's valuation of the coalition.
- Computational Efficiency: The decentralized algorithm runs in $O(n^3)$ time for $n$ agents. This makes it significantly more scalable than traditional coalition calculations, which often require exponential time.
Limitations and Future Work
While the mechanism is robust, it assumes agents act rationally based on their estimates and does not fully account for strategic deception or "gaming the system." Additionally, the final price is heavily dependent on the agents' initial offers; determining the optimal strategy for these offers remains a complex game-theoretic challenge for future research. Finally, while the iterative pairing allows for large groups, the mechanism is strictly designed for two-way negotiations, leaving simultaneous multi-way bargaining for future exploration.
Summary updated