Let q N and Π be a closed set of strictly positive distributions over [q ] . Let CH (Π) denote the convex hull of Π .

We kindly thank the reviewers for their detailed reviews, valuable feedback and suggestions for improvement. Indeed, our proof of the new SW theorem relies on an "ordering" of the coordinates of arbitrary equivariant SW theorem under arbitrary finite group action would be desirable, however the proof is out of our reach as of today. In a way, this limitation is similar to the distinction between "point clouds" (which in We will add this discussion in the paper, and mention it in the abstract. In its "deep" original version, it covers all type of "Message-Passing" GNNs, but not spectral GNNs which use powers of the adjacency matrix. We will clarify this in the final version.

Since the calculations are essentially identical to the proof of Theorem 4.2, we omit the details.

In social choice theory, anonymity (all agents being treated equally) and neutrality (all alternatives being treated equally) are widely regarded as ``minimal demands'' and ``uncontroversial'' axioms of equity and fairness. However, the ANR impossibility -- there is no voting rule that satisfies anonymity, neutrality, and resolvability (always choosing one winner) -- holds even in the simple setting of two alternatives and two agents. How to design voting rules that optimally satisfy anonymity, neutrality, and resolvability remains an open question. We address the optimal design question for a wide range of preferences and decisions that include ranked lists and committees. Our conceptual contribution is a novel and strong notion of most equitable refinements that optimally preserves anonymity and neutrality for any irresolute rule that satisfies the two axioms. Our technical contributions are twofold. First, we characterize the conditions for the ANR impossibility to hold under general settings, especially when the number of agents is large. Second, we propose the most-favorable-permutation (MFP) tie-breaking to compute a most equitable refinement and design a polynomial-time algorithm to compute MFP when agents' preferences are full rankings.

The determination of the computational complexity of multi-agent pathfinding on directed graphs (diMAPF) has been an open research problem for many years. While diMAPF has been shown to be polynomial for some special cases, only recently, it has been established that the problem is NP-hard in general. Further, it has been proved that diMAPF will be in NP if the short solution hypothesis for strongly connected directed graphs is correct. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.

SATNet is a differentiable constraint solver with a custom backpropagation algorithm, which can be used as a layer in a deep-learning system. It is a promising proposal for bridging deep learning and logical reasoning. In fact, SATNet has been successfully applied to learn, among others, the rules of a complex logical puzzle, such as Sudoku, just from input and output pairs where inputs are given as images. In this paper, we show how to improve the learning of SATNet by exploiting symmetries in the target rules of a given but unknown logical puzzle or more generally a logical formula. We present SymSATNet, a variant of SATNet that translates the given symmetries of the target rules to a condition on the parameters of SATNet and requires that the parameters should have a particular parametric form that guarantees the condition. The requirement dramatically reduces the number of parameters to learn for the rules with enough symmetries, and makes the parameter learning of SymSATNet much easier than that of SATNet. We also describe a technique for automatically discovering symmetries of the target rules from examples. Our experiments with Sudoku and Rubik's cube show the substantial improvement of SymSATNet over the baseline SATNet.

We develop a framework to leverage the elegant "worst average-case" idea in smoothed complexity analysis to social choice, motivated by modern applications of social choice powered by AI and ML. Using our framework, we characterize the smoothed likelihood of some fundamental paradoxes and impossibility theorems as the number of agents increases. For Condrocet's paradox, we prove that the smoothed likelihood of the paradox either vanishes at an exponential rate, or does not vanish at all. For the folklore impossibility on the non-existence of voting rules that satisfy anonymity and neutrality, we characterize the rate for the impossibility to vanish, to be either polynomially fast or exponentially fast. We also propose a novel easy-to-compute tie-breaking mechanism that optimally preserves anonymity and neutrality for even number of alternatives in natural settings. Our results illustrate the smoothed possibility of social choice---even though the paradox and the impossibility theorem hold in the worst case, they may not be a big concern in practice in certain natural settings.

We propose to study equivariance in deep neural networks through parameter symmetries. In particular, given a group $\mathcal{G}$ that acts discretely on the input and output of a standard neural network layer $\phi_{W}: \Re^{M} \to \Re^{N}$, we show that $\phi_{W}$ is equivariant with respect to $\mathcal{G}$-action iff $\mathcal{G}$ explains the symmetries of the network parameters $W$. Inspired by this observation, we then propose two parameter-sharing schemes to induce the desirable symmetry on $W$. Our procedures for tying the parameters achieve $\mathcal{G}$-equivariance and, under some conditions on the action of $\mathcal{G}$, they guarantee sensitivity to all other permutation groups outside $\mathcal{G}$.