Dependence Networks for Agreement Technologies? Guido Boella1 , Patrice Caire2 , Leendert van der Torre2 , and Serena Villata3 1 Department of Computer Science, University of Torino, Italy guido@di.unito.it 2 SnT and CSC, University of Luxembourg, Luxembourg patrice.caire@uni.lu,leon.vandertorre@uni.lu 3 INRIA Sophia Antipolis, France serena.villata@inria.fr Abstract. We introduce an abstract framework of dependence networks for the organization layer in the agreement technologies tower, and we illustrate it using an example from social networks. 1 Abstract dependence networks for the organisation layer Dependence networks [2] represent power relations, where the power of agent A over B is represented by the dependence of B on A. Here, we associate with dependencies only abstract reasons, such as goals. We propose to associate sets of proposals for agreements with dependence networks, where proposals are sets of dependencies. Consider the sit- Abstract Dependence Network Proposal Abstract Dependence Network Proposal a r₃ r₁ d c d c r r r₁ r₂ a r₁ b a b b (a) (b) (c) Abstract Dependence Network Abstract Dependence Network Admissible Preferred Proposal 3 Proposal 3 Admissible Proposal 1 Admissible Proposal 2 Proposal 1 Proposal 2 a a r₁ r₁ ' r₅ r₁ r₁ r₆ a c b b r₇ r₂ d b c r₄ ' r₂ (d) (e) Fig. 1: Abstract dependence network (a), proposal of a free gift (b), redundant pro- posal (c), non-redundant proposal (d), and preferred proposal (e) uation where Bob could give Alice a present, and Alice could pick up their children. This can be formalized by the abstract dependence network N = hS, R, Di (Figure ? AT2012, 15-16 October 2012, Dubrovnik, Croatia. Copyright held by the author(s). 1.a), where the set of stakeholders S = {a, b, c, d} represents Alice, Bob, Cathy and Dan, and the set of reasons R = {r, r1 , r2 , r3 , r4 , r5 , r6 , r7 , r8 }, with r : get a gift, {r1 }: pick up the kids at school, {r2 }: get professional referrals, {r3 }: buy computer equipment, {r4 }: pay for computer, {r5 }: get best price on next computer, {r6 }: get new clients, {r7 }: design book covers, and {r8 }: get use-cases for lectures; and the set of de- pendencies D = {(a, b, r), (b, a, r1 )}. Two examples of proposals are P = {(a, b, r)} (Figure 1.b), and P 0 = D = {(a, b, r), (b, a, r1 )} (Figure 1.a). A proposal is exchange based if every dependency is part of a cycle [1]. Consider the case where Bob gives Alice a present without getting anything in return (Figure 1.b): this is not a exchange- based proposal as the dependency is not reciprocated. In contrast, (Figure 1.a), there is a cycle C = h(a, b, r), (b, a, r1 )i. P is not exchange based, but P 0 is. An important property is the notion of redundancy. Consider a scenario in which neither Alice nor Bob could pick up their children. They would not consult with each other. Bob would ask Dan to pick the children up, while Alice would ask Cathy. As a result, both Cathy and Dan would find themselves in front of the school to pick up Alice and Bob’s children. Of course, this is inconvenient and a waste of time for Cathy and Dan. Though such situations may occur in practice due to lack of coordination, it makes less sense to propose this agreement. We model this scenario in Figure 1.c. There is one cycle C = h(a, c, r1 ), (c, b, r2 ), (b, d, r1 ), (d, a, r3 )i: two distinct stakeholders, namely a and b, depend on two distinct stakeholders, namely c and d, for the same reason r1 . The two dependencies can be part of the same proposal, but not a good proposal: a pro- posal is redundant if there are two distinct producers for the same reason. Consider the case where both Alice and Bob ask Cathy to pick up their children, while Cathy depends on Bob to get professional referrals, and on Alice, to design her next book cover (Fig- ure 1.d). This represents that stakeholder c can produce something which is consumed by both a and b, namely, to pick up the children. Proposals P1 = {(a, c, r1 ), (c, a, r7 )}, P2 = {(b, c, r1 ), (c, b, r2 )}, and P3 = {(a, c, r1 ), (c, a, r7 ), (b, c, r1 ), (c, b, r2 )} are non-redundant, whereas proposal P = {(a, c, r1 ), (c, b, r2 ), (b, d, r1 ), (d, a, r3 )} (Fig- ure 1.c) is redundant as there are two distinct producers for the same reason. A proposal is admissible if it is non-redundant, and every dependency is part of a cycle. We may define a preferred proposal as a proposal that obtains the maximal exchange, i.e., a maximal w.r.t. set inclusion admissible proposal. Consider two new stakeholders, such that Betty depends on her husband Alex to pick up their child at school, while Alex depends on Cathy to get new clients, and Cathy depends on Betty to get professional referrals (Figure1.e) where S = {a, b, d, a0 , b0 , c}, namely Alice, Bob, Dan, Alex, Betty and Cathy. Both cycles C1 and C2 , respectively proposals 1 and 2 (Figure1.e) are admissible proposals as they are non-redundant and exchange-based. The proposal C1 ∪ C2 is the unique preferred proposal containing both cycles. References 1. L. Sauro. Formalizing Admissibility Criteria in Coalition Formation among Goal Directed Agents. PhD thesis, University of Torino, 2006. 2. J. S. Sichman and R. Conte. Multi-agent dependence by dependence graphs. In Proc. of AAMAS, pages 483–490, 2002.