IJCAI 2018 Tutorial

Argumentation Meets Computational Social Choice
Dorothea Baumeister, Daniel Neugebauer, and Jörg Rothe
Heinrich-Heine-Universität Düsseldorf, Germany
{baumeister, neugebauer, rothe}@cs.uni-duesseldorf.de

 

This tutorial presents recent trends in abstract argumentation, focusing on gradual acceptance in and aggregation of abstract argumentation frameworks. Regarding the former, we highlight the technical properties and the expressive potential of gradual measures of acceptance, called ranking semantics, in abstract argumentation. We give an overview of specific recent proposals for ranking semantics, and discuss possibilities for comparison and axiomatic analysis of different ranking semantics. Regarding the latter, we take the point of view of computational social choice and apply its approach to the argumentation setting: When a group of agents takes part in an argumentation, the goal is to aggregate the individual agents' subjective views on the debate so as to reflect the joint view of the group as a whole. Even if they individually may disagree on the arguments and attack relations involved, there may well be a consensus about certain semantic properties, and we give an overview of which of them can be preserved under aggregation, using techniques from computational social choice.

Relatedly, we consider abstract argumentation frameworks when there is uncertainty about either the arguments or the attacks or both, and while uncertainty may be differently perceived by individual agents, the resulting incomplete argumentation frameworks can be merged in various ways to reflect the joint view of all agents. In particular, we survey recent complexity results on variants of the verification problem in incomplete argumentation frameworks for a variety of semantics introduced by Dung [1995]. Next, we turn to a possible extension of his model: value-based argumentation frameworks. In the audience-specific model, there is a label for each argument and some preference relation over the labels. An argumentation framework together with a preference relation may then be used to model an agent's individual view, where the defeat of an argument does not only depend on the attack relation but also on the individual preferences over labels. We survey recent results on the question of whether several such subjective views on the set of arguments can be rationalized, i.e., whether there is some argumentation framework together with an order over the labels such that the defeat relations of all single agents can be rationally explained. Finally, we conclude by discussing these recent trends in abstract argumentation, and we propose to apply aggregation methods to a wider range, including gradual and ranking semantics.


Speakers' Biographies:

Dorothea Baumeister is working in computational social choice, algorithmics, and complexity theory since 2007. In particular, she is an expert for judgment aggregation, fair division, and multiwinner elections. She has published eight papers in TCS and AI journals (including JAAMAS, Information & Computation, SCW, and MSS) and 19 papers in TCS and AI conferences (including IJCAI, AAMAS, and ECAI). Her complete list of publications can be found on her homepage or at dblp. She is a founding member of the Düsseldorf Institute for Internet and Democracy (DIID).

Daniel Neugebauer is a Ph.D. student at the graduate school "Online Participation" of HHU Düsseldorf since December 2014 and works in argumentation theory. In particular, he has published papers at AAAI and ADT. His publication list can be found here or at dblp.

Jörg Rothe is working in complexity theory and, in particular, in computational social choice since more than 20 years; his first paper in the latter field pinpoints the complexity of determining winners in Dodgson elections [Hemaspaandra et al., 1997]. Since then he has published 59 papers in TCS and AI journals (including one in AIJ, one in JACM, two in JAIR, four in JAAMAS, four in JCSS, one in SIAM Journal on Computing, three in Information & Computation, one in SCW, seven in TCS, etc.) and 81 papers in TCS and AI conferences (including two in IJCAI, five in AAAI, 15 in AAMAS, eight in ECAI, one in ICALP, two in COCOON, two in TARK, etc.). He also works in algorithmic game theory and fair division and, since 2014, in argumentation theory. His complete list of publications can be found on his homepage or at dblp. With two DAAD fellowships, he was a visiting scholar (1993/94) and a visiting assistant professor (1997/98) at the University of Rochester, USA, and as a visiting professor he spent his 2004 and 2009 sabbaticals there and in 2013 at Stanford University, USA. In 2000, he received a Heisenberg Fellowship from Deutsche Forschungsgemeinschaft (DFG). Since 2014, he serves as the chair of the Department of Computer Science at Heinrich-Heine-Universität Düsseldorf. He is an associate editor of Journal of Artificial Intelligence Research (JAIR), an editorial board member of Mathematical Logic Quarterly (MLQ), of the Journal of Universal Computer Science (J.UCS), and of the Mathematical Programming Glossary of the INFORMS Computing Society, a founding member of the Düsseldorf Institute for Internet and Democracy (DIID), and from 2009 through 2014 he was a founding advisory board member of the Centre for Mathematical Social Science at University of Auckland, New Zealand.


Outline of the Tutorial:

  • Introduction to Argumentation and to Computational Social Choice
  • Preservation of Semantic Properties
    • Aggregation Rules and Axioms
    • Which Semantic Properties Can Be Preserved?
  • Verifying Semantics in Incomplete AFs
    • Possible and Necessary Verification
    • Possible and Necessary Verification
  • Gradual Acceptance in Argumentation
    • An Overview of Gradual and Ranking Semantics
    • Axiomatic Analysis of Gradual Semantics
  • Rationalization
    • Single Agents
    • Multiple Agents
    • Rationalizability under Expansion Semantics
  • Discussion and Outlook

Slides for the IJCAI 2018 Tutorial:

Tutorial Bibliography:

  • [Airiau et al., 2017] S. Airiau, E. Bonzon, U. Endriss, N. Maudet, and J. Rossit. Rationalisation of Profiles of Abstract Argumentation Frameworks: Characterisation and Complexity. Journal of Artificial Intelligence Research, 60:149-177, 2017.
  • [Amgoud and Ben-Naim, 2013] L. Amgoud and J. Ben-Naim. Ranking-Based Semantics for Argumentation Frameworks. In Proceedings of the 7th International Conference on Scalable Uncertainty Management, pages 134-147. Springer-Verlag Lecture Notes in Artificial Intelligence #8078, September 2013.
  • [Amgoud and Ben-Naim, 2016] L. Amgoud and J. Ben-Naim. Axiomatic Foundations of Acceptability Semantics. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, pages 2-11. AAAI Press, April 2016.
  • [Baumeister et al., 2015a] D. Baumeister, D. Neugebauer, and J. Rothe. Verification in Attack-Incomplete Argumentation Frameworks. In Proceedings of the 4th International Conference on Algorithmic Decision Theory, pages 341-358. Springer-Verlag Lecture Notes in Artificial Intelligence #9346, September 2015.
  • [Baumeister et al., 2015b] D. Baumeister, J. Rothe, and H. Schadrack. Verification in Argument-Incomplete Argumentation Frameworks. In Proceedings of the 4th International Conference on Algorithmic Decision Theory, pages 359-376. Springer-Verlag Lecture Notes in Artificial Intelligence #9346, September 2015.
  • [Baumeister et al., 2018] D. Baumeister, D. Neugebauer, J. Rothe, and H. Schadrack. Complexity of Verification in Incomplete Argumentation Frameworks. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. AAAI Press, February 2018.
  • [Besnard and Hunter, 2001] P. Besnard and A. Hunter. A Logic-Based Theory of Deductive Arguments. Artificial Intelligence, 128(1):203-235, 2001.
  • [Bonzon et al., 2016a] E. Bonzon, J. Delobelle, S. Konieczny, and N. Maudet. A Comparative Study of Ranking-based Semantics for Abstract Argumentation. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, pages 914-920. AAAI Press, February 2016.
  • [Bonzon et al., 2016b] E. Bonzon, J. Delobelle, S. Konieczny, and N. Maudet. Argumentation Ranking Semantics based on Propagation. In Proceedings of the 6th International Conference on Computational Models of Argument, pages 139-150. IOS Press, September 2016.
  • [Brandt et al., 2016] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.
  • [Cayrol and Lagasquie-Schiex, 2005] C. Cayrol and M. Lagasquie-Schiex. Graduality in Argumentation. Journal of Artificial Intelligence Research, 23:245-297, 2005.
  • [Chen and Endriss, 2017] W. Chen and U. Endriss. Preservation of Semantic Properties during the Aggregation of Abstract Argumentation Frameworks. In Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge, pages 118-129. arXiv:1707.08740 [cs.AI], EPTCS 251, 2017.
  • [Coste-Marquis et al., 2007] S. Coste-Marquis, C. Devred, S. Konieczny, M. Lagasquie-Schiex, and P. Marquis. On the Merging of Dung's Argumentation Systems. Artificial Intelligence, 171(10):730-753, 2007.
  • [Delobelle et al., 2015] J. Delobelle, S. Konieczny, and S. Vesic. On the Aggregation of Argumentation Frameworks. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 2911-2917. AAAI Press/IJCAI, July 2015.
  • [Dietrich and List, 2007] F. Dietrich and C. List. Judgment Aggregation by Quota Rules: Majority Voting Generalized. Journal of Theoretical Politics, 19(4):391-424, 2007.
  • [Dimopoulos and Torres, 1996] Y. Dimopoulos and A. Torres. Graph Theoretical Structures In Logic Programs and Default Theories. Theoretical Computer Science, 170(1):209-244, 1996.
  • [Dung, 1995] P. Dung. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence, 77(2):321-357, 1995.
  • [Dunne et al., 2012] P. Dunne, P. Marquis, and M. Wooldridge. Argument Aggregation: Basic Axioms and Complexity Results. In Proceedings of the 4th International Conference on Computational Models of Argument, volume 245, pages 129-140. IOS Press, September 2012.
  • [Endriss and Grandi, 2017] U. Endriss and U. Grandi. Graph Aggregation. Artificial Intelligence, 245:86-114, 2017.
  • [Grossi and Modgil, 2015] D. Grossi and S. Modgil. On the Graded Acceptability of Arguments. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 868-874. AAAI Press/IJCAI, July 2015.
  • [Hunter and Thimm, 2017] A. Hunter and M. Thimm. Probabilistic Reasoning with Abstract Argumentation Frameworks. Journal of Artificial Intelligence Research, 59:565-611, 2017.
  • [Jakobovits and Vermeir, 1999] H. Jakobovits and D. Vermeir. Robust Semantics for Argumentation Frameworks. Journal of Logic and Computation, 9(2):215-261, 1999.
  • [Kim et al., 2013] E. Kim, S. Ordyniak, and S. Szeider. The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation. In Proceedings of the 2nd International Workshop on Theory and Applications of Formal Argumentation, pages 158-175. Springer-Verlag Lecture Notes in Artificial Intelligence #8306, 2013.
  • [Matt and Toni, 2008] P. Matt and F. Toni. A Game-Theoretic Measure of Argument Strength for Abstract Argumentation. In Proceedings of the 11th European Conference on Logics in Artificial Intelligence, pages 285-297. Springer-Verlag Lecture Notes in Artificial Intelligence #5293, September 2008.
  • [Pu et al., 2014] F. Pu, J. Luo, Y. Zhang, and G. Luo. Argument Ranking with Categoriser Function. In Proceedings of the 7th International Conference on Knowledge Science, Engineering and Management, pages 290-301. Springer-Verlag Lecture Notes in Artificial Intelligence #8793, October 2014.
  • [Pu et al., 2015] F. Pu, J. Luo, Y. Zhang, and G. Luo. Attacker and Defender Counting Approach for Abstract Argumentation. In Proceedings of the 37th Annual Meeting of the Cognitive Science Society, pages 1913-1918. Cognitive Science Society, July 2015.
  • [Rothe, 2015] J. Rothe, editor. Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer, 2015.
  • [Santini, 2016] F. Santini. Graded Justification of Arguments via Internal and External Endogenous Features. In Proceedings of the 10th International Conference on Scalable Uncertainty Management, pages 352-359. Springer-Verlag Lecture Notes in Artificial Intelligence #9858, September 2016.
  • [Thimm, 2012] M. Thimm. A Probabilistic Semantics for Abstract Argumentation. In Proceedings of the 20th European Conference on Artificial Intelligence, pages 750-755. IOS Press, August 2012.
  • [Tohmé et al., 2008] F. Tohmé, G. Bodanza, and G. Simari. Aggregation of Attack Relations: A Social-Choice Theoretical Analysis of Defeasibility Criteria. In Proceedings of the 5th International Symposium on Foundations of Information and Knowledge Systems, pages 8-23. Springer-Verlag Lecture Notes in Artificial Intelligence #4932, February 2008.
  • [Wu et al., 2010] Y. Wu, M. Caminada, and M. Podlaszewski. A Labelling-Based Justification Status of Arguments. Studies in Logic, 3(4):12-29, 2010.