Introduction
In the field of Distributed Artificial Intelligence (DAI), autonomous agents must frequently coordinate their actions to achieve collective goals. Traditional coordination often relies on complex negotiation protocols, which are computationally expensive and communication-intensive. A simpler alternative is voting; however, standard voting systems are prone to strategic manipulation and typically only capture ordinal preferences (ranking) rather than cardinal utility (the magnitude of preference).
This paper proposes the application of the Clarke Tax—a classic mechanism from economics—as a robust preference-revelation tool. By taxing agents only when their specific vote alters the group outcome, the system incentivizes truth-telling as the mathematically optimal strategy, effectively solving the "free rider" and manipulation problems in multi-agent coordination.
Methodology: The Clarke Tax Mechanism
The core of the proposed system is a voting process where agents submit numerical "bids" representing their internal utility for various candidate states. The state with the highest aggregate bid is selected as the group's consensus action.
To prevent agents from overstating their preferences to ensure a win, the Clarke Tax is applied. An agent $i$ is fined a tax if and only if their vote changed the winning outcome. The tax amount is calculated as the loss of utility incurred by the other agents due to that change. Specifically, if the group's choice without agent $i$ would have been state $B$, but with agent $i$ it is state $A$, agent $i$ pays the difference between the total bids for $B$ and $A$ (excluding $i$'s own bid).
Assessment of Worth
Agents can calculate their bids using several strategies:
- All-or-nothing: Full value if the goal is met, zero otherwise.
- Partial satisfaction: Value proportional to the number of goal predicates satisfied.
- Future cost: Value based on the difference between the cost to reach the goal from the current state versus the candidate state.
Experimental Domain: Blocks World
The authors demonstrate the mechanism using a classic symbolic AI domain: the Blocks World. In this scenario, multiple agents move blocks to reach specific configurations. The system generates a "ballot" of candidate states by identifying maximal consistent subsets of all agents' goal predicates.
Key Insights and Results
Truth-telling as a Dominant Strategy
The most significant finding is that under the Clarke Tax, an agent's best move is always to bid their true utility. Overbidding risks a tax higher than the utility gained, while underbidding risks losing a preferred outcome to avoid a tax that would likely have been lower than the utility loss. This transforms negotiation from a strategic game into a pure information exchange.
Fairness and Work Distribution
By utilizing the "future cost" assessment method, the mechanism facilitates a "fair" consensus where agents end up approximately equidistant from their ultimate goals. The paper also addresses the "tax waste" problem—where tax revenue must be removed from the system to maintain incentives—by suggesting that taxes from one group of agents be redistributed to a separate, indifferent group.
Limitations and Future Work
While the Clarke Tax prevents individual manipulation, it remains vulnerable to collusion; a coalition of agents can still coordinate bids to skew results. Additionally, the computational complexity of generating all possible candidate states can be prohibitive in large-scale environments. Future research is needed to address the centralization of the tax collector and the enforcement of "debts" in systems where taxes are paid through future labor rather than currency.
Summary updated