Just read 'Time-Quality Tradeoffs in Reallocative Negotiation with Combinatorial Contract Types' (1999) by Martin Andersson and Tuomas Sandholm following on from reading [46] yesterday. Some thoughts:
Nice discussion of distributed reallocative negotiation "versus" (centralized) (combinatorial) auctions at the end of page 1 continuing on page 2.
Multiagent Travelling Salesman Problem (page 2). Interesting.
The contracting system between agents ("contract sequencing") described on pages 4 and 5 is in essence an exhaustive search. Naturally, slow and cumbersome. Multi-agent dialogues and interest-based negotiation could perhaps play a role here. Also, no "algorithm" (contracting system) provided for OCSM-contracts, or even, contracts of mixed/different types.
I like the presentation of the results, i.e. comparing the different contract types in terms of (i) the outcomes (solution quality in terms of social welfare) reached, and (ii) the number of contracts tried and performed before an (local) optimum is reached.
Tuesday, 30 December 2008
Monday, 29 December 2008
Decentralized multiagent contracts
"Decentralized multiagent contracts can be implemented for example by circulating the contract message among the parties and agreeing that the contract becomes valid if every agent signs." ('Contract Types for Satisficing Task Allocation: I Theoretical Results' (1998) by T. W. Sandholm)
Alternatively to passing the contract around, something else to try: an agent noticing that a multiagent contract is necessary could broadcast a proposal of the multiagent contract to all prospective agents and if all agents agree, then the initiating agent could broadcast a confirmation to the recipients sealing the contract.
Alternatively to passing the contract around, something else to try: an agent noticing that a multiagent contract is necessary could broadcast a proposal of the multiagent contract to all prospective agents and if all agents agree, then the initiating agent could broadcast a confirmation to the recipients sealing the contract.
46, Contract Types for Satisficing Task Allocation: I Theoretical Results
Classification of contract types below taken from 'Contract Types for Satisficing Task Allocation: I Theoretical Results' (1998) by Tuoumas W. Sandholm. Very very important/related paper to keep referring back to. Will need to realise the OCSM-contract to achieve completeness in my work.
O-contract: one task given by an agent i to an agent j (+ contract price i pays to j for handling the task set).
C-contract: a cluster (more than 1) of tasks given by an agent i to an agent j (+ contract price i pays to j for handling the task set).
S-contract: swaps of tasks where agent i subcontracts a (single) task to agent j and vice-versa (+ amount i pays to j and amount j pays to i).
M-contract: A multi-agent contract involving at least three agents, wherein each agent involved gives away a single resource to another agent (+ payment).
Each contract type above is necessary (and avoids some of the local optima that the other three do not) but is not sufficient in and of itself for reaching the global optimum via "individually rational" contracts.
OCSM-contract: combines/merges characteristics of the above contract types into one contract type - where the ideas of the above four contract types can be applied simultaneously (atomically).
O-contract: one task given by an agent i to an agent j (+ contract price i pays to j for handling the task set).
C-contract: a cluster (more than 1) of tasks given by an agent i to an agent j (+ contract price i pays to j for handling the task set).
S-contract: swaps of tasks where agent i subcontracts a (single) task to agent j and vice-versa (+ amount i pays to j and amount j pays to i).
M-contract: A multi-agent contract involving at least three agents, wherein each agent involved gives away a single resource to another agent (+ payment).
Each contract type above is necessary (and avoids some of the local optima that the other three do not) but is not sufficient in and of itself for reaching the global optimum via "individually rational" contracts.
OCSM-contract: combines/merges characteristics of the above contract types into one contract type - where the ideas of the above four contract types can be applied simultaneously (atomically).
Sunday, 28 December 2008
44, Towards Interest-Based Negotiation
Goal Arguments (which justify agents' adoption of certain goals) in the paper 'Towards Interest-Based Negotiation' (TIBN) by Iyad Rahwan et al take the form ((SuperG,B,SubG):G), i.e. an agent adopts (intends) a goal (G) because it believes G is instrumental to achieve its supergoal (SuperG), believes the context (B) which justifies G to be true and believes the plan (SubG) for achieving G to be achievable.
We identify here a few forms of attacks allowed (in TIBN) on these Goal Arguments for which we have equivalents in our multi-agent setting of 'On the Benefits of Argumentation for Negotiation' (OBAN).
(1)
- Attack in TIBN: For a Goal Argument ((SuperG,B,SubG):G), show ¬b where b is a belief in B, i.e. disqualifying a context condition.
- Similar attack in OBAN: Agent Y argues "I do not have resource R", where "you have resource R" is a belief agent X has (& utters) as part of either requesting R from Y or requesting R2 from Y. In the latter case, X's prior argument would be: "Y does not need R2 because Y has R (which alone is sufficient for fulfilling Y's goal)".
(2)
- Attack in TIBN: For a Goal Argument ((SuperG,B,SubG):G), show ¬p where p is a goal in SubG, i.e. a subgoal is unachievable.
- Similar attack in OBAN: Agent Y argues "I need to retain resource R (and hence your (sub)goal of obtaining R is unachievable)", where R is a resource agent X requests from Y.
(3)
- Attack: For a Goal Argument ((SuperG,B,SubG):R), show set of goals P such that achieve(P,G) where G is a goal in SuperG and R is not a goal in P, i.e. there is an alternative plan P which achieves the supergoal G and does not include R.
- Similar attacks in OBAN (in the case where R is a resource ("goal" in the language of TIBN) agent X requests from agent Y):
--- X argues "you do not need resource R (since you have a resource R2 that alone is sufficient for fulfilling your supergoal G)".
--- X argues "you do not need resource R (since I have a resource R2 that alone is sufficient for fulfilling your supergoal G and I will exchange with you R2 for R)".
We identify here a few forms of attacks allowed (in TIBN) on these Goal Arguments for which we have equivalents in our multi-agent setting of 'On the Benefits of Argumentation for Negotiation' (OBAN).
(1)
- Attack in TIBN: For a Goal Argument ((SuperG,B,SubG):G), show ¬b where b is a belief in B, i.e. disqualifying a context condition.
- Similar attack in OBAN: Agent Y argues "I do not have resource R", where "you have resource R" is a belief agent X has (& utters) as part of either requesting R from Y or requesting R2 from Y. In the latter case, X's prior argument would be: "Y does not need R2 because Y has R (which alone is sufficient for fulfilling Y's goal)".
(2)
- Attack in TIBN: For a Goal Argument ((SuperG,B,SubG):G), show ¬p where p is a goal in SubG, i.e. a subgoal is unachievable.
- Similar attack in OBAN: Agent Y argues "I need to retain resource R (and hence your (sub)goal of obtaining R is unachievable)", where R is a resource agent X requests from Y.
(3)
- Attack: For a Goal Argument ((SuperG,B,SubG):R), show set of goals P such that achieve(P,G) where G is a goal in SuperG and R is not a goal in P, i.e. there is an alternative plan P which achieves the supergoal G and does not include R.
- Similar attacks in OBAN (in the case where R is a resource ("goal" in the language of TIBN) agent X requests from agent Y):
--- X argues "you do not need resource R (since you have a resource R2 that alone is sufficient for fulfilling your supergoal G)".
--- X argues "you do not need resource R (since I have a resource R2 that alone is sufficient for fulfilling your supergoal G and I will exchange with you R2 for R)".
Friday, 26 December 2008
45, Mass argumentation and the semantic web
This paper ('Mass argumentation and the semantic web' by Iyad Rahwan) contains some useful links (footnotes 1-5 & 9) and a very useful background (Sections 1 and 2). The rest of the paper is not really (directly) related to my research though.
Content of the paper: "Argumentation theory - a crash course", "Arguing on today's web", "Arguing on the semantic web", "An infrastructure for unified semantic argument annotation".
Content of the paper: "Argumentation theory - a crash course", "Arguing on today's web", "Arguing on the semantic web", "An infrastructure for unified semantic argument annotation".
Monday, 22 December 2008
44, Towards Interest-Based Negotiation
Some thoughts following on from reading 'Towards Interest-Based Negotiation' (2003) by Iyad Rahwan et al with my aamas-submitted (not accepted) paper in mind:
The paper contains some nice ideas about goal selection which would (/could!) be useful in a (larger) context of multi-agent negotiation (/resource allocation) and in building a generative model (as I intend), but the work here leaves much unspecified and is not generative in and of itself. What is presented in Section 5 ("Dialogues about Goals") is a protocol. No policy or strategy is defined. This is left for future work. I will read the authors' newer paper ('An Empirical Study of Interest-Based Negotiation') to see if this is done and also any other related (later papers) by the authors.
In addition, the framework deals with agent systems consisting of two agents only.
Content of the paper: "Arguing about goals vs Arguing about beliefs", "Agents and goal support" (goals and beliefs/subgoals/supergoals/roles/adoption), "How to attack a goal" (attacking beliefs/subgoals/supergoals), "Dialogues about goals".
"Goal arguments" are presented to be of the form (H:G), where H is the triple support (SuperGoal,Beliefs,SubGoals) for G.
An interesting question, identified as outside the scope of this paper, is: How does an agent, given a top-level goal, generate (from the various options) the set of (sub-) goals to achieve? Suggested approaches: consider the costs of adopting different plans as well as the utilities of the goals achieved, or, identify the goal(s) with the strongest support.
The paper contains some nice ideas about goal selection which would (/could!) be useful in a (larger) context of multi-agent negotiation (/resource allocation) and in building a generative model (as I intend), but the work here leaves much unspecified and is not generative in and of itself. What is presented in Section 5 ("Dialogues about Goals") is a protocol. No policy or strategy is defined. This is left for future work. I will read the authors' newer paper ('An Empirical Study of Interest-Based Negotiation') to see if this is done and also any other related (later papers) by the authors.
In addition, the framework deals with agent systems consisting of two agents only.
Content of the paper: "Arguing about goals vs Arguing about beliefs", "Agents and goal support" (goals and beliefs/subgoals/supergoals/roles/adoption), "How to attack a goal" (attacking beliefs/subgoals/supergoals), "Dialogues about goals".
"Goal arguments" are presented to be of the form (H:G), where H is the triple support (SuperGoal,Beliefs,SubGoals) for G.
An interesting question, identified as outside the scope of this paper, is: How does an agent, given a top-level goal, generate (from the various options) the set of (sub-) goals to achieve? Suggested approaches: consider the costs of adopting different plans as well as the utilities of the goals achieved, or, identify the goal(s) with the strongest support.
27, On the Benefits of Exploiting Hierarchical Goals in Bilateral Automated Negotiation
Some thoughts following on from re-reading 'On the Benefits of Exploiting Hierarchical Goals in Bilateral Automated Negotiation' (2007) by Iyad Rahwan et al with my aamas-submitted (not accepted) paper in mind:
- What is presented is a protocol and not a generative model as such.
- The negotiation framework consists of (/is limited to) two agents.
- Agents' preferences over (sets of) resources is specified as a (pre-given) numerical utility function. "Deals" between agents (to reallocate resources) make use of "side payments" based on this utility function.
- The relationship "sub" (linking a goal to "sub" -goals and/or -resources needed to achieve it) seems shared between all agents (though agents have no prior knowledge of each other's main goals or preferences).
- Much in this paper rests on the existence/allowance of "partial plans" (wherein leaf nodes may be goals as well as resources) and the setting of positive interaction between agents' "shared"/"common" goals such that an agent may benefit from a common goal (or sub-goal) achieved by the other agent.
Subscribe to:
Posts (Atom)