Dynamically formed internet coalitions hold open the promise of harnessing the power of groups in many contexts:
There are a large number of architectural and theoretical challenges to be overcome before dynamic coalitions can throw their weight around on the internet. Like-minded participants must have a way of finding one another; the definition of "like-minded" in a given context must be determined. The division of labor, and the reintegration of sub-results, may need to be handled. The contribution of each coalition member to the group effort might need to be ascertained and rewarded appropriately [2, 12] (techniques like the Shapley Value [8, 9] may be useful in these cases). There may be issues of privacy and security as well (for example, I may be willing to enter into a group purchase of cars, but I'd rather that only the dealer knew exactly which optional accessories I was ordering).
Another important issue that needs to be resolved in the formation of coalitions is the veracity of the participants. Can a potential coalition partner gain an advantage by lying, either about its goals or capabilities? We have been examining this question, building on previous work in two-agent Task Oriented Domains [5, 14].
Sometimes, agents in an encounter may find it to their benefit to exchange tasks, thereby lowering their overall cost of execution. When agents are able to agree on such an exchange, they have reached a deal. The original work on TOD's considered only two-agent encounters, and explored the potential for deception as agents tried to reach a deal. For example, an agent could sometimes benefit by hiding some of its tasks, or by creating a fake task, that would improve its position in the negotiation.
Certain DAI work [7, 3, 11] has recently focused on more-than-two-agent domains, and general coalition formation. Groups of agents may agree to work together for the benefit of all the members of the group. The challenges here are to find these coalitions of agents, and to determine how the joint reward should be divided among them. Most of this work assumes complete knowledge among the interacting agents and/or truthful agents. These assumptions are not realistic in many domains, including standard internet domains where dynamic coalitions are being formed by agents representing user interests. The possibility of incomplete information among agents opens up the possibility of deception as part of the negotiating strategy of an agent, as was examined for TODs in the two-agent case.
What we are examining in this paper is thus the extension of the original
TOD work from the two-agent case to the multiple agent case. Although restricted
to the simplest of domains, it begins to uncover the opportunities for
deception in coalition formation, which has direct bearing on the dynamic,
automatic formation of coalitions on the internet.
In this abstract, we present the main theorems and results of this
work. Admittedly, it's a bit dry. But startling and entertaining examples
(and detailed proofs) exist for the full paper version.
The Shapley Value [9, 12] for agent i is a weighted average of all the utilities that i contributes to all possible coalitions. The weight of each coalition is the probability that this coalition will be formed in a random process that starts with the one-agent coalition, and in which this coalition grows by one agent at a time such that each agent that joins the coalition is credited with his contribution to the coalition. The Shapley Value is actually the expected utility that each agent will have from such a random process (assuming any coalition and permutation is equally likely).
Following [13], we can define a Shapley Value-based mechanism for subadditive TODs that forms the full coalition and divides the value of the full coalition using the Shapley Value. The mechanism simply chooses the following (all-or-nothing) mixed deal, (p_1,...,p_n), such that p_i = $\frac{\sum_{S \subset N, i \not\in S} \frac{(n-|S|-1)! |S|!}{n!} \Delta_c^i(S)}{c(N)}.$ [Pardon my LaTeX.]
Theorem 1 [Futility of Hiding Tasks]: For any encounter in a multi-agent subadditive TOD, using the Shapley Value-based mechanism over all-or-nothing deals, every "hiding" lie is not beneficial.
Theorem 2 [Phantom Lies Are Unsafe]: For any encounter in a multi-agent subadditive TOD, using the Shapley Value-based mechanism over all-or-nothing deals, every "phantom" lie has a positive probability of being discovered. Therefore, with a sufficiently severe penalty mechanism, telling the truth is the optimal strategy.
Theorem 3 [Futility of Decoy Tasks in Concave TODs]: For any encounter in a multi-agent concave TOD, using the Shapley Value-based mechanism over all-or-nothing deals, every "decoy" lie is not beneficial.
The following table summarizes the situation, for the Shapley Value-based mechanism over all-or-nothing deals:
| Hidden | Phantom | Decoy | |
| Subadditive TODs | T_ | T/P | L |
| Concave TODs | T_ | T_ | T_« |
| Modular TODs | T | T | T« |
The entries in the table marked T signify that honesty is the best policy (lies are never beneficial). The entry L means that there exists an encounter such that at least one of the agents has an incentive to lie. The entry marked T/P refers to lies that are not beneficial because they may be discovered; if the agent tells the truth, it is because he is afraid of the penalty that he will be fined if his lie is discovered. Thus, T/P can be transformed to T if the mechanism is enhanced to include a sufficiently high penalty for discovered lies. The symbols _ and « signify implication between cells in the table, with "_" signifying downward implication and "«" signifying implication towards the cell on the left (in other tables we will also use » and ^).
Theorem 4: For any encounter in a two-agent subadditive TOD, using the Shapley Value-based mechanism over all-or-nothing deals, if agent A1 knows that the cost of T1 is greater than the cost of T2, he can generate a default decoy lie that may benefit him, and will never harm him.
The situation is much more complicated in multiagent subadditive TODs. As in the two-agent domain there are many examples in which a decoy lie is beneficial and there are many examples in which a decoy lie is harmful. However, it is not so simple to characterize the cases in which a decoy lie can only benefit the liar (and never harm him), nor the cases in which a decoy lie can only harm the liar (and never benefit him).
In the full paper, we give 7 examples, differing from one another in subtle ways, that do or do not allow for beneficial deception. We then present a theorem that characterizes the relationship among agent costs that allow for beneficial deception.
In the full paper, we also refine the concept of concavity to speak of an encounter which is "concave at agent k", and show that in this situation, decoy lies are not beneficial.
Theorem 5: For any encounter in a multi-agent subadditive TOD, using the Shapley Value-based mechanism over all-or-nothing deals, which is concave at agent k, every "decoy" lie is not beneficial to agent k.
With encounters in multiagent TODs, and any PMM over pure deals, the following table summarizes the opportunities for deception (notice that the opportunities for lying are increased):
| Hidden | Phantom | Decoy | |
| Subadditive TODs | L | L | L |
| Concave TODs | L^ | L^» | L^ |
| Modular TODs | L^ | T | T« |
With encounters in multiagent TODs, and any PMM over mixed deals, the following table summarizes the opportunities for deception:
| Hidden | Phantom | Decoy | |
| Subadditive TODs | L | T/P | L |
| Concave TODs | L^ | T | T_« |
| Modular TODs | L^ | T | T« |
Finally, with encounters in multiagent TODs, and any PMM over all-or-nothing deals, the following table summarizes the opportunities for deception:
| Hidden | Phantom | Decoy | |
| Subadditive TODs | T_ | T/P | L |
| Concave TODs | T_ | T | T_« |
| Modular TODs | T | T | T« |
[2] Theories of Coalition Formation, J. P. Kahan and A. Rapoport. London: Lawrence Erlbaum Associates. 1984.
[3] Forming Coalitions in the Face of Uncertain Rewards. Steven Ketchpel, Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI'94), 1994, pp. 414-419.
[4] Globally Distributed Computation over the Internet --- the POPCORN Project. Noam Nisan, Shmulik London, Ori Regev, and Noam Camiel. Proceedings of the 18th International Conference on Distributed Computing Systems, 1998.
[5] Rules of Encounter: Designing Conventions for Automated Negotiation Among Computers. Jeffrey S. Rosenschein and Gilad Zlotkin. MIT Press, Cambridge, Massachusetts. 1994.
[6] Coalition Formation among Bounded Rational Agents. T. Sandholm and V. Lesser. 14th International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Canada, pp. 662-669. 1995.
[7] Coalitions among Computationally Bounded Agents. T. Sandholm and V. Lesser. Artificial Intelligence 94(1), 99-137, Special issue on Economic Principles of Multiagent Systems. 1997.
[8] Cores of convex games. L. S. Shapley. International Journal of Game Theory, 1:11-26. 1971.
[9] A value for {n-Person} games. L. S. Shapley. In A. E. Roth, ed., The Shapley Value. Cambridge: Cambridge University Press, Chapter 2, pp. 31-40. 1988.
[10] Coalition formation among autonomous agents: Strategies and complexity. Onn Shehory and Sarit Kraus. Pre-Proceedings of the Fifth European Workshop on Modeling Autonomous Agents in a Multi-Agent World. 1993.
[11] Methods for Task Allocation via Agent Coalition Formation. Onn Shehory and Sarit Kraus. Artificial Intelligence. Volume 101, Numbers 1-2, May 1998, pp. 165-200.
[12] Individual contribution and just compensation. H. P. Young, In A. E. Roth, ed., The Shapley Value. Cambridge: Cambridge University Press, Chapter 17, pp. 267-278. 1988.
[13] Coalition, Cryptography, and Stability: Mechanisms for Coalition Formation in Task Oriented Domains, Gilad Zlotkin and Jeffrey S. Rosenschein. The National Conference on Artificial Intelligence, Seattle, Washington, August 1994, pages~432--437.
[14] Mechanism Design for Automated Negotiation, and its Application to Task Oriented Domains, Gilad Zlotkin and Jeffrey S. Rosenschein. Journal of Artificial Intelligence. Volume 86, Number 2, October 1996, pages 195--244.
[1] N. Camiel, S. London, N. Nisan and O. Regev.
The POPCORN project – An interim report. Distributed computation over the
internet in Java. Sixth International World Wide Web Conference.
Santa-Clara. 1997.
The POPCORN project provides an infrastructure for globally distributed computation over the entire Internet. It provides any programmer connected to the Internet with a single huge virtual parallel computer composed of all processors on the Internet which care to participate at any given moment. A market-based mechanism of trade of CPU time underlies the system, so as to motivate processors to provide their CPU cycles for other people's computations.
In our work we have been examining the problem of coalition formation. The POPCORN project is an example of a possible use of this theory.
[2] E. Ephrati and J. S. Rosenschein. The Clarke tax as consensus mechanism among automated. In Proceedings of the Ninth National Conference on Artificial Intelligence. Boston. 1991.
Ephrati and Rosenschein presented a voting mechanism called the Clarke Task mechanism. In a voting setting, each agent expresses its preferences, and a group choice mechanism is used to select the result. This result is enforced so that all agents have to abide by the solution prescribed by the mechanism. Ephrati and Rosenschein have also considered the case where the preferences of the agents are not known. In this case the agents have to declare their preferences. However, the preferences declared might be different from the true preferences. The Clarke tax procedure assures that every agent should always tell his true preferences values.
Ephrati and Rosenschein have used a variety of different mechanisms to reach consensus among agents. Using these mechanisms, they considered the case of lack of information and they have chosen a protocol that motivates the agents to tell the truth, as we try to do with coalition formation.
[3] P. J. Gymtrasiewics and E. H. Durfee. A rigorous, operational formalization of recursive modeling. In Proceedings of the First International Conference on Multi-Agent Systems (ICMAS), pages 125-132. 1995.
Another method to coordinate the activities of autonomous agents is the Recursive Modeling Method (RMM). RMM views a multi-agent situation from the perspective of an agent that is individually trying to decide what actions it should do right now. To make decisions, RMM uses a decision-theoretic paradigm of rationality, where an agent attempts to maximize its expected utility given its beliefs. The basic building block of RMM’s representation is a payoff matrix that expresses the agent’s beliefs about its environment. In order to solve its own decision-making situation, the agent needs an idea of what the other agents are likely to do. This can be done by representing what it knows about the other agents’ decision-making situations, thus modeling them in terms of their payoff matrices. The fact that other agents could also be modeling others, including the original agent, leads to a recursive model.
Thus, the RMM is another coordination model based on game theory which assumes that different agents may have different knowledge about the world.
[4] S. Ketchpel. Forming coalitions in the face of uncertain rewards. In Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 414-419. 1994.
The work of Ketchpel also addresses the problem of forming coalitions between self-interested agents in super-additive environments. Ketchpel noted that the coalition formation problem is related to the stable marriage problem and makes use of algorithms for the latter problem. Ketchpel points out that in reality the value that a coalition obtains may be unknown. In fact, each agent might have a different expectation for the value of the collaboration, and both values may be different from the true utility. He suggests a modification to the algorithm to solve this problem.
The problem that Ketchpel refers to is derived from the fact that the agents don’t have full information; this is also what makes lying possible, and this is exactly the problem we address in our work.
[5] J. S. Rosenschein and G. Zlotkin. Rules of encounter. MIT press. 1994.
Rosenschein and Zlotkin use tools from game theory for analyzing different negotiation mechanisms among pairs of agents. Rosenschein and Zlotkin developed a domain theory for negotiation. The aim of this theory is to classify domains where agents can operate in a way that an appropriate negotiation mechanism could be chosen. They categorized classes of domains into a three-level hierarchy, where each level is increasingly more general. For each domain, they designed a negotiation protocol (a negotiation protocol means the public rules of the negotiation). A protocol specifies the kind of deals the agent can make, as well as the sequence of offers and counter-offers that they are allowed.
They also observed that common knowledge is somewhat unrealistic. In order to get around the lack of information, Rosenschein and Zlotkin suggest that the agents will explicitly declare their tasks and resources. In this case the agents may lie in order to gain in the subsequent negotiation. Rosenschein and Zlotkin have analyzed when rational agents are motivated to declare truthfully.
In our work, we extend their work from the two-agent case to the multiple agent case.
[6] T. W. Sandholm and V. R. Lesser. Coalitions between computationally bounded agents.
Sandholm and Lesser’s research also discusses coalition. What makes their work unique is the fact that they relax the assumption of perfect rationality. In their setting, the agents lack full rationality. Thus, the deduction process itself is costly: either an agent has to pay for computational resources or the computation with his own limited resources takes time. Based on the agents’ problem-solving algorithms, Sandholm and Lesser state which agents should form coalitions and which coalition structures are stable. These prescriptions differ significantly from those for fully rational agents.
[7] L. S. Shapley. A value for n-person games. In H. W. Kunn and A. W. Tucker, editors, Contributions to the theory of games 2, Annals of mathematics studies 28, (Princeton University Press, Princeton N.J.), pages 307-317. 1953.
Coalition formation has been widely studied in game theory. Many of the solution concepts for coalition formation are static. They address the question of how to divide the payoffs among the agents. But being static in nature, they do not usually address the dynamics of the coalition formation process. Nevertheless, models of game theory can be used as a basis for the agents’ interaction protocols. Automated agents in DAI can be modeled as players of game-theoretic models. Analyzing the coordination between agents as a game gives a stronger theoretical basis to the research. In this work we have also used tools from game theory.
[8] O. Shechory and S. Kraus. Task allocation via coalition formation among autonomous agents. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, pages 661-665. 1995.
Shechory and Kraus present an algorithm for coalition structure generation among cooperative – social welfare maximizing, i.e., not self-interested – agents. They consider situations where each task should be attached to a group of agents, which will perform the task. Since task allocation among agents may be approached as assigning groups of agents to tasks, the partition of agents into subgroups becomes the main issue. Therefore, the task allocation problem becomes similar to the set-partitioning problem (SPP). The SPP is finding a partition of a set into subsets, so that the partition has minimal cost. The SPP is an NP-hard problem. This implies a computational complexity which is too high. However, a variety of heuristic algorithms for solving this problem have been suggested. Among them, is the algorithm of Chvatal. Based on this algorithm, Shechory and Kraus present a greedy distributed set-partitioning algorithm for autonomous agents that work as DPS system.
[9] O. Shechory and S. Kraus. A kernel-oriented model for coalition formation in general environments: Implementation and results. In Proceedings of the National Conference on Artificial Intelligence, pages 134-140. 1996.
Shechory and Kraus analyze coalition formation among rational, self-interested agents in environments, which are not necessarily superadditive.
They present a distributed, negotiation-based, polynomial, kernel-oriented algorithm. The algorithm consists of steps in which coalitions transmit, accept, and reject proposals for creating new coalitions. The algorithm starts with all the agents in single-membered coalitions. At each step, at least one coalition will attempt to improve the payoffs of its members by making a coalition formation proposal to another coalition. The acceptance of such a proposal will improve the situation of the agents involved. The algorithm may continue until all the proposals of all the coalitions are rejected or until a steady state has been reached.
The work of Shechory and Kraus considers a more general environment than ours, but it assumes full information, which is generally not realistic.
[10] G. Zlotkin and J. S. Rosenschein. Coalition, cryptography, and stability: Mechanisms for coalition formation in task oriented domains. In Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 432-437. 1994.
Zlotkin and Rosenschein analyze coalitions between rational, self-interested agents. They discuss the special case of subadditive task-oriented domains, which are a strict subset of task-oriented domains. In such domains, agents will always form the grand coalition (i.e., one coalition in which all the agents are members), since this coalition structure maximizes the utility that the agents can derive. The main problem in such domains is how to divide the joint utility between the agents. Zlotkin and Rosenschein suggest a mechanism in which each agent will handle the tasks of all agents with a certain probability. This probability is set according to the Shapley value, in a way that guarantees each agent an expected utility that equals its Shapley value.
A naive method that guarantees each agent an expected utility that equals each Shapley value has exponential complexity in the number of agents, but Zlotkin and Rosenschein present a novel cryptographic method for achieving this with linear complexity in the number of agents.
In this work we consider their mechanism when agents don’t have full
information about each other’s goals.