Xuan Kien Phung

Xuan Kien Phung, Sylvie Hamel

Kemeny's rule is one of the most studied and well-known voting schemes with various important applications in computational social choice and biology. Recently, Kemeny's rule was generalized via a set-wise approach by Gilbert et. al. This paradigm presents interesting advantages in comparison with Kemeny's rule since not only pairwise comparisons but also the discordance between the winners of subsets of three alternatives are also taken into account in the definition of the $3$-wise Kendall-tau distance between two rankings. In spite of the NP-hardness of the 3-wise Kemeny problem which consists of computing the set of $3$-wise consensus rankings, namely rankings whose total $3$-wise Kendall-tau distance to a given voting profile is minimized, we establish in this paper several generalizations of the Major Order Theorems, as obtained by Milosz and Hamel for Kemeny's rule, for the $3$-wise Kemeny voting schemes to achieve a substantial search space reduction by efficiently determining in polynomial time the relative orders of pairs of alternatives. Essentially, our theorems quantify precisely the nontrivial property that if the preference for an alternative over another one in an election is strong enough, not only in the head-to-head competition but even when taking into account one or two more alternatives, then the relative order of these two alternatives in all $3$-wise consensus rankings must be as expected. As an application, we also obtain an improvement of the Major Order Theorems for Kememy's rule. Moreover, we show that the well-known $3/4$-majority rule of Betzler et al. for Kemeny's rule is only valid in general for elections with no more than $5$ alternatives with respect to the $3$-wise Kemeny scheme. Several simulations and tests of our algorithms on real-world and uniform data are provided.

Xuan Kien Phung, Sylvie Hamel

The important Kemeny problem, which consists of computing median consensus rankings of an election with respect to the Kemeny voting rule, admits important applications in biology and computational social choice and was generalized recently via an interesting setwise approach by Gilbert et. al. Our first results establish optimal quantitative extensions of the Unanimity property and the well-known $3/4$-majority rule of Betzler et al. for the classical Kemeny median problem. Moreover, by elaborating an exhaustive list of quantified axiomatic properties (such as the Condorcet and Smith criteria, the $5/6$-majority rule, etc.) of the $3$-wise Kemeny rule where not only pairwise comparisons but also the discordance between the winners of subsets of three candidates are also taken into account, we come to the conclusion that the $3$-wise Kemeny voting scheme induced by the $3$-wise Kendall-tau distance presents interesting advantages in comparison with the classical Kemeny rule. For example, it satisfies several improved manipulation-proof properties. Since the $3$-wise Kemeny problem is NP-hard, our results also provide some of the first useful space reduction techniques by determining the relative orders of pairs of alternatives. Our works suggest similar interesting properties of higher setwise Kemeny voting schemes which justify and compensate for the more expensive computational cost than the classical Kemeny scheme.

Xuan Kien Phung, Sylvie Hamel

The Kemeny aggregation problem consists of computing the consensus rankings of an election with respect to the well-known Kemeny-Young voting method. These consensus rankings satisfy various fundamental properties and are the geometric medians of the votes in the election under the Kendall-tau distance which counts the number of pairwise disagreements. The Kemeny aggregation problem admits important applications in various domains such as computational social choice, machine learning, operations research, and biology but it is unfortunately NP-hard. Recently, Milosz and the second author presented an approach to reduce the search space of the problem by solving the relative order of pairs of elements in those consensus. In this article, we prove an optimized extension of this approach achieving significantly more refined space reduction techniques without adding much to the running time of the algorithms in practice, as illustrated by experimental results and analysis on real and synthetic data. We show how the constraints built by our approach can be used in combination with other methods such as Integer Programming and Finest Condorcet Partitioning to achieve an efficient and scalable solution approach to the Kemeny aggregation problem. Relaxed and approximate versions of our algorithms are also described and evaluated. We also provide practical methods to compute provable guarantees for the quality of the approximate rankings obtained.

Xuan Kien Phung

For non-uniform cellular automata (NUCA) with finite memory over an arbitrary universe with multiple local transition rules, we show that pointwise nilpotency, pointwise periodicity, and pointwise eventual periodicity properties are respectively equivalent to nilpotency, periodicity, and eventual periodicity. Moreover, we prove that every linear NUCA which satisfies pointwise a polynomial equation (which may depend on the configuration) must be an eventually periodic linear NUCA. Generalizing results for higher dimensional group and linear CA, we also establish the decidability results of the above dynamical properties as well as the injectivity for arbitrary NUCA with finite memory which are local perturbations of higher dimensional linear and group CA. Some generalizations to the case of sparse global perturbations of higher dimensional linear and group CA are also obtained.

Xuan Kien Phung

Gottschalk's surjunctivity conjecture for a group $G$ states that it is impossible for cellular automata (CA) over the universe $G$ with finite alphabet to produce strict embeddings of the full shift into itself. A group universe $G$ satisfying Gottschalk's surjunctivity conjecture is called a surjunctive group. The surjunctivity theorem of Gromov and Weiss shows that every sofic group is surjunctive. In this paper, we study the surjunctivity of local perturbations of CA and more generally of non-uniform cellular automata (NUCA) with finite memory and uniformly bounded singularity over surjunctive group universes. In particular, we show that such a NUCA must be invertible whenever it is reversible. We also obtain similar results which extend to the class of NUCA a certain dual-surjunctivity theorem of Capobianco, Kari, and Taati for CA.