Computing tournament solutions using relation algebra and RelView

We describe a simple computing technique for the tournament choice problem. It rests upon relational modeling and uses the BDD-based computer system RelView for the evaluation of the relation-algebraic expressions that specify the solutions and for the visualization of the computed results. The Copeland set can immediately be identified using RelView’s labeling feature. Relation-algebraic specifications of the Condorcet non-losers, the Schwartz set, the top cycle, the uncovered set, the minimal covering set, the Banks set, and the tournament equilibrium set are delivered. We present an example of a tournament on a small set of alternatives, for which the above choice sets are computed and visualized via RelView. The technique described in this paper is very flexible and especially appropriate for prototyping and experimentation, and as such very instructive for educational purposes. It can easily be applied to other problems of social choice and game theory.     

Applying relation algebra and RelView to measures in a social network

We present an application of relation algebra to measure agents’ ‘strength’ in a social network with influence between agents. In particular, we deal with power, success, and influence of an agent as measured by the generalized Hoede–Bakker index and its modifications, and by the influence indices. We also apply relation algebra to determine followers of a coalition and the kernel of an influence function. This leads to specifications, which can be executed with the help of the BDD-based tool RelView after a simple translation into the tool’s programming language. As an example we consider the present Dutch Parliament.     

An interdisciplinary approach to coalition formation

A stable government is by definition not dominated by any other government. However, it may happen that all governments are dominated. In graph–theoretic terms this means that the dominance graph does not possess a source. In this paper we are able to deal with this case by a clever combination of notions from different fields, such as relational algebra, graph theory and social choice theory, and by using the computer support system RelView for computing solutions and visualizing the results. Using relational algorithms, in such a case we break all cycles in each initial strongly connected component by removing the vertices in an appropriate minimum feedback vertex set. In this way we can choose a government that is as close as possible to being un-dominated. To achieve unique solutions, we additionally apply the majority ranking recently introduced by Balinski and Laraki. The main parts of our procedure can be executed using the RelView tool. Its sophisticated implementation of relations allows to deal with graph sizes that are sufficient for practical applications of coalition formation.     

Optimal coalition formation and surplus distribution: Two sides of one coin

A fuzzy coalitional game represents a situation in which players can vary the intensity at which they participate in the coalitions accessible to them, as opposed to the treatment as a binary choice in the non-fuzzy (crisp) game. Building on the property - not made use of so far in the literature of fuzzy games - that a fuzzy game can be represented as a convex program, this paper shows that the optimum of such a program determines the optimal coalitions as well as the optimal rewards for the players, two sides of one coin. Furthermore, this program is seen to provide a unifying framework for representing the core, the least core, and the (fuzzy) nucleolus, among others. Next, we derive conditions for uniqueness of core rewards and to deal with non-uniqueness we introduce a family of parametric perturbations of the convex program that encompasses a large number of well-known concepts for selection from the core, including the Dutta-Ray solution (Dutta and Ray, 1989), the equal sacrifice solution (Yu, 1973), the equal division solution (Selten, 1972) and the tau-value (Tijs, 1981). We also generalize the concept of the Grand Coalition of contracting players by allowing for multiple technologies, and we specify the conditions for this allocation to be unique and Egalitarian. Finally, we show that our formulation offers a natural extension to existing models of production economies with threats and division rules for common surplus.     

Differential approximation of min sat, max sat and related problems

We present differential approximation results (both positive and negative) for optimal satisfiability, optimal constraint satisfaction, and some of the most popular restrictive versions of them. As an important corollary, we exhibit an interesting structural difference between the landscapes of approximability classes in standard and differential paradigms.     

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

Using ideas and results from polynomial time approximation and exact computation we design approximation algorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, max independent set and min vertex cover.     

On a generalization of Chen's iterated integrals

Text

In this paper, Chen's iterated integrals are generalized by interpolation of functions of the positive integer number of times which particular forms are iterated in integrals along specific paths, to certain complex values. These generalized iterated integrals satisfy both an additive iterative property and comultiplication formula. In a particular example, a (non-classical) multiplicative iterative property is also shown to hold. After developing this theory in the first part of the paper we discuss various applications, including the expression of certain zeta functions as complex iterated integrals (from which an obstruction to the existence of a contour integration proof of the functional equation for the Dedekind zeta function emerges); a way of thinking about complex iterated derivatives arising from a reformulation of a result of Gel'fand and Shilov in the theory of distributions; and a direct topological proof of the monodromy of polylogarithms.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=dsVvo7s8BYU.     

An exact algorithm for MAX-CUT in sparse graphs

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O^*(2^(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O^*(2^mn/(m+n)). Both algorithms use polynomial space.     

Pointlike sets with respect to R and J

We present an algorithm to compute the pointlike subsets of a finite semigroup with respect to the pseudovariety of all finite R-trivial semigroups. The algorithm is inspired by Henckell’s algorithm for computing the pointlike subsets with respect to the pseudovariety of all finite aperiodic semigroups. We also give an algorithm to compute -pointlike sets, where denotes the pseudovariety of all finite J-trivial semigroups. We finally show that, in contrast with the situation for , the natural adaptation of Henckell’s algorithm to computes pointlike sets, but not all of them.     

Cohomology and deformations of the infinite-dimensional filiform Lie algebra

Denote the infinite-dimensional -graded Lie algebra defined by basis e_i, i1, and relations [e₁,e_i]=e_i+1 for all i2. We compute in this article the bracket structure on , and in relation to this, we establish that there are only finitely many true deformations of in each non-positive weight by constructing them explicitly. It turns out that in weight 0 one gets exactly the other two filiform Lie algebras.     

Notes on the nuclearity of random subalgebras of O2{\mathcal {O}_2}

There exists a separable exact C*-algebra A which contains all separable exact C*-algebras as subalgebras, and for each norm-dense measure μ on A and independent μ-distributed random elements x ₁, x ₂, ... we have . Further, there exists a norm-dense non-atomic probability measure μ on the Cuntz algebra such that for an independent sequence x ₁, x ₂, ... of μ-distributed random elements x _i we have . We introduce the notion of the stochastic rank for a unital C*-algebra and prove that the stochastic rank of C([0, 1] ^d ) is d. B. Burgstaller was supported by the Austrian Schr?dinger stipend J2471-N12.     

A sparse counterpart of Reichel and Gragg’s package QRUP

We describe how to maintain the triangular factor of a sparse QR factorization when columns are added and deleted and Q cannot be stored for sparsity reasons. The updating procedures could be thought of as a sparse counterpart of Reichel and Gragg’s package QRUP. They allow us to solve a sequence of sparse linear least squares subproblems in which each matrix B_k is an independent subset of the columns of a fixed matrix A, and B_k+1 is obtained by adding or deleting one column. Like Coleman and Hulbert [T. Coleman, L. Hulbert, A direct active set algorithm for large sparse quadratic programs with simple bounds, Math. Program. 45 (1989) 373-406], we adapt the sparse direct methodology of Björck and Oreborn of the late 1980s, but without forming A^TA, which may be only positive semidefinite. Our Matlab 5 implementation works with a suitable row and column numbering within a static triangular sparsity pattern that is computed in advance by symbolic factorization of A^TA and preserved with placeholders.     

A remark on renormalized volume and Euler characteristic for ache 4-manifolds

This note computes a renormalized volume and a renormalized Gauss-Bonnet-Chern formula for asymptotically complex hyperbolic Einstein (so-called ache) 4-manifolds.     

Realizations and LP

LP can be seen as a logic of knowledge with justifications. See [S. Artemov, The logic of justification, The Review of Symbolic Logic 1 (4) (2008) 477–513] for a recent comprehensive survey of justification logics generally. Artemov’s Realization Theorem says justifications can be extracted from validities in the more conventional Hintikka-style logic of knowledge S4, in which they are not explicitly present. Justifications, however, are far from unique. There are many ways of realizing each theorem of S4 in the logic LP. If the machinery of justifications is to be applied to artificial intelligence, or better yet, to everyday reasoning, we will need to work with whatever justifications we may have at hand—one version may not be interchangeable with another, even though they realize the same S4 formula. In this paper we begin the process of providing tools for reasoning about justifications directly. The tools are somewhat complex, but in retrospect this should not be surprising. Among other things, we provide machinery for combining two realizations of the same formula, and for replacing subformulas by equivalent subformulas. (The second of these is actually weaker than just stated, but this is not the place for a detailed formulation.) The results are algorithmic in nature—semantics for LP plays no role. We apply our results to provide a new algorithmic proof of Artemov’s Realization Theorem itself. This paper is a much extended version of [M.C. Fitting, Realizations and LP, in: S. Artemov, A. Nerode (Eds.), Logical Foundations of Computer Science—New York ’07, in: Lecture Notes in Computer Science, vol. 4514, Springer-Verlag, 2007, pp. 212–223].