Coalitions of Arguments : An Approach with Constraint Programming

• Autorzy: Bistarelli S. , Santini F.
• Języki publikacji: EN

Abstrakty

EN

The aggregation of generic items into coalitions leads to the creation of sets of homogenous entities. In this paper we accomplish this for an input set of arguments, and the result is a partition according to distinct lines of thought, i.e., groups of 'coherent' ideas. We extend Dung's Argumentation Framework (AF) in order to deal with coalitions of arguments. The initial set of arguments is partitioned into not-intersected subsets. All the found coalitions show the same property inherited by Dung, e.g., all the coalitions in the partition are admissible (or conflict-free, complete, stable): they are generated according to Dung's principles. Each of these coalitions can be assigned to a different agent. We use Soft Constraint Programming as a formal approach to model and solve such partitions in weighted AFs: semiring algebraic structures can be used to model different optimization criteria for the obtained coalitions. Moreover, we implement and solve the presented problem with JaCoP, a Java constraint solver, and we test the code over a small-world network.

Słowa kluczowe

EN

constraint programming; coalition; semirings (mathematics); ordered algebraic structures; mathematical optimization; mathematical models

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 124, nr 4
• Strony: 383--401
• Opis fizyczny: Bibliogr. 29 poz., wykr.

Twórcy

autor

Bistarelli S.

• Dipartimento di Matematica e Informatica, Universita ` di Perugia, Perugia, Italy

autor

Santini F.

• Dipartimento di Matematica e Informatica, Universita ` di Perugia, Perugia, Italy

Bibliografia

• [1] Amgoud, L.: An Argumentation-Based Model for Reasoning About Coalition Structures, ArgMAS05, 4049, Springer, 2005, ISBN 3-540-36355-6.
• [2] Amgoud, L., Prade, H.: Using arguments for making and explaining decisions, Artif. Intell., 173(3-4), 2009, 413-436.
• [3] Apt, K. R., Witzel, A.: A Generic Approach to Coalition Formation, CoRR, abs/0709.0435, 2007.
• [4] Besnard, P., Doutre, S.: Checking the acceptability of a set of arguments, Workshop on Non-Monotonic Reasoning, 2004.
• [5] Bistarelli, S.: Semirings for Soft Constraint Solving and Programming, vol. 2962 of LNCS, Springer, 2004, ISBN 3-540-21181-0.
• [6] Bistarelli, S., Campli, P., Santini, F.: Finding partitions of arguments with Dung’s properties via SCSPs, SAC (W. C. Chu, W. E. Wong, M. J. Palakal, C.-C. Hung, Eds.), ACM, 2011, ISBN 978-1-4503-0113-8.
• [7] Bistarelli, S., Foley, S., O’Sullivan, B., Santini, F.: Semiring-based frameworks for trust propagation in small-world networks and coalition formation criteria, Security and Communication Networks, 3(6), 2010, 595-610, ISSN 1939-0122.
• [8] Bistarelli, S., Martinelli, F., Santini, F.: A Semantic Foundation for Trust Management Languages with Weights: An Application to the RT Family, Autonomic and Trusted Computing, 5th International Conference, 5060, Springer, 2008.
• [9] Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based Constraint Solving and Optimization, Journal of the ACM, 44(2), March 1997, 201-236.
• [10] Bistarelli, S., Pini, M. S., Rossi, F., Venable, K. B.: From soft constraints to bipolar preferences: modelling framework and solving issues, J. Exp. Theor. Artif. Intell., 22(2), 2010, 135-158.
• [11] Bistarelli, S., Santini, F.: A Common Computational Framework for Semiring-based Argumentation Systems, ECAI'10, 215, IOS Press, 2010, ISBN 978-1-60750-605-8.
• [12] Bistarelli, S., Santini, F.: ConArg: A Constraint-Based Computational Framework for Argumentation Systems, ICTAI, IEEE, 2011, ISBN 978-1-4577-2068-0.
• [13] Bistarelli, S., Santini, F.: Modeling and Solving AFs with a Constraint-Based Tool: ConArg, TAFA (S. Mod- gil, N. Oren, F. Toni, Eds.), 7132, Springer, 2011, ISBN 978-3-642-29183-8.
• [14] Boella, G., van der Torre, L., Villata, S.: Social Viewpoints for Arguing about Coalitions, PRIMA, 5357, Springer, 2008.
• [15] Bogart, K. P.: Introductory Combinatorics, Academic Press, Inc., Orlando, FL, USA, 2000, ISBN 0121108309.
• [16] Brewka, G., Woltran, S.: Abstract Dialectical Frameworks, KR (F. Lin, U. Sattler, M. Truszczynski, Eds.), AAAI Press, 2010.
• [17] Bulling, N., Dix, J.: Modelling and Verifying Coalitions using Argumentation and ATL, Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial, 14(46), 2010, 45-73.
• [18] Cayrol, C., Lagasquie-Schiex, M.-C.: Coalitions of arguments: A tool for handling bipolar argumentation frameworks, Int. J. Intell. Syst., 25(1), January 2010, 83-109, ISSN 0884-8173.
• [19] da Costa Pereira, C., Tettamanzi, A., Villata, S.: Changing Ones Mind: Erase or Rewind?, IJCAI (T. Walsh, Ed.), IJCAI/AAAI, 2011, ISBN 978-1-57735-516-8.
• [20] Dung, P. M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell., 77(2), 1995, 321-357, ISSN 0004-3702.
• [21] Dunne, P. E., Hunter, A., McBurney, P., Parsons, S., Wooldridge, M.: Weighted argument systems: Basic definitions, algorithms, and complexity results, Artif. Intell., 175(2), 2011, 457-486.
• [22] Harvey, W. D., Ginsberg, M. L.: Limited Discrepancy Search, IJCAI (1), 1995.
• [23] Horling, B., Lesser, V.: A survey of multi-agent organizational paradigms, Knowl. Eng. Rev., 19(4), 2004, 281-316, ISSN 0269-8889.
• [24] Kleinberg, J.: Navigation in a Small World, Nature, 406, 2000, 845, ISSN 0269-8889.
• [25] Matt, P.-A., Toni, F.: A Game-Theoretic Measure of Argument Strength for Abstract Argumentation, Proceedings of the 11th European conference on Logics in Artificial Intelligence, JELIA ’08, Springer-Verlag, Berlin, Heidelberg, 2008, ISBN 978-3-540-87802-5.
• [26] Ohta, N., Conitzer, V., Ichimura, R., Sakurai, Y., Iwasaki, A., Yokoo, M.: Coalition Structure Generation Utilizing Compact Characteristic Function Representations, CP, 5732, Springer, 2009.
• [27] O’Madadhain, J., Fisher, D., White, S., Boey, Y.: The JUNG (Java Universal Network/Graph) framework, Technical report, UC Irvine, 2003.
• [28] Rossi, F., van Beek, P., Walsh, T.: Handbook of Constraint Programming, Elsevier Science Inc., NY, USA, 2006, ISBN 0444527265.
• [29] Shehory, O., Kraus, S.: Task Allocation Via Coalition Formation Among Autonomous Agents, IJCAI (1), 1995.