Andrei Constantinescu

Convex Consensus (CC) allows a set of parties to agree on a value \(v\) inside the convex hull of their inputs with respect to a predefined convexity notion, even in the presence of byzantine parties. In this work, we focus on achieving CC in the best-of-both-worlds paradigm, i.e., simultaneously tolerating at most \(t_s\) corruptions if communication is synchronous, and at most \(t_a \leq t_s\) corruptions if it is asynchronous. Our protocol is randomized, which is a requirement under asynchrony, and we prove that it achieves optimal resilience. In the process, we introduce communication primitives tailored to the best-of-both-worlds model, which we believe to be of independent interest. These are a deterministic primitive, which allows honest parties to obtain intersecting views, and a randomized primitive, leading to identical views (which is impossible to achieve deterministically). Afterwards, we consider achieving consensus using deterministic protocols, for which the agreement condition must be appropriately relaxed depending on the convexity space. For the relevant case of graph convexity spaces, we find that a previous asynchronous approximate agreement protocol for chordal graphs is incorrect, and hereby give a new protocol for the problem designed for the best-of-both-worlds model and achieving tight point-wise resilience bounds. Finally, we show that asynchronous graph approximate agreement remains unsolvable by deterministic protocols even when corruptions are restricted to at most two crashing nodes and the distance agreement threshold is linear in the size of the graph.

A group of \(n\) agents with numerical preferences for each other are to be assigned to the \(n\) seats of a dining table. We study two natural topologies: circular (cycle) tables and panel (path) tables. For a given seating arrangement, an agent’s utility is the sum of their preference values towards their (at most two) direct neighbors. An arrangement is envy-free if no agent strictly prefers someone else’s seat, and it is stable if no two agents strictly prefer each other’s seats. Recently, it was shown that for both paths and cycles it is NP-hard to decide whether an envy-free arrangement exists, even for symmetric binary preferences. In contrast, we show that, if agents come from a bounded number of classes, the problem is solvable in polynomial time for arbitrarily-valued possibly asymmetric preferences, including outputting an arrangement if possible. We also give simpler proofs of the previous hardness results if preferences are allowed to be asymmetric. For stability, it is known that deciding the existence of stable arrangements is NP-hard for both topologies, but only if sufficiently-many numerical values are allowed. As it turns out, even constructing unstable instances can be challenging in certain cases, e.g., binary values. We propose a complete characterization of the existence of stable arrangements based on the number of distinct values in the preference matrix and the number of agent classes. We also ask the same question for non-negative values and give an almost-complete characterization, the most interesting outstanding case being that of paths with two-valued non-negative preferences, for which we experimentally find that stable arrangements always exist and prove it under the additional constraint that agents can only swap seats when sitting at most two positions away. Similarly to envy-freeness, we also give a polynomial-time algorithm for determining a stable arrangement assuming a bounded number of classes. We moreover consider the swap dynamics and exhibit instances where they do not converge, despite a stable arrangement existing.

An assembly of \(n\) voters needs to decide on \(t\) independent binary issues. Each voter has opinions about the issues, given by a \(t\)-bit vector. Anscombe's paradox shows that a policy following the majority opinion in each issue may not survive a vote by the very same set of \(n\) voters, i.e., more voters may feel unrepresented by such a majority-driven policy than represented. A natural resolution is to come up with a policy that deviates a bit from the majority policy but no longer gets more opposition than support from the electorate. We show that a Hamming distance to the majority policy of at most \(\lfloor(t - 1) / 2\rfloor\) can always be guaranteed, by giving a new probabilistic argument relying on structure-preserving symmetries of the space of potential policies. Unless the electorate is evenly divided between the two options on all issues, we in fact show that a policy strictly winning the vote exists within this distance bound. Our approach also leads to a deterministic polynomial-time algorithm for finding policies with the stated guarantees, answering an open problem of previous work. For odd \(t\), unless we are in the pathological case described above, we also give a simpler and more efficient algorithm running in expected polynomial time with the same guarantees. We further show that checking whether distance strictly less than \(\lfloor(t - 1) / 2\rfloor\) can be achieved is NP-hard, and that checking for distance at most some input \(k\) is FPT with respect to several natural parameters.

We study the complexity of determining a winning committee under the Chamberlin–Courant voting rule when voters’ preferences are single-crossing on a line, or, more generally, on a tree. For the line, Skowron et al. (2015) describe an \(O(n^2mk)\) algorithm (where \(n\), \(m\), \(k\) are the number of voters, the number of candidates and the committee size, respectively); we show that a simple tweak improves the time complexity to \(O(nmk)\). We then improve this bound for \(k=\Omega(\log n)\) by reducing our problem to the \(k\)-link path problem for DAGs with concave Monge weights, obtaining a \(nm2^{O\left(\sqrt{\log k\log\log n}\right)}\) algorithm for the general case and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater, Puppe, and Slinko (2015), and develop a \(O(nmk)\) algorithm for this case as well.