Valued preference-based instantiation of argumentation frameworks with varied strength defeats

A Dung-style argumentation framework aims at representing conflicts among elements called arguments. The basic ingredients of this framework is a set of arguments and a Boolean abstract (i.e., its origin is not known) binary defeat relation. Preference-based argumentation frameworks are instantiations of Dung's framework in which the defeat relation is derived from an attack relation and a preference relation over the arguments. Recently, Dung's framework has been extended in order to consider the strength of the defeat relation, i.e., to quantify the degree to which an argument defeats another argument. In this paper, we instantiate this extended framework by a preference-based argumentation framework with a valued preference relation. As particular cases, the latter can be derived from a weight function over the arguments or a Boolean preference relation. We show under some reasonable conditions that there are “less situations” in which a defense between arguments holds with a valued preference relation compared to a Boolean preference relation. Finally, we provide some conditions that the valued preference relation shall satisfy when it is derived from a weight function.     

Rich preference-based argumentation frameworks

An argumentation framework is seen as a directed graph whose nodes are arguments and arcs are attacks between the arguments. Acceptable sets of arguments, called extensions, are computed using a semantics. Existing semantics are solely based on the attacks and do not take into account other important criteria like the intrinsic strengths of arguments.The contribution of this paper is three fold. First, we study how preferences issued from differences in strengths of arguments can help in argumentation frameworks. We show that they play two distinct and complementary roles: (i) to repair the attack relation between arguments, (ii) to refine the evaluation of arguments. Despite the importance of both roles, only the first one is tackled in existing literature. In a second part of this paper, we start by showing that existing models that repair the attack relation with preferences do not perform well in certain situations and may return counter-intuitive results. We then propose a new abstract and general framework which treats properly both roles of preferences. The third part of this work is devoted to defining a bridge between the argumentation-based and the coherence-based approaches for handling inconsistency in knowledge bases, in particular when priorities between formulae are available. We focus on two well-known models, namely the preferred sub-theories introduced by Brewka and the demo-preferred sets defined by Cayrol, Royer and Saurel. For each of these models, we provide an instantiation of our abstract framework which is in full correspondence with it.     

Optimization of dialectical outcomes in dialogical argumentation

When informal arguments are presented, there may be imprecision in the language used, and so the audience may be uncertain as to the structure of the argument graph as intended by the presenter of the arguments. For a presenter of arguments, it is useful to know the audience's argument graph, but the presenter may be uncertain as to the structure of it. To model the uncertainty as to the structure of the argument graph in situations such as these, we can use probabilistic argument graphs. The set of subgraphs of an argument graph is a sample space. A probability value is assigned to each subgraph such that the sum is 1, thereby reflecting the uncertainty over which is the actual subgraph. We can then determine the probability that a particular set of arguments is included or excluded from an extension according to a particular Dung semantics. We represent and reason with extensions from a graph and from its subgraphs, using a logic of dialectical outcomes that we present. We harness this to define the notion of an argumentation lottery, which can be used by the audience to determine the expected utility of a debate, and can be used by the presenter to decide which arguments to present by choosing those that maximize expected utility. We investigate some of the options for using argumentation lotteries, and provide a computational evaluation.     

Probabilistic qualification of attack in abstract argumentation

An argument graph is a graph where each node denotes an argument, and each arc denotes an attack by one argument on another. It offers a valuable starting point for theoretical analysis of argumentation following the proposals by Dung. However, the definition of an argument graph does not take into account the belief in the attacks. In particular, when constructing an argument graph from informal arguments, where each argument is described in free text, it is often evident that there is uncertainty about whether some of the attacks hold. This might be because there is some expressed doubt that an attack holds or because there is some imprecision in the language used in the arguments. In this paper, we use the set of spanning subgraphs of an argument graph as a sample space. A spanning subgraph contains all the arguments, and a subset of the attacks, of the argument graph. We assign a probability value to each spanning subgraph such that the sum of the assignments is 1. This means we can reflect the uncertainty over which is the actual subgraph using this probability distribution. Using the probability distribution over subgraphs, we can then determine the probability that a set of arguments is admissible or an extension. We can also obtain the probability of an attack relationship in the original argument graph as a marginal distribution (i.e. it is the sum of the probability assigned to each subgraph containing that attack relationship). We investigate some of the features of this proposal, and we consider the utility of our framework for capturing some practical argumentation scenarios.     

Argumentation update in YALLA (Yet Another Logic Language for Argumentation)

This article proposes a complete framework for handling the dynamics of an abstract argumentation system. This frame can encompass several belief bases under the form of several argumentation systems, more precisely it is possible to express and study how an agent who has her own argumentation system can interact on a target argumentation system (that may represent a state of knowledge at a given stage of a debate). The two argumentation systems are defined inside a reference argumentation system called the universe which constitutes a kind of “common language”. This paper establishes three main results. First, we show that change in argumentation in such a framework can be seen as a particular case of belief update. Second, we have introduced a new logical language called YALLA in which the structure of an argumentation system can be encoded, enabling to express all the basic notions of argumentation theory (defense, conflict-freeness, extensions) by formulae of YALLA. Third, due to previous works about dynamics in argumentation we have been in position to provide a set of new properties that are specific for argumentation update.     

Eliminating counterexamples: A Grade 8 student’s learning trajectory for contrapositive proving

This study uses a teaching experiment and retrospective analysis to develop a learning trajectory for improving a Grade 8 student’s ability to construct, critique, and validate contrapositive arguments. The study is predicated on the hypothesis that adolescents perform poorly on contrapositive reasoning tasks because they lack sufficient ways of justifying contrapositive argumentation as a viable mode of argumentation. By studying a student’s actions and comments as she develops, critiques, and validates not-the-conclusion-implies-the-conditions-are-impossible arguments for conditional claims, a promising learning trajectory for contrapositive argumentation is developed. The student’s learning trajectory demonstrates how a conception of contrapositive proving as eliminating counterexamples can be useful in developing, critiquing, and validating contrapositive arguments.     

Traveling salesman problem heuristics: Leading methods, implementations and latest advances

Heuristics for the traveling salesman problem (TSP) have made remarkable advances in recent years. We survey the leading methods and the special components responsible for their successful implementations, together with an experimental analysis of computational tests on a challenging and diverse set of symmetric and asymmetric TSP benchmark problems. The foremost algorithms are represented by two families, deriving from the Lin-Kernighan (LK) method and the stem-and-cycle (S&C) method. We show how these families can be conveniently viewed within a common ejection chain framework which sheds light on their similarities and differences, and gives clues about the nature of potential enhancements to today’s best methods that may provide additional gains in solving large and difficult TSPs.     

A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

Postulates for logic-based argumentation systems

Logic-based argumentation systems are developed for reasoning with inconsistent information. Starting from a knowledge base encoded in a logical language, they define arguments and attacks between them using the consequence operator associated with the language. Finally, a semantics is used for evaluating the arguments.In this paper, we focus on systems that are based on deductive logics and that use Dung's semantics. We investigate rationality postulates that such systems should satisfy. We define five intuitive postulates: consistency and closure under the consequence operator of the underlying logic of the set of conclusions of arguments of each extension, closure under sub-arguments and exhaustiveness of the extensions, and a free precedence postulate ensuring that the free formulas of the knowledge base (i.e., the ones that are not involved in inconsistency) are conclusions of arguments in every extension. We study the links between the postulates and explore conditions under which they are guaranteed or violated.     

Density of stable convex semi-infinite vector optimization problems

In this paper, we show that every convex semi-infinite vector optimization (CSVO for brevity) problem can be arbitrarily approximated by stable CSVO problems, i.e., the set of all stable CSVO problems (the weak solution map is continuous or the solution map is upper semicontinuous) is dense in the set of all CSVO problems with the given topology.     

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

Algorithms for generating arguments and counterarguments in propositional logic

A common assumption for logic-based argumentation is that an argument is a pair 〈Φ,α〉 where Φ is minimal subset of the knowledgebase such that Φ is consistent and Φ entails the claim α. Different logics provide different definitions for consistency and entailment and hence give us different options for formalising arguments and counterarguments. The expressivity of classical propositional logic allows for complicated knowledge to be represented but its computational cost is an issue. In previous work we have proposed addressing this problem using connection graphs and resolution in order to generate arguments for claims that are literals. Here we propose a development of this work to generate arguments for claims that are disjunctive clauses of more than one disjunct, and also to generate counteraguments in the form of canonical undercuts (i.e. arguments that with a claim that is the negation of the conjunction of the support of the argument being undercut).     

Crown reductions for the Minimum Weighted Vertex Cover problem

The paper studies crown reductions for the Minimum Weighted Vertex Cover problem introduced recently in the unweighted case by Fellows et al. [Blow-Ups, Win/Win's and crown rules: some new directions in FPT, in: Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG’03), Lecture notes in computer science, vol. 2880, 2003, pp. 1-12, Kernelization algorithms for the vertex cover problem: theory and experiments, in: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, Louisiana, January 2004, pp. 62-69]. We describe in detail a close relation of crown reductions to Nemhauser and Trotter reductions that are based on the linear programming relaxation of the problem. We introduce and study the so-called strong crown reductions, suitable for finding (or counting) all minimum vertex covers, or finding a minimum vertex cover under some additional constraints. It is described how crown decompositions and strong crown decompositions suitable for such problems can be computed in polynomial time. For weighted König-Egerváry graphs (G,w) we observe that the set of vertices belonging to all minimum vertex covers, and the set of vertices belonging to no minimum vertex covers, can be efficiently computed.Further, for some specific classes of graphs, simple algorithms for the MIN-VC problem with a constant approximation factor r<2 are provided. On the other hand, we conclude that for the regular graphs, or for the Hamiltonian connected graphs, the problem is as hard to approximate as for general graphs.It is demonstrated how the results about strong crown reductions can be used to achieve a linear size problem kernel for some related vertex cover problems.     

Evaluation of nondominated solution sets for k-objective optimization problems: An exact method and approximations

Integrated Preference Functional (IPF) is a set functional that, given a discrete set of points for a multiple objective optimization problem, assigns a numerical value to that point set. This value provides a quantitative measure for comparing different sets of points generated by solution procedures for difficult multiple objective optimization problems. We introduced the IPF for bi-criteria optimization problems in [Carlyle, W.M., Fowler, J.W., Gel, E., Kim, B., 2003. Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decision Sciences 34 (1), 63–82]. As indicated in that paper, the computational effort to obtain IPF is negligible for bi-criteria problems. For three or more objective function cases, however, the exact calculation of IPF is computationally demanding, since this requires k (⩾3) dimensional integration.In this paper, we suggest a theoretical framework for obtaining IPF for k (⩾3) objectives. The exact method includes solving two main sub-problems: (1) finding the optimality region of weights for all potentially optimal points, and (2) computing volumes of k dimensional convex polytopes. Several different algorithms for both sub-problems can be found in the literature. We use existing methods from computational geometry (i.e., triangulation and convex hull algorithms) to develop a reasonable exact method for obtaining IPF. We have also experimented with a Monte Carlo approximation method and compared the results to those with the exact IPF method.     

Computational complexity of stable partitions with B-preferences

Consider a special stable partition problem in which the player's preferences over sets to which she could belong are identical with her preferences over the most attractive member of a set and in case of indifference the set of smaller cardinality is preferred. If the preferences of all players over other (individual) players are strict, a strongly stable and a stable partition always exists. However, if ties are present, we show that both the existence problems are NP-complete. These results are very similar to what is known for the stable roommates problem. Received: July 2000/Revised: October 2002 RID="*" ID="*"  This work was supported by the Slovak Agency for Science, contract #1/7465/20 “Combinatorial Structures and Complexity of Algorithms”.     

Violator spaces: Structure and algorithms

Sharir and Welzl introduced an abstract framework for optimization problems, called LP-type problems or also generalized linear programming problems, which proved useful in algorithm design. We define a new, and as we believe, simpler and more natural framework: violator spaces, which constitute a proper generalization of LP-type problems. We show that Clarkson's randomized algorithms for low-dimensional linear programming work in the context of violator spaces. For example, in this way we obtain the fastest known algorithm for the P-matrix generalized linear complementarity problem with a constant number of blocks. We also give two new characterizations of LP-type problems: they are equivalent to acyclic violator spaces, as well as to concrete LP-type problems (informally, the constraints in a concrete LP-type problem are subsets of a linearly ordered ground set, and the value of a set of constraints is the minimum of its intersection).     

Analytic efficient solution set for multi-criteria quadratic programs

We present active set methods to evaluate the exact analytic efficient solution set for multi-criteria convex quadratic programming problems (MCQP) subject to linear constraints. The idea is based on the observations that a strictly convex programming problem admits a unique solution, and that the efficient solution set for a multi-criteria strictly convex quadratic programming problem with linear equality constraints can be parameterized. The case of bi-criteria quadratic programming (BCQP) is first discussed since many of the underlying ideas can be explained much more clearly in the case of two objectives. In particular we note that the efficient solution set of a BCQP problem is a curve on the surface of a polytope. The extension to problems with more than two objectives is straightforward albeit some slightly more complicated notation. Two numerical examples are given to illustrate the proposed methods.     

Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

ABSTRACT

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.