On the measure of conflicts: Shapley inconsistency values. (English) Zbl 1210.68106
Summary: There are relatively few proposals for inconsistency measures for propositional belief bases. However, inconsistency measures are potentially as important as information measures for artificial intelligence, and more generally for computer science. In particular, they can be useful to define various operators for belief revision, belief merging, and negotiation. The measures that have been proposed so far can be split into two classes. The first class of measures takes into account the number of formulae required to produce an inconsistency: the more formulae required to produce an inconsistency, the less inconsistent the base. The second class takes into account the proportion of the language that is affected by the inconsistency: the more propositional variables affected, the more inconsistent the base. Both approaches are sensible, but there is no proposal for combining them. We address this need in this paper: our proposal takes into account both the number of variables affected by the inconsistency and the distribution of the inconsistency among the formulae of the base. Our idea is to use existing inconsistency measures in order to define a game in coalitional form, and then to use the Shapley value to obtain an inconsistency measure that indicates the responsibility/contribution of each formula to the overall inconsistency in the base. This allows us to provide a more reliable image of the belief base and of the inconsistency in it.
MSC:
| 68T27 | Logic in artificial intelligence |
Keywords:
inconsistency management; inconsistency tolerance; inconsistency measures; conflict resolution; paraconsistency; Shapley valuesReferences:
| [1] | Alchourrón, C.; Gärdenfors, P.; Makinson, D., On the logic of theory change: Partial meet contraction and revision functions, Journal of Symbolic Logic, 50, 510-530 (1985) · Zbl 0578.03011 |
| [2] | (Aumann, R. J.; Hart, S., Handbook of Game Theory with Economic Applications, vol. 3 (2002), North-Holland) · Zbl 0993.90001 |
| [3] | Benferhat, S.; Dubois, D.; Prade, H., Argumentative inference in uncertain and inconsistent knowledge bases, (Proceedings of the International Conference on Uncertainty in Artificial Intelligence (UAI’93) (1993), Morgan Kaufmann), 411-419 |
| [4] | Benferhat, S.; Dubois, D.; Prade, H., Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study, Part 1: The flat case, Studia Logica, 58, 17-45 (1997) · Zbl 0867.68100 |
| [5] | Booth, R.; Meyer, T., Admissible and restrained revision, Journal of Artificial Intelligence Research, 26, 127-151 (2006) · Zbl 1182.68284 |
| [8] | Booth, R., Social contraction and belief negotiation, Information Fusion, 7, 1, 19-34 (2006) |
| [10] | Barragáns-Martínez, B.; Pazos-Arias, J. J.; Fernández-Vilas, A., Merging requirements views with incompleteness and inconsistency, (Proceedings of the IEEE Australian Software Engineering Conference (ASWEC’05) (2005), IEEE Computer Society Press) |
| [12] | Chen, Q.; Zhang, C.; Zhang, S., A verification model for electronic transaction protocols, (Advanced Web Technologies and Applications. Advanced Web Technologies and Applications, LNCS, vol. 3007 (2004), Springer), 824-833 |
| [13] | Delgrande, J.; Dubois, D.; Lang, J., Iterated revision as prioritized merging, (Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasonin (KR’06) (2006), AAAI Press), 210-220 |
| [14] | Dubois, D.; Lang, J.; Prade, H., Possibilistic logic, (Hogger, C.; Gabbay, D.; Robinson, J., Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 3 (1994), Oxford University Press), 439-513 · Zbl 0810.68005 |
| [15] | Darwiche, A.; Pearl, J., On the logic of iterated belief revision, Artificial Intelligence, 89, 1-29 (1997) · Zbl 1018.03012 |
| [16] | Eiter, T.; Gottlob, G., On the complexity of propositional knowledge base revision, updates, and counterfactuals, Artificial Intelligence, 57, 2-3, 227 (1992) · Zbl 0763.68038 |
| [18] | Grant, J.; Hunter, A., Measuring inconsistency in knowledgebases, Journal of Intelligent Information Systems, 27, 159-184 (2006) |
| [21] | Gregoire, E.; Mazure, B.; Piette, C., Using local search to find MSSes and MUSes, European Journal of Operational Research, 199, 3, 640-646 (2009) · Zbl 1176.90410 |
| [22] | Grant, J., Classifications for inconsistent theories, Notre Dame Journal of Formal Logic, 19, 435-444 (1978) · Zbl 0305.02040 |
| [23] | Hansson, S. O., What’s new isn’t always best, Theoria, 63, 1-13 (1998), (Special issue on non-prioritized belief revision) |
| [24] | Hunter, A.; Konieczny, S., Approaches to measuring inconsistent information, (Inconsistency Tolerance. Inconsistency Tolerance, LNCS, vol. 3300 (2005), Springer), 189-234 |
| [26] | Hunter, A.; Liu, W., Knowledge base stratification and merging based on degree of support, (Proceedings of the Tenth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’09). Proceedings of the Tenth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’09), LNCS, vol. 5590 (2009), Springer), 385-395 · Zbl 1245.68194 |
| [27] | Hunter, A., Measuring inconsistency in knowledge via quasi-classical models, (Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI’02) (2002), MIT Press), 68-73 |
| [28] | Hunter, A., Logical comparison of inconsistent perspectives using scoring functions, Knowledge and Information Systems, 6, 5, 528-543 (2004) |
| [29] | Hunter, A., How to act on inconsistent news: Ignore, resolve, or reject, Data and Knowledge Engineering, 57, 221-239 (2006) |
| [30] | Jin, Y.; Thielscher, M., Iterated belief revision, revised, Artificial Intelligence, 171, 1-18 (2007) · Zbl 1168.03318 |
| [31] | Kemeny, J., A logical measure function, Journal of Symbolic Logic, 18, 289-308 (1953) · Zbl 0052.01202 |
| [33] | Konieczny, S.; Lang, J.; Marquis, P., \(DA^2\) merging operators, Artificial Intelligence, 157, 49-79 (2004) · Zbl 1085.68167 |
| [35] | Knight, K. M., Measuring inconsistency, Journal of Philosophical Logic, 31, 77-98 (2002) · Zbl 1003.03022 |
| [36] | Knight, K. M., Two information measures for inconsistent sets, Journal of Logic, Language and Information, 12, 227-248 (2003) · Zbl 1015.03035 |
| [37] | Konieczny, S., Belief base merging as a game, Journal of Applied Non-Classical Logics, 14, 3, 275-294 (2004) · Zbl 1185.68693 |
| [38] | Lehmann, D.; Magidor, M., What does a conditional knowledge base entail?, Artificial Intelligence, 55, 1-60 (1992) · Zbl 0762.68057 |
| [39] | Lozinskii, E., Resolving contradictions: A plausible semantics for inconsistent systems, Journal of Automated Reasoning, 12, 1-31 (1994) · Zbl 0804.68141 |
| [40] | Luce, R. D.; Raiffa, H., Games and Decision (1957), Wiley · Zbl 0084.15704 |
| [42] | Mu, K.; Jin, Z.; Lu, R.; Liu, W., Measuring inconsistency in requirements engineering, (Proceedings of the Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’05). Proceedings of the Eighth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU’05), LNAI, vol. 3571 (2005), Springer), 440-451 · Zbl 1122.68666 |
| [43] | Manor, R.; Rescher, N., On inferences from inconsistent information, Theory and Decision, 1, 179-219 (1970) · Zbl 0212.31103 |
| [44] | Monderer, D.; Samet, D., Variations on the Shapley value, (Handbook of Game Theory with Economic Applications, vol. 3 (2002), North-Holland), 2055-2076 |
| [46] | Paris, J. B., The Uncertain Reasoner’s Companion: A Mathematical Perspective, Cambridge Tracts in Theoretical Computer Science, vol. 39 (1994), Cambridge University Press · Zbl 0838.68104 |
| [48] | Priest, G., Minimally inconsistent LP, Studia Logica, 50, 321-331 (1991) · Zbl 0748.03017 |
| [49] | Reiter, R., A theory of diagnosis from first principles, Artificial Intelligence, 32, 57-95 (1987) · Zbl 0643.68122 |
| [50] | Shapley, L. S., A value for \(n\)-person games, (Kuhn, H. W.; Tucker, A. W., Contributions to the Theory of Games II. Contributions to the Theory of Games II, Annals of Mathematics Studies, vol. 28 (1953), Princeton University Press), 307-317 · Zbl 0050.14404 |
| [51] | Spohn, W., Ordinal conditional functions: A dynamic theory of epistemic states, (Harper, W. L.; Skyrms, B., Causation in Decision, Belief Change, and Statistics, vol. 2 (1987), Princeton University Press), 105-134 |
| [53] | Wong, P.; Besnard, Ph., Paraconsistent reasoning as an analytic tool, Journal of the Interest Group in Propositional Logic, 9, 233-246 (2001) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
