Abstract This paper addresses the generation of binary 2-separating codes and the study of the code rates that can be achieved in practice. In the case of binary 2-separating codes, there exist lower and upper theoretical bounds in the rates that can be achieved. The generation of 2-separating codes has been studied from a theoretical point of view, but, as far as we know, it has not been tackled from a practical point of view. In this paper, we consider and analyze two different generation algorithms. Both algorithms were implemented in CUDA and executed in GPUs, for the sake of efficiency. The first algorithm is inspired by the Moser–Tardos algorithm, which is based on the Local Lovász Lemma. This algorithm has a strong theoretical appeal; codes obtained through this first algorithm can be shown to match the best known lower bound. To generate codes with rates as large as possible, a second algorithm has been implemented. The rates achieved are larger than those achieved with the first algorithm, but they still are very far from the theoretical upper bound. The results obtained suggest that the theoretical upper bound can probably be improved.

The usefulness of Identifiable Parent Property (IPP) schemes in diverse scenarios has led to several distinct but related concepts. This work focuses on three of these concepts: “classical” IPP codes, Multimedia IPP codes, and IPP set systems. Although several existence bounds for all of the above schemes are known, constructions are scarce. In this paper, we present explicit constructions of all mentioned IPP notions, in the form of combinatorial objects. Our discussion follows a systematic procedure. First, we use the Lovász Local Lemma (LLL) to obtain existence bounds for the object to be constructed. The bounds derived essentially match the previously best-known ones. Additionally, our proof strategy enables for further development. It allows us to use the Moser-Tardos algorithmic version of the LLL in order to construct, with polynomial complexity, the actual objects. Moreover, we extend the results of Giotis et al. to precisely establish the computational complexity of the proposed algorithms.

We investigate when non-dictatorial aggregation is possible from an algorithmic perspective, where non-dictatorial aggregation means that the votes cast by the members of a society can be aggregated in such a way that there is no single member of the society that always dictates the collective outcome. We consider the setting in which the members of a society take a position on a fixed collection of issues, where for each issue several different alternatives are possible, but the combination of choices must belong to a given set X of allowable voting patterns. Such a set X is called a possibility domain if there is an aggregator that is non-dictatorial, operates separately on each issue, and returns values among those cast by the society on each issue. We design a polynomial-time algorithm that decides, given a set X of voting patterns, whether or not X is a possibility domain. Furthermore, if X is a possibility domain, then the algorithm constructs in polynomial time a non-dictatorial aggregator for X. Furthermore, we show that the question of whether a Boolean domain X is a possibility domain is in NLOGSPACE. We also design a polynomial-time algorithm that decides whether X is a uniform possibility domain, that is, whether X admits an aggregator that is non-dictatorial even when restricted to any two positions for each issue. As in the case of possibility domains, the algorithm also constructs in polynomial time a uniform non-dictatorial aggregator, if one exists. Then, we turn our attention to the case where X is given implicitly, either as the set of assignments satisfying a propositional formula, or as a set of consistent evaluations of a sequence of propositional formulas. In both cases, we provide bounds to the complexity of deciding if X is a (uniform) possibility domain. Finally, we extend our results to four types of aggregators that have appeared in the literature: generalized dictatorships, whose outcome is always an element of their input, anonymous aggregators, whose outcome is not affected by permutations of their input, monotone, whose outcome does not change if more individuals agree with it and systematic, which aggregate every issue in the same way.

In the field of Judgment Aggrgation, a domain, that is a subset of a Cartesian power of $\{0,1\}$, is considered to reflect abstract rationality restrictions on vectors of two-valued judgments on a number of issues. We are interested in the ways we can aggregate the positions of a set of individuals, whose positions over each issue form vectors of the domain, by means of unanimous (idempotent) functions, whose output is again an element of the domain. Such functions are called non-dictatorial, when their output is not simply the positions of a single individual. Here, we consider domains admitting various kinds of non-dictatorial aggregators, which reflect various properties of majority aggregation: (locally) non-dictatorial, generalized dictatorships, anonymous, monotone, StrongDem and systematic. We show that interesting and, in some sense, democratic voting schemes are always provided by domains that can be described by propositional formulas of specific syntactic types we define. Furthermore, we show that we can efficiently recognize such formulas and that, given a domain, we can both efficiently check if it is described by such a formula and, in case it is, construct it. Our results fall in the realm of classical results concerning the syntactic characterization of domains with specific closure properties, like domains closed under logical AND which are the models of Horn formulas. The techniques we use to obtain our results draw from judgment aggregation as well as propositional logic and universal algebra.

We consider the problem of aggregating votes cast by a society on a fixed set of issues, where each member of the society may vote for one of several positions on each issue, but the combination of votes on the various issues is restricted to a set of feasible voting patterns. We follow the aggregation framework used by Dokow and Holzman [Aggregation of non-binary evaluations, Advances in Applied Mathematics , 45:4, 487--504, 2010], in which both preference aggregation and judgment aggregation can be cast. We require the aggregation to be independent on each issue, and also supportive, i.e., for every issue, the corresponding component of every aggregator, when applied to a tuple of votes, must take as value one of the votes in that tuple. We prove that, in such a setup, non-dictatorial aggregation of votes in a society of an arbitrary size is possible if and only if either there is a non-dictatorial aggregator for two voters or there is an aggregator for three voters such that, for each issue, the corresponding component of the aggregator, when restricted to two-element sets of votes, is a majority operation or a minority operation. We then introduce a notion of a uniform non-dictatorial aggregator, which is an aggregator such that on every issue, and when restricted to arbitrary two-element subsets of the votes for that issue, it differs from all projection functions. We first give a characterization of sets of feasible voting patterns that admit a uniform non-dictatorial aggregator. After this and by making use of Bulatov’s dichotomy theorem for conservative constraint satisfaction problems, we connect social choice theory with the computational complexity of constraint satisfaction by proving that if a set of feasible voting patterns has a uniform non-dictatorial aggregator of some arity, then the multi-sorted conservative constraint satisfaction problem on that set (with each issue representing a different sort) is solvable in polynomial time; otherwise, it is NP-complete.