Can We Reach Pareto Optimal Outcomes Using Bottom-Up Approaches? | SpringerLink
Skip to main content
Springer Nature Link
Log in

Can We Reach Pareto Optimal Outcomes Using Bottom-Up Approaches?

  • Conference paper
  • First Online:
Conflict Resolution in Decision Making (COREDEMA 2016)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 10238))

Included in the following conference series:

Abstract

Classically, disciplines like negotiation and decision making have focused on reaching Pareto optimal solutions due to its stability and efficiency properties. Despite the fact that many practical and theoretical algorithms have successfully attempted to provide Pareto optimal solutions, they have focused on attempting to reach Pareto Optimality using horizontal approaches, where optimality is calculated taking into account every participant at the same time. Sometimes, this may prove to be a difficult task (e.g., conflict, mistrust, no information sharing, etc.). In this paper, we explore the possibility of achieving Pareto Optimal outcomes in a group by using a bottom-up approach: discovering Pareto optimal outcomes by interacting in subgroups. We analytically show that the set of Pareto optimal outcomes in a group covers the Pareto optimal outcomes within its subgroups. This theoretical finding can be applied in a variety of scenarios such as negotiation teams, multi-party negotiation, and team formation to social recommendation. Additionally, we empirically test the validity and practicality of this proof in a variety of decision making domains and analyze the usability of this proof in practical situations.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The total number is \(min(1000,\left( {\begin{array}{c}m\\ n\end{array}}\right) )\), where m is the total number of available preference profiles and n is the size of the group.

  2. 2.

    Except for the Book domain, where we only have 7 preference profiles.

  3. 3.

    Even non-linear functions may look like linear when the number of points is reduced.

  4. 4.

    Again, the total number is \(min(1000,\left( {\begin{array}{c}m\\ n\end{array}}\right) )\).

  5. 5.

    http://www.imdb.com. Visited on 16th November 2015.

  6. 6.

    http://www.goodreads.com/. Visited on 16th November 2015.

References

  1. Amador, S., Okamoto, S., Zivan, R.: Dynamic multi-agent task allocation with spatial and temporal constraints. In: Proceedings of the International Conference on Autonomous Agents and Multi-agent Systems, pp. 1495–1496. International Foundation for Autonomous Agents and Multiagent Systems (2014)

    Google Scholar 

  2. Anagnostopoulos, A., Becchetti, L., Castillo, C., Gionis, A., Leonardi, S.: Online team formation in social networks. In: Proceedings of the 21st International Conference on World Wide Web, pp. 839–848. ACM (2012)

    Google Scholar 

  3. Argente, E., Botti, V., Carrascosa, C., Giret, A., Julian, V., Rebollo, M.: An abstract architecture for virtual organizations: the thomas approach. Knowl. Inf. Syst. 29(2), 379–403 (2011)

    Article  Google Scholar 

  4. Aydoğan, R., Hindriks, K.V., Jonker, C.M.: Multilateral mediated negotiation protocols with feedback. In: Marsa-Maestre, I., Lopez-Carmona, M.A., Ito, T., Zhang, M., Bai, Q., Fujita, K. (eds.) Novel Insights in Agent-based Complex Automated Negotiation. SCI, vol. 535, pp. 43–59. Springer, Tokyo (2014). doi:10.1007/978-4-431-54758-7_3

    Chapter  Google Scholar 

  5. Bogomolnaia, A., Moulin, H.: Size versus fairness in the assignment problem. Games Econ. Behav. 90, 119–127 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  6. Brandt, F., Conitzer, V., Endriss, U.: Computational social choice. In: Multiagent system, pp. 213–283 (2012)

    Google Scholar 

  7. Corne, D.W., Knowles, J.D.: Techniques for highly multiobjective optimisation: some nondominated points are better than others. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO 2007, pp. 773–780. ACM, New York (2007)

    Google Scholar 

  8. Jonge, D., Sierra, C.: NB\(^{3}\): a multilateral negotiation algorithm for large, non-linear agreement spaces with limited time. Auton. Agents Multi-agent Syst. 29(5), 896–942 (2015)

    Article  Google Scholar 

  9. Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Merelo, J.J., Schwefel, H.-P. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 849–858. Springer, Heidelberg (2000). doi:10.1007/3-540-45356-3_83

    Chapter  Google Scholar 

  10. di Pierro, F.: Many-objective evolutionary algorithms and applications to water resources engineering. Ph.D. thesis, University of Exeter (2006)

    Google Scholar 

  11. Esparcia, S., Sanchez-Anguix, V., Aydoğan, R.: A negotiation approach for energy-aware room allocation systems. In: Corchado, J.M., et al. (eds.) Highlights on Practical Applications of Agents and Multi-Agent Systems, vol. 365, pp. 280–291. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  12. García-Segarra, J., Ginés-Vilar, M.: The impossibility of paretian monotonic solutions: a strengthening of Roths result. Oper. Res. Lett. 43(5), 476–478 (2015)

    Article  MathSciNet  Google Scholar 

  13. Hara, K., Ito, T.: A mediation mechanism for automated negotiating agents whose utility changes over time. In: Twenty-Seventh AAAI Conference on Artificial Intelligence (2013)

    Google Scholar 

  14. Heiskanen, P., Ehtamo, H., Hämäläinen, R.P.: Constraint proposal method for computing pareto solutions in multi-party negotiations. Eur. J. Oper. Res. 133(1), 44–61 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hewitt, C.: Open information systems semantics for distributed artificial intelligence. Artif. Intell. 47(1–3), 79–106 (1991)

    Article  MathSciNet  Google Scholar 

  16. Horn, J., Nafpliotis, N., Goldberg, D.E.: A niched pareto genetic algorithm for multiobjective optimization. In: Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, pp. 82–87. IEEE (1994)

    Google Scholar 

  17. Xiao-Bing, H., Wang, M., Di Paolo, E.: Calculating complete and exact pareto front for multiobjective optimization: a new deterministic approach for discrete problems. IEEE Trans. Cybern. 43(3), 1088–1101 (2013)

    Article  Google Scholar 

  18. Kamishima, T.: Nantonac collaborative filtering: recommendation based on order responses. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 583–588. ACM (2003)

    Google Scholar 

  19. Kash, I., Procaccia, A.D., Shah, N.: No agent left behind: dynamic fair division of multiple resources. J. Artif. Intell. Res. 51, 579–603 (2014)

    MathSciNet  MATH  Google Scholar 

  20. Lai, G., Li, C., Sycara, K.: Efficient multi-attribute negotiation with incomplete information. Group Decis. Negot. 15(5), 511–528 (2006)

    Article  Google Scholar 

  21. Li, H., Zhang, Q.: Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans. Evol. Comput. 13(2), 284–302 (2009)

    Article  Google Scholar 

  22. Lin, R., Kraus, S., Baarslag, T., Tykhonov, D., Hindriks, K., Jonker, C.M.: Genius: an integrated environment for supporting the design of generic automated negotiators. Comput. Intell. 30(1), 48–70 (2014)

    Article  MathSciNet  Google Scholar 

  23. Marsa-Maestre, I., Klein, M., Jonker, C.M., Aydoğan, R.: From problems to protocols: towards a negotiation handbook. Decis. Support Syst. 60, 39–54 (2014)

    Article  Google Scholar 

  24. Masthoff, J.: Group recommender systems: combining individual models. In: Ricci, F., Rokach, L., Shapira, B., Kantor, P.B. (eds.) Recommender Systems Handbook, pp. 677–702. Springer, USA (2011)

    Chapter  Google Scholar 

  25. Miller, B.N., Albert, I., Lam, S.K., Konstan, J.A., Riedl, J.: Movielens unplugged: experiences with an occasionally connected recommender system. In: Proceedings of the 8th International Conference on Intelligent User Interfaces, pp. 263–266. ACM (2003)

    Google Scholar 

  26. O’Neill, B.: The number of outcomes in the pareto-optimal set of discrete bargaining games. Math. Oper. Res. 6(4), 571–578 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  27. Rahwan, I., Larson, K.: Pareto optimality in abstract argumentation. In: AAAI, pp. 150–155 (2008)

    Google Scholar 

  28. Sanchez-Anguix, V., Dai, T., Semnani-Azad, Z., Sycara, K., Botti, V.: Modeling power distance and individualism/collectivism in negotiation team dynamics. In: 45 Hawaii International Conference on System Sciences (HICSS-45), pp. 628–637 (2012)

    Google Scholar 

  29. Sanchez-Anguix, V., Julian, V., Botti, V., Garcia-Fornes, A.: Reaching unanimous agreements within agent-based negotiation teams with linear and monotonic utility functions. IEEE Trans. Syst. Man Cybern. Part B 42(3), 778–792 (2012)

    Article  Google Scholar 

  30. Sanchez-Anguix, V., Julian, V., Botti, V., Garcia-Fornes, A.: Studying the impact of negotiation environments on negotiation teams’ performance. Inf. Sci. 219, 17–40 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  31. Sanchez-Anguix, V., Aydoğan, R., Julian, V., Jonker, C.: Unanimously acceptable agreements for negotiation teams in unpredictable domains. Electr. Commer. Res. Appl. 13(4), 243–265 (2014)

    Article  Google Scholar 

  32. Sanchez-Anguix, V., Espinosa, A., Hernandez, L., Garcia-Fornes, A.: MAMSY: a management tool for multi-agent systems. In: Demazeau, Y., Pavón, J., Corchado, J.M., Bajo, J. (eds.) 7th International Conference on Practical Applications of Agents and Multi-agent Systems (PAAMS), vol. 55, pp. 130–139. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  33. Sanchez-Anguix, V., Julian, V., Botti, V., García-Fornes, A.: Tasks for agent-based negotiation teams: analysis, review, and challenges. Eng. Appl. Artif. Intell. 26(10), 2480–2494 (2013)

    Article  MATH  Google Scholar 

  34. Sánchez-Anguix, V., Valero, S., Julián, V., Botti, V., García-Fornes, A.: Evolutionary-aided negotiation model for bilateral bargaining in ambient intelligence domains with complex utility functions. Inf. Sci. 222, 25–46 (2013)

    Article  Google Scholar 

  35. Sarwar, B.M., Karypis, G., Konstan, J., Riedl, J.: Recommender systems for large-scale e-commerce: scalable neighborhood formation using clustering. In: Proceedings of the fifth International Conference on Computer and Information Technology, vol. 1. Citeseer (2002)

    Google Scholar 

  36. Skowron, P., Faliszewski, P., Slinko, A.: Achieving fully proportional representation is easy in practice. In: Proceedings of the International Conference on Autonomous Agents and Multi-agent Systems, pp. 399–406. International Foundation for Autonomous Agents and Multiagent Systems (2013)

    Google Scholar 

  37. Zhenh, R., Chakraborty, N., Dai, T., Sycara, K.: Automated multilateral negotiation on multiple issues with private information. INFORMS J. Comput. 28(4), 612–628 (2015)

    MathSciNet  MATH  Google Scholar 

  38. Ziegler, C.-N., McNee, S.M., Konstan, J.A., Lausen, G.: Improving recommendation lists through topic diversification. In: Proceedings of the 14th International Conference on World Wide Web, pp. 22–32. ACM (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Coventry University, Coventry, UK

    Victor Sanchez-Anguix

  2. Özyeğin University, Istanbul, Turkey

    Reyhan Aydoğan

  3. Centrum Wiskunde and Informatica, Amsterdam, Netherlands

    Tim Baarslag

  4. Technical University of Delft, Delft, Netherlands

    Reyhan Aydoğan & Catholijn M. Jonker

Authors
  1. Victor Sanchez-Anguix
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Reyhan Aydoğan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tim Baarslag
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Catholijn M. Jonker
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Victor Sanchez-Anguix .

Editor information

Editors and Affiliations

  1. Özyeğin University, Istanbul, Turkey

    Reyhan Aydoğan

  2. Centrum Wiskunde and Informatica (CWI), Amsterdam, The Netherlands

    Tim Baarslag

  3. University of Southampton, Southampton, United Kingdom

    Enrico Gerding

  4. Interactive Intelligence, Delft University of Technology, Delft, Zuid-Holland, The Netherlands

    Catholijn M. Jonker

  5. Department of Computer Systems and Computation, Technical University of Valencia, Valencia, Spain

    Vicente Julian

  6. Coventry University, West Midlands, United Kingdom

    Victor Sanchez-Anguix

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Sanchez-Anguix, V., Aydoğan, R., Baarslag, T., Jonker, C.M. (2017). Can We Reach Pareto Optimal Outcomes Using Bottom-Up Approaches?. In: Aydoğan, R., Baarslag, T., Gerding, E., Jonker, C., Julian, V., Sanchez-Anguix, V. (eds) Conflict Resolution in Decision Making. COREDEMA 2016. Lecture Notes in Computer Science(), vol 10238. Springer, Cham. https://doi.org/10.1007/978-3-319-57285-7_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-57285-7_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-57284-0

  • Online ISBN: 978-3-319-57285-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics