Selecting Partners, Agents 2000

학회: Agents

년도: 2000

저자: Bikramjit Banerjee, Sandip Sen

1. Introduction

이기적인 agent의 목적은 자신의 local utility를 최대로 만들어 주는 agent와 협력하는 것이다. 이 논문에서는 다른 agent와 협력해서 받는 utility에 대해 다룬다.

어떤 이와 같이 협동을 할 때 받을 utility 값들이 확률들로 주어짐

얼마만큼의 횟수로 협동을 할 지 알 경우 누구와 협동하는게 좋을 지 알아봄

2. Coalition Formation

(1) searching for optimal coalition structure

어떻게 revenue의 합이 최대가 되게 그룹화할건가

(2) decision mechanisms for forming coalitions

어떤 coalition에 들어갈 건가

(3) payoff division in a coalition

어떻게 나눌 것인가

여기서는 위에 3개 안다룸

3. Payoff-structures of partnerships

{(u1,p1),(u2,p2).....}

payoff와 payoff를 받을 확률의 pair의 tuple로 되어 있음. payoff의 종류는 partnership에 따라 다름

4. selecting the potentially most beneficial partnership for limited interactions

두 partner가 있고 각 파트너는 유틸리티의 값의 확률분포를 갖음. 두 partnership끼리 묶어서 비교함. 여러 partneship가 있을 때 가장 많이 남들보다 좋은 경우가 있는 partnership을 고름

어떤 partner랑 정해진 횟수안에 협력을 했을 때 더 이익인지를 확률적으로 계산함

(모든 가능한 경우에 대한 평균으로 구함)

A 개의 partnership, N번의 interaction, n은 전체 partnership 중 최대 payoff 갯수

시간 복잡도는 O(A^2*N^2n) A^2는 각 partnership끼리 비교에서 나옴

각 확률의 합이 1이하일 수 잇는데 이는 같은 경우가 있을 수 있어서임

 

5. Comparative evaluation with a decision mechanism for infinite interactions

Expected Utility Maximization Principle(MEU): utility 평균이 가장 큰 것 선택, 무한대로 interact할 경우 보장

그러나 실제로는 무한대로 interact못함. interact가 짧을 경우 평균이 더 낮은게 더 높은 utility를 줄 수 있음.

 

(1) 무한대로 가면 MEU형태로 바뀜

(2) payoff-structure와 interaction 횟수에 기반함

 

6. Evaluation scenario

broker: 선택하는 자

service-provider, recipient: 협력하는 자

 

7. Experimental results

MEU-partnership: 평균을 조금 높이고 최대가 나올 확률을 줄임

non-MEU-partnership: 고정

MEU 방식으로 위 두개를 비교, non-MEU 방식으로 위 두개를 비교

objective function S의 output이 한번 이상 바뀜. 이는 payoff의 분포와 multinomial coefficients, decomposition-pattern of number of interaction에 따라 영향을 받는다.

MEU를 선택하는 것이 interaction이 많아질수록 많아진다. 숫자가 커질 경우 MEU 선택 방식이 더 좋다.

MEU partner의 최대 utility가 높아지면 더 자주 선택된다. 평균이 잘 발생하지 않는 최대 utility에 기반하면 그 잘 발생하지 않는 utility를 선택하기 위해 더 선택된다.

짧은 N 구간에서 빈번한 변화. 평균값 차이가 작고 최대값이 낮아서.

 

8. Conclusion

probability-theory based procedure for making the selection을 제안하고 MEU principle과 비교

payoff -structure가 부정확할 경우의 문제가 있을 수 있다.