Hello Stack Overflow......

I hate deadlock!
I hate deadlock!

I hate deadlock!

Well... I am doing a experiment on automatic coalition formation. It works fine until the deadlock comes...

A Review on Multilateral Bargaining - Part 2

In my last post I reviewed Aumann's approaches on Multilateral Bargaining Problems[1]. He presents that a multilateral bargaining problem has a bargaining set as a kind of solution. However, the computation on finding the bargaining set is complicated and Aumann did not give an method to find such a solution in a general n-player game.

Elaine Bennett had made a great improvement on this problem[2]. Bennett proposed a solution and interpret it as a set of imputations for every potential coalition. In the imputation, the partition of utilities is related to a bargaining function f^S and agents' outside options d^S. I will explain this in detail through the example below.

Example 2.1(the example 2 in [1]) v(1)=v(2)=v(3)=v(123)=0, v(12)=20,v(23)=30,v(13)=100
Aumann gave the bargaining set for this problem such that

{(0,0,0;1,2,3), 
(20≤x1≤70,0,100-x1;13,2), 
(20,0,0;12,3)
(0,0,30;1,23)}

The outside option is the utility a player i would obtain if he broke off negotiation in a coalition S and took the initiative to form his best alternative coalition. Therefore, the player 1's outside option in coalition {13} is 20 (if he can form a coalition with player 2) and the outside option in {12} is x1. 

Therefore "the agreement in coalition S depends on the agreements in other coalitions which depend in turn on the outside options in these other coalitions, which depend in turn on the agreement in the coalition S." (like a tongue twister...) And this caused the interrelationships between bargaining problems of the severals coalitions. 

Now for instants let the bargaining function f works in a way that divides the share equally, therefore x1=45. and we then have a Bennett's solution for example 2.1. We notice that player 1's outside option for coalition {12} is 45, which is infeasible for the coalition {12}, then {12} will not form. 

Bennett had proved that there is at least one of the solution agreements is feasible in a multilateral bargaining problem.

However, a solution is not an outcome. Imaging that in example 2.1 if player 1 and 2 form a coalition, the coalition structure is broken off and player 3 will not form a coalition any more. 

Moreover, the actual outcome may be mattered if the coalitions cannot simultaneously form. 
Example 2.2(the example 3 in [2]) v(12)=40,v(23)=34,v(34)=20,v(14)=34,v(S)=0 for other S.
One solution to example 2.2 is (22,22,12,12;14,23), however, if player 4 wait for player 2 and 3 to form a coalition and leave, then he can bargain with player 1 without a viable outside option. Then player 4 will yield a payoff of 17. 

(It too late now and I have to stop here and go to sleep... I will continue a bit more on this paper in my next update:p)


[1] Aumann, Robert J. The bargaining set for cooperative games. Defense Technical Information Center, 1961.
[2] Bennett, Elaine. "Multilateral bargaining problems." Games and Economic Behavior 19.2 (1997): 151-179.

A Review on Multilateral Bargaining - Part 1

From this post, I will start to write a series of reviews on multilateral bargaining and coalition formation mechanisms. I would like to do this to resort some of my understanding on related topics.

This series will review some approaches on both economic (game theory approaches) and multi-agent systems.

========================================================================

I think many people who are interested in game theory may have heard the name of Nash and Rubinstein, who have both made outstanding contribution to the game theory. The former one proposed the famous Nash bargaining solution and the later one designed the well-known Rubinstein Model. However, those two approaches are mainly developed in the field of the bilateral bargaining problem (even some parts can be extended to multilateral bargaining problem). For the multilateral bargaining problem, I noticed that there are also some great researchers doing some interesting and unique researches.

The most different between bilateral bargaining and multilateral bargaining is that the later one is effected by coalition matters and therefore some theories such as Nash bargaining solution will be not suitable any more. Instead, it is very necessary to take the coalition formation issue into consideration. 

The earliest paper I have found is [3] by Robert J. Aumann and Michael Maschler, which discussed how the coalition can be "stable" under n-player bargaining games. For a simple example, 

Example 1.1  In a bargaining game there are three players, labeled as 1, 2, 3. Any two of them can work together as a coalition. The coalition {1,2} and {1,3} can obtain 100 to work together, whilst coalition {2,3} can gain only 50. Otherwise, they can obtain nothing, such that

v(1)=v(2)=v(3)=0; v({1,2})=v({1,3})=100, v({2,3})=50; v({1,2,3})=0

In example 1.1, if player 1 proposes an utility partition (80,20,0) for coalition structure {{1,2},3},then player 2 can object by pointing out that (0,21,29) for {1,{2,3}}; on the other hand,  (75,25,0) {{1,2}.3} is stable, because an objection of player 2, e.g. (0,26,24) {1,{2,3}} can be met by a counter objection (75,0,25) {{1,3},2}.

Therefore, Aumann proposed a definition such that a stable coalition satisfies that for each "objection" of a subset of the coalition, there is a "counter objection" against the "objection".

In this paper[3], Aumman have enumerated such a lot examples for n-player games, n=2, 3, 4, 5, and in pretty good simpleness and clearness. This work has build a foundation for many later works.

The one who proposed a rigorous analysis is in Elaine Bennett's paper[4] (also a later version [5]). In his work, the interrelationships among coalitions became a key issue in multilateral bargaining games. Also the outside option has been discussed in depth. (Aumann has noticed there are some factors as an "alternatives"). I will write more on this in my next update.

Also I plan to write reviews on following topics in my future updates:

3C/3P games (one man out)

Nash stable

Bargaining solutions

Coalition formation mechanisms (in multi-agent systems)

Negotiation mechanisms (in multi-agent systems)

......

[1] Rubinstein, Ariel. "Perfect equilibrium in a bargaining model." Econometrica: Journal of the Econometric Society (1982): 97-109.

[2] Nash Jr, John F. "The bargaining problem." Econometrica: Journal of the Econometric Society (1950): 155-162.

[3] Aumann, Robert J. The bargaining set for cooperative games. Defense Technical Information Center, 1961.

[4] Bennett, Elaine. "Multilateral bargaining problems." Economic Department, University of California at Los Angeles WP594 (1986).

[5] Bennett, Elaine. "Multilateral bargaining problems." Games and Economic Behavior 19.2 (1997): 151-179.

Review: Agents in Electronic Commerce: Component Technologies for Automated Negotiation and Coalition Formation

This paper reviews six component technologies for automated negotiation and coalition formation.

1. OCSM-contracts in marginal cost based contracting
 Different agents may have different resource so they have different abilities to handle the tasks. A model which allow agents to reallocate tasks.  Agents make contracting decisions based on marginal cost (I am not very sure what is the marginal cost here). The model also defines how agents reallocate task and how to pay for the changing. The author also gives the proof that the globally optimal task allocation can be reached by any hill-climbing algorithm in a finite number of steps. However, the time cost on a large-scale system is still a problem. [2] gives experimental results.

2. leveled commitment contracts
 The contract is binding among agents in traditional negotiation protocols. However, there are events may cause agents decommit. Self-interest agents will decommit when they can get more utility and they will try to avoid the penalty. Thus, the contracts should be able to avoid this situation. Leveled commitment contracts implement the backtracking method for avoiding local optima.

3. anytime coalition structure generation with worst case guarantees
 This part discuss the superadditive and how to guarantee the worst cast is within a bound.

4. trading off computation cost against optimization quality within each coalition

5. distributing search among insincere agents
A method for distributing search works among self-interest agents without a trusted third party.

6. unenforced contract execution.

For 4 & 6, I think I need to read again before I write something...



[1] T. Sandholm “Agents in Electronic Commerce: Component Technologies for Automated Negotiation and Coalition Formation” Autonomous Agents and Multi-Agent Systems, 3(1), 73-96. 2000.

[2] M. R. Andersson and T. W. Sandholm, ‘‘Time-quality tradeoffs in reallocative negotiation with combinatorial contract types,’’ in Proceedings of the National Conference on Artificial Intelligence (AAAI), Orlando, FL, 1999, pp. 3-10.

Review: A Classification Scheme for Negotiation in Electronic Commerce

In the paper "A Classification Scheme for Negotiation in Electronic Commerce", the authors raised problems of "first-generation" system and also give the definition of "Negotiation Space" in order to clarify the possible parameters which may be considered in the space.

The first generation systems only provide users some choices to select.Even though there may be some shopping assistants which can help users look for the best deal, the actions left for users are still limited.

Only select/accept choices mode is not enough for implementing complicated negotiation. By defining the negotiation space, it promotes a clearly framework for next generation negotiation systems. The negotiation space indicated the possible parameters may used in negotiation procedure. Moreover, the negotiation space allows automatic negotiation mechanisms to reach the best deals. More actions for the agents, such as to generate offers, to accept/decline offers, can be implemented to the systems.

Although the negotiation space concept provides a good classification scheme for negotiation, this paper had not give any practical implementation, but three related papers may provide more information about it. They are:

Paurobally and Cunningham

Vetter and Pitsch

Oliveira and Rocha



Reference

E. Oliveira and A.-P. Rocha. Agents advanced features for negotiation in electronic
commerce and virtual organisation formation process. In C. Sierra and F. Dignum,
editors, This book. Springer Verlag, June 2000.

Lomuscio, A. R., M. Wooldridge, and N. R. Jennings. (2001). “A Classification Scheme for Negotiation in Electronic Commerce,” in F. Dignum and C. Sierra (eds.), Agent-Mediated Electronic Commerce: A European Perspective. Springer Verlag, 19–33.

M. Vetter and S. Pitsch. Towards a flexible trading process over the internet. In C. Sierra and F. Dignum, editors, This book. Springer Verlag, June 2000.

S. Paurobally and J. Cunningham. Formal models for negotiation using dynamic logic. In C. Sierra and F. Dignum, editors, This book. Springer Verlag, June 2000.

Some Understandings about Forming Coalitions

A precondition of forming coalitions is that there is a way to distribute the utility and pay off among the coalition members.

Generally thinking the aim of forming a coalition is to gain more social utility. However, for a self-interested agent, it decided to form or join a coalition if and only if the coalition can maximized its utility. A self-interested agent doesn't care about the amount of social utility.

However, is it that all ways to increase the utilities among a group of agents can be seen as forming coalitions.

For example, there are two agents i and j. i wants a good C and j wants a good D. i has the good D and j has the good C. Both agents can maximize their utilities by changing the goods they own. Do i and j form a coalition? I was thinking they do, but now, I think I probably wrong in the way I am thinking it.

The coalition theory is not to concern about how agents cooperate, but it care about the largest value that the coalition can obtain. 


In other words, the concepts of coalition and cooperate are at different levels.

A Review of Zeuthen Strategy

Risk

At step t, agent i decides not to make a concession. He will take a risk if its opponent does not make a concession as well and they will run into a conflict.

Rosenschein & Zlotkin provided a way to measure the risk:

They also described it as:

Risk(i,t) = (utility agent 1 loses by conceding and accepting agent 2's offer) / 

                 (utility agent 1 loses by not conceding and causing a conflict)

We can see from the risk function that the more concession you make, the more risk you take. 

Zeuthen Strategy


Zeuthen Strategy proposes to balance the risks of agents in negotiation. In each step, the agent with a less risk should make a sufficient concession, until they make an agreement.


A Sufficient Concession is one that change the balance of risk between two agents. The agent which has made the sufficient concession should have higher risk than its opponent.


By using Zeuthen Strategy, agents may make an agreement which can maximal the product of utilities (Nash Product), but not the sum of utilities. (Pareto optimal)




The computationally complexity of Zeuthen Strategy is O(2^n).