ݺߣ

ݺߣShare a Scribd company logo

Many to Many Matching of Agents with Nonlinear Utility Function

?Download as PPTX, PDF?
?
Shun Okuhara
Shun Okuhara

The document proposes a negotiation matching protocol for agents with nonlinear utility functions. It involves the following steps: 1) Agents search for local optimal solutions in their nonlinear utility spaces using simulated annealing. 2) Agents generate bids representing high utility agreements and submit them to a mediator. 3) The mediator checks for overlaps between the bid sets to find successful matchings that maximize social utility. Experimental results showed the proposed method approximated optimal solutions and social welfare increased with more bids. Future work involves validating effectiveness for larger-scale matching problems.

1 of 15
Download to read offline
Many to Many Matching of Agents with Nonlinear Utility Function Nagoya institute of technology Takayuki Ito, Moustafa laboratory QIAO SENSEN, Takayuki Ito, Ahmed Moustafa, Shun Okuhara (Many to Many Matching of Agents with Nonlinear Utility Function)
Introduction Many to many matching problem The result of negotiation between two agent sets is the problem of finding the best combination. Many to many negotiation problem has many applications in the real world. ?Matching application finds the best pair of men and women. ?Transportation problems optimize how much product is shipped from a factory to a store. ?Negotiations conducted by people are also matching of offers proposed by buyers and sellers from their respective utility spaces. Fig.1 many to many matching of Sellers and Buyers Existing studies do not consider the interdependence of issues. Seller Buyer Buyer Seller Buyer Buyer 1
Multi-issues negotiation problem Negotiations are an important social activity for conflict resolution and consensus building for mutual benefit multi-issue negotiation problem :It is a negotiation problem with multiple issues. C Independent issue: Utility can be expressed as a linear function. C Interdependence issues: Utility can be expressed by a non-linear function that requires multi-objective optimization Utility function using constraint expression C Constraints express the range of utility for each issue [1] Non-linear utility space C The utility space using the constraint expression becomes an uneven nonlinear space. [1] Hiromitsu HATTORI, Takayuki ITO, and Mark KLEIN and M. Klein, An Auction-Based Negotiation Protocol for Agents with Nonlinear Utility Functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J89-D, No. 12, pp.2648-2660, 2006(in Japanese). 0 20 40 60 80 100 Isuue Isuue2 Practical negotiation matching needs to consider complex dependencies between issues. Utility 2 Fig.2 Non-linear utility space
research object Task (Issue) ? Given the complex utility space, it is very difficult to find the best combination in many-to-many negotiation matching. Proposed method ? The agent presents preferences (bid) to a mediator and the mediator finds an agreement combination that maximizes social utility. Proposal of negotiation matching protocol based on complex utility space 3
Related research Particle Swarm Optimization and Kernel Density Estimator in Concurrent Negotiations Kostas et al. [2] study a simultaneous negotiation of one buyer and multiple sellers. The buyer and the seller aim to reach an agreement by repeating the proposal and response based on the proposal response protocol. In this paper, particle swarm optimization is used to search for the optimal solution. Buyers method is to change the negotiation strategy for each seller based on the optimal solution. The above research assumes independence between issues but does not consider complex utility spaces. [2]Kostas Kolomvatsos, Stathes Hadjiefthymiades. On the Use of Particle Swarm Optimization and Kernel Density Estimator in Concurrent Negotiations[J]. Information Sciences 262.November 2013. Offer Offer Offer seller 1 seller 2 seller 3 buyer N N N Fig.Negotiation using particle swarm optimization. Negotiation matching method that assumes realistic and complicated utility space is required 4
Proposed method |Proposal of negotiation matching protocol based on mediator ? Mediator accepts bids and matches efficiently. Agent d Agent c Agent a Agent b Group A Group B mediator as bid cs bid bs bid ds bid Fig4Many to Many matching 5
Approach Matching process agent A agent B agent C agent D agent a agent b agent c agent d The mediator calculates the negotiation result of all pairs for each agent bid. A B C D a 50 40 X 60 b 60 X X 20 c 80 110 20 50 d 90 X 60 70 For example ?Agent A and Agent a can negotiate and agree to get 50 social benefits ?Agent B and Agent b cannot agree . 6 Fig5Matching Fig6 Utility value in the matrix
Approachstep1 Searching local optimal solution by SA Searching by Simulated Annealing (SA) [step1] Agents explore local optimal solutions in their nonlinear utility spaces by SA. ContractsUtility local optimum solution [1] Hiromitsu HATTORI, Takayuki ITO, and Mark KLEIN and M. Klein, An Auction-Based Negotiation Protocol for Agents with Nonlinear Utility Functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J89-D, No. 12, pp.2648-2660, 2006(in Japanese). 7 Fig7 Search high utility point
Approachstep2 Generating bids The agent calculates the utility value, which is the total utility of the constraints satisfied by the agreement. [step2] The mediator set the number of bids. The agent selects bids with a high utility value and submit it to the mediator. ?? s = ? ? ?, ??(??) ??(??, ?) s : agreement ?? Utility ? ? constraint ?(??)A set of consensus proposals that can satisfy constraint ? ? ??(??, ?)Utility value when constraint ? ? is satisfied by agreement s [1] Hiromitsu HATTORI, Takayuki ITO, and Mark KLEIN and M. Klein, An Auction-Based Negotiation Protocol for Agents with Nonlinear Utility Functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J89-D, No. 12, pp.2648-2660, 2006(in Japanese). Contracts Utility 1 43 2 8 Fig8 Draft agreements
Approachstep3 Deciding consensus [step3] ? Each agent submits a set of bids. ? The mediator checks the overlap between the bid sets, and if there is an overlap, the matching is successful. ? For every pair, the mediator check the overlap and store its utility value in the matrix. Fig9 Consensus decision Contracts UtilityUtility Agent Agent A B C D a 50 40 X 60 b 60 X X 20 c 80 110 20 50 d 90 X 60 70 9 Fig.10 : Sample of utility value in the matrix
Overview of evaluation experiment Experimental settings The constraint is generated as follows (Issue 1, Issue 2, Issue 3) = ([3,6], [2,9], [3,8]) The constraints are single constraints, binary constraints, triple constraints ... Agent_num 4, 6,8,10,12,14,16 Issue_num 3,4 Issue_value_num [ 0, 9] Constraints_num 10 Bids_num [ 0, 100 ] Table 1: Parameter values 10
Result Experimental results with 3 issues The Social welfare is increasing with the increase in the number of bids, and the common part of the value of the issue can be searched. 0 1000 2000 3000 4000 5000 6000 7000 8000 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 Relationship between number of agent and social welfare agent_num_4 agent_num_6 agent_num_8 agent_num_10 agent_num_12 agent_num_14 agent_num_16 Number of bids: Number of bids submitted by one agent Socialwelfare 11
Result 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 10 20 30 40 50 60 70 80 90 Relationship between the number of agents and social utility agent_num_4 agent_num_6 agent_num_8 agent_num_10 agent_num_12 agent_num_14 agent_num_16 Experimental results with 4 issues Social utility increases as the number of bids increases. It is difficult to agree with a small number of issues. Number of bids Socialwelfare 12
Experimental result Results of comparison between the proposed method and full search 3 issues: Approximate solution of optimal solution can be obtained. 4 issues: Utility value has decreased significantly. It is difficult to agree with a small number of bids 0 500 1000 1500 2000 2500 3000 3500 4000 0 10 20 30 40 50 60 70 80 90 Average utility ALL_average_utility SA_average_utility 0 500 1000 1500 2000 2500 0 10 20 30 40 50 60 70 80 90 Average utility ALL_average_utility SA_average_utility Comparison result of issue 3 Comparison result of issue 4 Number of bids Socialwelfare Number of bids Socialwelfare 13
Conclusion Proposed method ? Explored local optimal solution in nonlinear utility space by SA ? Set a mediator between each agent to search for a matching combination that maximizes social utility. Evaluation experiment results ? It is possible to omit some of the information required for bidding to be disclosed to mediators. ? The effectiveness of the proposed method is presented experimentally. Future work ? Experiment that the proposed method is effective for larger-scale matching problem is essential. Proposed Matching Protocol with Non-linear Utility Function by Mediator 14

More Related Content

Many to Many Matching of Agents with Nonlinear Utility Function

  • 1. Many to Many Matching of Agents with Nonlinear Utility Function Nagoya institute of technology Takayuki Ito, Moustafa laboratory QIAO SENSEN, Takayuki Ito, Ahmed Moustafa, Shun Okuhara (Many to Many Matching of Agents with Nonlinear Utility Function)
  • 2. Introduction Many to many matching problem The result of negotiation between two agent sets is the problem of finding the best combination. Many to many negotiation problem has many applications in the real world. ?Matching application finds the best pair of men and women. ?Transportation problems optimize how much product is shipped from a factory to a store. ?Negotiations conducted by people are also matching of offers proposed by buyers and sellers from their respective utility spaces. Fig.1 many to many matching of Sellers and Buyers Existing studies do not consider the interdependence of issues. Seller Buyer Buyer Seller Buyer Buyer 1
  • 3. Multi-issues negotiation problem Negotiations are an important social activity for conflict resolution and consensus building for mutual benefit multi-issue negotiation problem :It is a negotiation problem with multiple issues. C Independent issue: Utility can be expressed as a linear function. C Interdependence issues: Utility can be expressed by a non-linear function that requires multi-objective optimization Utility function using constraint expression C Constraints express the range of utility for each issue [1] Non-linear utility space C The utility space using the constraint expression becomes an uneven nonlinear space. [1] Hiromitsu HATTORI, Takayuki ITO, and Mark KLEIN and M. Klein, An Auction-Based Negotiation Protocol for Agents with Nonlinear Utility Functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J89-D, No. 12, pp.2648-2660, 2006(in Japanese). 0 20 40 60 80 100 Isuue Isuue2 Practical negotiation matching needs to consider complex dependencies between issues. Utility 2 Fig.2 Non-linear utility space
  • 4. research object Task (Issue) ? Given the complex utility space, it is very difficult to find the best combination in many-to-many negotiation matching. Proposed method ? The agent presents preferences (bid) to a mediator and the mediator finds an agreement combination that maximizes social utility. Proposal of negotiation matching protocol based on complex utility space 3
  • 5. Related research Particle Swarm Optimization and Kernel Density Estimator in Concurrent Negotiations Kostas et al. [2] study a simultaneous negotiation of one buyer and multiple sellers. The buyer and the seller aim to reach an agreement by repeating the proposal and response based on the proposal response protocol. In this paper, particle swarm optimization is used to search for the optimal solution. Buyers method is to change the negotiation strategy for each seller based on the optimal solution. The above research assumes independence between issues but does not consider complex utility spaces. [2]Kostas Kolomvatsos, Stathes Hadjiefthymiades. On the Use of Particle Swarm Optimization and Kernel Density Estimator in Concurrent Negotiations[J]. Information Sciences 262.November 2013. Offer Offer Offer seller 1 seller 2 seller 3 buyer N N N Fig.Negotiation using particle swarm optimization. Negotiation matching method that assumes realistic and complicated utility space is required 4
  • 6. Proposed method |Proposal of negotiation matching protocol based on mediator ? Mediator accepts bids and matches efficiently. Agent d Agent c Agent a Agent b Group A Group B mediator as bid cs bid bs bid ds bid Fig4Many to Many matching 5
  • 7. Approach Matching process agent A agent B agent C agent D agent a agent b agent c agent d The mediator calculates the negotiation result of all pairs for each agent bid. A B C D a 50 40 X 60 b 60 X X 20 c 80 110 20 50 d 90 X 60 70 For example ?Agent A and Agent a can negotiate and agree to get 50 social benefits ?Agent B and Agent b cannot agree . 6 Fig5Matching Fig6 Utility value in the matrix
  • 8. Approachstep1 Searching local optimal solution by SA Searching by Simulated Annealing (SA) [step1] Agents explore local optimal solutions in their nonlinear utility spaces by SA. ContractsUtility local optimum solution [1] Hiromitsu HATTORI, Takayuki ITO, and Mark KLEIN and M. Klein, An Auction-Based Negotiation Protocol for Agents with Nonlinear Utility Functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J89-D, No. 12, pp.2648-2660, 2006(in Japanese). 7 Fig7 Search high utility point
  • 9. Approachstep2 Generating bids The agent calculates the utility value, which is the total utility of the constraints satisfied by the agreement. [step2] The mediator set the number of bids. The agent selects bids with a high utility value and submit it to the mediator. ?? s = ? ? ?, ??(??) ??(??, ?) s : agreement ?? Utility ? ? constraint ?(??)A set of consensus proposals that can satisfy constraint ? ? ??(??, ?)Utility value when constraint ? ? is satisfied by agreement s [1] Hiromitsu HATTORI, Takayuki ITO, and Mark KLEIN and M. Klein, An Auction-Based Negotiation Protocol for Agents with Nonlinear Utility Functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J89-D, No. 12, pp.2648-2660, 2006(in Japanese). Contracts Utility 1 43 2 8 Fig8 Draft agreements
  • 10. Approachstep3 Deciding consensus [step3] ? Each agent submits a set of bids. ? The mediator checks the overlap between the bid sets, and if there is an overlap, the matching is successful. ? For every pair, the mediator check the overlap and store its utility value in the matrix. Fig9 Consensus decision Contracts UtilityUtility Agent Agent A B C D a 50 40 X 60 b 60 X X 20 c 80 110 20 50 d 90 X 60 70 9 Fig.10 : Sample of utility value in the matrix
  • 11. Overview of evaluation experiment Experimental settings The constraint is generated as follows (Issue 1, Issue 2, Issue 3) = ([3,6], [2,9], [3,8]) The constraints are single constraints, binary constraints, triple constraints ... Agent_num 4, 6,8,10,12,14,16 Issue_num 3,4 Issue_value_num [ 0, 9] Constraints_num 10 Bids_num [ 0, 100 ] Table 1: Parameter values 10
  • 12. Result Experimental results with 3 issues The Social welfare is increasing with the increase in the number of bids, and the common part of the value of the issue can be searched. 0 1000 2000 3000 4000 5000 6000 7000 8000 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 Relationship between number of agent and social welfare agent_num_4 agent_num_6 agent_num_8 agent_num_10 agent_num_12 agent_num_14 agent_num_16 Number of bids: Number of bids submitted by one agent Socialwelfare 11
  • 13. Result 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 10 20 30 40 50 60 70 80 90 Relationship between the number of agents and social utility agent_num_4 agent_num_6 agent_num_8 agent_num_10 agent_num_12 agent_num_14 agent_num_16 Experimental results with 4 issues Social utility increases as the number of bids increases. It is difficult to agree with a small number of issues. Number of bids Socialwelfare 12
  • 14. Experimental result Results of comparison between the proposed method and full search 3 issues: Approximate solution of optimal solution can be obtained. 4 issues: Utility value has decreased significantly. It is difficult to agree with a small number of bids 0 500 1000 1500 2000 2500 3000 3500 4000 0 10 20 30 40 50 60 70 80 90 Average utility ALL_average_utility SA_average_utility 0 500 1000 1500 2000 2500 0 10 20 30 40 50 60 70 80 90 Average utility ALL_average_utility SA_average_utility Comparison result of issue 3 Comparison result of issue 4 Number of bids Socialwelfare Number of bids Socialwelfare 13
  • 15. Conclusion Proposed method ? Explored local optimal solution in nonlinear utility space by SA ? Set a mediator between each agent to search for a matching combination that maximizes social utility. Evaluation experiment results ? It is possible to omit some of the information required for bidding to be disclosed to mediators. ? The effectiveness of the proposed method is presented experimentally. Future work ? Experiment that the proposed method is effective for larger-scale matching problem is essential. Proposed Matching Protocol with Non-linear Utility Function by Mediator 14

Editor's Notes

  • #2: Hello, everyone. It is a great honor to be able to speak to you today. Let me introduce myself first. My name is Shun Okuhara and I am Asistant Prof. in Nagoya Institute of Technology. Today Id like to talk about Matching program for Nonlinear Utility
  • #3: gˤ϶यζνh}ڤޤоǤϡĤΥ`ȼϤνhYMߺϤ碌̽}ࡩཻhޥå󥰆}ȺӤޤ СˤФνh}I֤}Ӥ֤΄ÿg᰸offerνhޥå󥰤Ǥ ȴоǤϡhޥå󥰤ˤơ}Փ㆖}QäƤޤयоǤϥץՓgƤȁƤޤՓg˴ڤ໥vS򿼑]Ƥޤ
  • #4: hȤ໥Τ˸ϽQȺγɤФҪЄӤǤ hˤυgһՓQ}䡢}ՓQ}ꡢоǤ}Փ㆖}ĿƤޤ }Փ㆖}Ǥ϶ՓՓg໥vS֤ģĤ˷֤뤳ȤǤޤ Փϡ`Ȥ΄äΤvȤƱF뤳ȤǤvS֤ՓόgˤƶयڤĿmҪǾΤvDZF뤳ȤǤޤ оǤƼsFävՓgvSFޤƼsȤϸՓvƄää빠FǤ СՓ1[6, 8]Փ2[5,7]ιǺ⤬ä줿ϤƼsܤǤ꣬һ΄ääȤȤǤ Ƽsयڤȣ˱褦ʰ͹ΤǾΤ΄ÿgǤޤΤ褦ʄÿg?ϣयƼsܤʵصǤτÂ?ߤʤ꣬˳㤹Ƽs?٤ʤص?ϣä?ͤʤޤ 2 : 40
  • #5: оǤϣg˽}ˤmäǤՓͬʿvSڤ뽻h}עĿ}jʄÿg˻Ťhޥå󥰥ץȥ᰸ޤ n}ϡ}jʄÿgǰȤơνhޥå󥰤MߺϤ碌̽ΤϡӋȤƷdzyʵǤ ᰸ַϡǥ`O`Ȥ뤳Ȥǡǥ`ᄿäˤޥå󥰤νMߺϤ碌ҊĤ뷽Ǥ 3 :
  • #6: kostasϣˤI֤}ΉӤ֤ĤƷ}ՓˤĤͬrhФо򤷤Ƥޤ I֤ȉӤ֤᰸ץȥȤ᰸ȏR귵ȤˤĿָޤ I֤ȺmmofferҊĤoffer˻ŤǽhԤ{Ƥץȥ᰸Ƥޤ ˤνhץȥ϶ՓȁϤǤϣͬrhˤƄʤ褯γɤǤ^gǤϡ ՓgvS֤ĽhयvS򿼑]Ǥ¤ޥå󥰥ץȥ뤬ҪǤ˼ޤ 4 :
  • #7: оǤϥǥ`˻Ťޥå󥰥ץȥ᰸ޤ ᰸ޥå󥰤χ˱褦ˣĤΥ`פ˷֤졢줾Υ`פ}Υ`Ȥڤޤ `פg˥ǥ`Oޤǥ`Ϥ줾Υ`ȤܤȡꡢǤڥҊĤ ؤ߸2ޥå󥰤ФĄäȤʤޥå󥰤νMߺϤ碌򤵤ޤ 5 :
  • #8: ᰸ַǤϡ`Ȥ}Фޤ ĤΥ`ȤgǡؤʤϤ㤬ȿޤ ˤ넿äκͤζĤΥ`ȤĄäǤ ǥ``ȤϡҤΤ褦ˡȫƤΥڥνhYȤƤĄäΥޥȥåޤ СAgent A Agent aϡǤ50Ąä뤳Ȥζޤ ޤAgent B Agent bϺǤƤʤȤޤʤμϤؤʤ꤬ʤȤζǤ ޥȥåȫƤΥڥĄä᤿顢󣲲ޥå󥰥르ꥺʹʵĤ˽MߺϤ碌̽ޤ gYǤϡʥ󥯥쥹ηˤäơgH˥ޥå󥰤Ƥޤ
  • #9: ᰸ַhƤޤоǤϷΥ`ᥫ˥˻Ťhץȥ򒈏ޥå󥰥ץȥȤƏäޤ ƥåףǤϥ`Ȥϸ΄ÿgˤƥץ󥰤Фץ󥰵Ȥ˥ߥƥåɥ˩`󥰤ǺⰸȤʤm̽ޤ 7 :
  • #10: STEPǤϡ`Ȥϥߥƥåɥ˩`󥰤ǵäܤǤⰸ΄ÂӋ㤷ޤ ÂϺⰸ㤹Ƽs΄äξtͤ뤳ȤǤޤ ⰸ΄ÂӋ㤷ˤτÂθߤ혤O줿λȤɤޤ
  • #11: STEPǤϡ`Ȥɤ줿ǥ``ޤ ǥ`줿Сͨβ֤֤̽ޤ Ĥˤϡ֤Փv낎ιι֤ͨޤ ֤ͨڤʤСνMߺϤ碌ϿԤΤⰸȤʤޤ 8 :
  • #12: оΌgYO˱ޤAgentρIɤΥ`פͬˤʤ똔żOƤޤ ƼsυgƼsƼsƼsɤƤޤ оǤ϶यՓv򜺤Ƽsϣä?ߤʤ. Ƽs򜺤Τ?٤ʤϤϣä?ͤȤʤޤ ȫƤΌgYϣԇФYƽȤäƤޤ
  • #13: Փ򣳤ȤrΥ`ĄävS򥰥դˤޤ kSτÂSʾޤ यʤۤɡ⤷䤹ʤ뤳Ȥ狼ޤ ȫƤΥ`Ǥ뤳Ȥˤ⤹륨`Ȥयʤ ޥå󥰤ޤǤƤĄäӤƤ뤳ȤQǤޤ φ}gޤʮ֤˴󤭤ʤϤǤ᰸ޥå󥰥ץȥ뤬 ֤Փv낎ιι֤ͨ̽ǤƤ뤳ȤhǤޤ
  • #14: ΤՓ򣴤ȤrΥ`ĄävS򥰥դˤޤ ȫƤΥ`vƤͬӤ˰餤ĄäӤƤΤQǤޤ 40¤ΕrϤۤȤɤΥ`Ǻ⤬ǤƤʤȤ狼ޤ ՓһĉȤˤꆖ}`뤬ָĤˉӤơ٤ʤǤϺ⤹Ԥͤ ޥå󥰤ޤǤƤʤhǤޤ
  • #15: ^gYǤՓȣΕr᰸ַȫ̽DŽÿg̽뷽Ȥα^Фޤ kS˄ÂSɫΥդȫ̽ɫ᰸ַǤ ՓΕr᰸ַȫ̽ȱȤ٤ۤȤɤvƄÂβϳޤǤ ᰸ַՓ΄ÿgǤϴ_gm˽ƽ뤳ȤǤ뤳Ȥ狼ޤ ՓΕrǤϣΕrȱȤل˜päƤ뤳Ȥ狼롢󤭤Ǥϥޥå󥰤ǤƤ뤬 СǤϤۤܥޥå󥰤ǤƤʤYȤʤޤϡՓʤꆖ}gΣ\Ȥʤꆖ}`뤬ָĤˉӤÿg̽ʮ֤Τޥå󥰤yˤʤꄿäͤʤähǤޤ
  • #16: This is conclusion of my presentation. ThatAΤǸؤ That brings me to the end of my presentation, thank for your attention. ϤоΤޤȤǤ ꤬Ȥޤ