Publications

Preprints

2023

1. ePrint

   Meeting in a Convex World: Convex Consensus with Asynchronous Fallback

   Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, and 1 more author

   2023

   Abs Bib ePrint

   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.

   @misc{Constantinescu2023Convex,
     author = {Constantinescu, Andrei and Ghinea, Diana and Wattenhofer, Roger and Westermann, Floris},
     title = {Meeting in a Convex World: Convex Consensus with Asynchronous Fallback},
     howpublished = {Cryptology ePrint Archive, Paper 2023/1364},
     year = {2023},
     url = {https://eprint.iacr.org/2023/1364},
   }

Conference Articles

2024

1. ICALP 24

   Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games

   Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, and 2 more authors

   In Proceedings of the 51st International Colloquium on Automata, Languages and Programming, Tallinn, Estonia, Jul 2024

   Abs arXiv Bib

   A decade ago, Gerhard Woeginger posed an open problem that became well-known as “Woeginger’s Hiking Problem”: Consider a group of \(n\) people that want to go hiking; everyone expresses preferences over the size of their hiking group in the form of an interval between \(1\) and \(n\). Is it possible to efficiently assign the \(n\) people to a set of hiking subgroups so that every person approves the size of their assigned subgroup? The problem is also known as efficiently deciding if an instance of an anonymous Hedonic Game with interval approval preferences admits a wonderful partition. We resolve the open problem in the affirmative by presenting an \(O(n^5)\) time algorithm for Woeginger’s Hiking Problem. Our solution is based on employing a dynamic programming approach for a specific rectangle stabbing problem from computational geometry. Moreover, we propose natural, more demanding extensions of the problem, e.g., maximizing the number of satisfied participants and variants with single-peaked preferences, and show that they are also efficiently solvable. Last but not least, we employ our solution to efficiently compute a partition that maximizes the egalitarian welfare for anonymous single-peaked Hedonic Games.

   @inproceedings{Constantinescu2023Hiking,
     title = {Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games},
     author = {Constantinescu, Andrei and Lenzner, Pascal and Reiffenhäuser, Rebecca and Schmand, Daniel and Varricchio, Giovanna},
     year = {2024},
     month = jul,
     booktitle = {Proceedings of the 51st International Colloquium on Automata, Languages and Programming, Tallinn, Estonia},
     selected = true
   }

2. AAAI 24

   Unravelling Expressive Delegations: Complexity and Normative Analysis

   Giannis Tyrovolas, Andrei Constantinescu, and Edith Elkind

   In Proceedings of the 38th AAAI Conference on Artificial Intelligence, Vancouver, Canada, Feb 2024

   Abs arXiv Bib

   We consider binary group decision-making under a rich model of liquid democracy recently proposed by Colley, Grandi, and Novaro (2022): agents submit ranked delegation options, where each option may be a function of multiple agents' votes; e.g., "I vote yes if a majority of my friends vote yes." Such ballots are unravelled into a profile of direct votes by selecting one entry from each ballot so as not to introduce cyclic dependencies. We study delegation via monotonic Boolean functions, and two unravelling procedures: MinSum, which minimises the sum of the ranks of the chosen entries, and its egalitarian counterpart, MinMax. We provide complete computational dichotomies: MinSum is hard to compute (and approximate) as soon as any non-trivial functions are permitted, and polynomial otherwise; for MinMax the easiness results extend to arbitrary-arity logical ORs and ANDs taken in isolation, but not beyond. For the classic model of delegating to individual agents, we give asymptotically near-tight algorithms for carrying out the two procedures and efficient algorithms for finding optimal unravellings with the highest vote count for a given alternative. These algorithms inspire novel tie-breaking rules for the setup of voting to change a status quo. We then introduce a new axiom, which can be viewed as a variant of the participation axiom, and use algorithmic techniques developed earlier in the paper to show that it is satisfied by MinSum and a lexicographic refinement of MinMax (but not MinMax itself).

   @inproceedings{Tyrovolas2023Unravelling,
     title = {Unravelling Expressive Delegations: Complexity and Normative Analysis},
     author = {Tyrovolas, Giannis and Constantinescu, Andrei and Elkind, Edith},
     booktitle = {Proceedings of the 38th AAAI Conference on Artificial Intelligence, Vancouver, Canada},
     year = {2024},
     month = feb,
   }

2023

1. OPODIS 23

   A Fair and Resilient Decentralized Clock Network for Transaction Ordering

   Andrei Constantinescu, Diana Ghinea, Lioba Heimbach, and 2 more authors

   In Proceedings of the 27th International Conference on Principles of Distributed Systems, Tokyo, Japan, Dec 2023

   Abs arXiv Bib Slides

   Traditional blockchain design gives miners or validators full control over transaction ordering, i.e., they can freely choose which transactions to include or exclude, as well as in which order. While not an issue initially, the emergence of decentralized finance has introduced new transaction order dependencies allowing parties in control of the ordering to make a profit by front-running others' transactions. In this work, we present the Decentralized Clock Network, a new approach for achieving fair transaction ordering. Users submit their transactions to the network's clocks, which run an agreement protocol that provides each transaction with a timestamp of receipt which is then used to define the transactions' order. By separating agreement from ordering, our protocol is efficient and has a simpler design compared to other available solutions. Moreover, our protocol brings to the blockchain world the paradigm of asynchronous fallback, where the algorithm operates with stronger fairness guarantees during periods of synchronous use, switching to an asynchronous mode only during times of increased network delay.

   @inproceedings{Constantinescu2023FairClocks,
     title = {A Fair and Resilient Decentralized Clock Network for Transaction Ordering},
     author = {Constantinescu, Andrei and Ghinea, Diana and Heimbach, Lioba and Wang, Zilin and Wattenhofer, Roger},
     year = {2023},
     month = dec,
     booktitle = {Proceedings of the 27th International Conference on Principles of Distributed Systems, Tokyo, Japan},
   }

2. WINE 23

   Stable Dinner Party Seating Arrangements (Best Paper Award)

   Damien Berriaud, Andrei Constantinescu, and Roger Wattenhofer

   In Proceedings of the 19th Conference on Web and Internet Economics, Shanghai, China, Dec 2023

   Abs arXiv Bib Slides

   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.

   @inproceedings{Berriaud2023StableDinnerParty,
     title = {Stable Dinner Party Seating Arrangements},
     author = {Berriaud, Damien and Constantinescu, Andrei and Wattenhofer, Roger},
     booktitle = {Proceedings of the 19th Conference on Web and Internet Economics, Shanghai, China},
     month = dec,
     year = {2023},
     selected = true
   }

3. WINE 23

   Recovering Single-Crossing Preferences From Approval Ballots

   Andrei Constantinescu, and Roger Wattenhofer

   In Proceedings of the 19th Conference on Web and Internet Economics, Shanghai, China, Dec 2023

   Abs arXiv Bib Code Slides

   An electorate with fully-ranked innate preferences casts approval votes over a finite set of alternatives. As a result, only partial information about the true preferences is revealed to the voting authorities. In an effort to understand the nature of the true preferences given only partial information, one might ask whether the unknown innate preferences could possibly be single-crossing. The existence of a polynomial time algorithm to determine this has been asked as an outstanding problem in the works of Elkind and Lackner. We hereby give a polynomial time algorithm determining a single-crossing collection of fully-ranked preferences that could have induced the elicited approval ballots, or reporting the nonexistence thereof. Moreover, we consider the problem of identifying negative instances with a set of forbidden sub-ballots, showing that any such characterization requires infinitely many forbidden configurations.

   @inproceedings{Constantinescu2023RecoveringSingleCrossing,
     author = {Constantinescu, Andrei and Wattenhofer, Roger},
     title = {Recovering Single-Crossing Preferences From Approval Ballots},
     booktitle = {Proceedings of the 19th Conference on Web and Internet Economics, Shanghai, China},
     month = dec,
     year = {2023},
   }

4. AAMAS 23

   Computing the Best Policy That Survives a Vote

   Andrei Constantinescu, and Roger Wattenhofer

   In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, London, United Kingdom, Jun 2023

   Abs arXiv Bib Official Slides

   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.

   @inproceedings{Constantinescu2023BestPolicy,
     author = {Constantinescu, Andrei and Wattenhofer, Roger},
     title = {Computing the Best Policy That Survives a Vote},
     year = {2023},
     isbn = {9781450394321},
     publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
     address = {Richland, SC},
     booktitle = {Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, London, United Kingdom},
     pages = {2058--2066},
     numpages = {9},
     month = jun,
     keywords = {probabilistic method, judgment aggregation, Anscombe's paradox, randomized algorithms, computational complexity, multiple referenda, approval ballots, computational social choice},
     location = {London, United Kingdom},
     series = {AAMAS'23},
     selected = true
   }

2022

1. IJCAI 22

   Voting in Two-Crossing Elections

   Andrei Constantinescu, and Roger Wattenhofer

   In Proceedings of the 31st International Joint Conference on Artificial Intelligence, Vienna, Austria, Jul 2022

   Abs arXiv Bib Official Slides

   We introduce two-crossing elections as a generalization of single-crossing elections, showing a number of new results. First, we show that two-crossing elections can be recognized in polynomial time, by reduction to the well-studied consecutive ones problem. We also conjecture that recognizing \(k\)-crossing elections is NP-complete in general, providing evidence by relating to a problem similar to consecutive ones proven to be hard in the literature. Single-crossing elections exhibit a transitive majority relation, from which many important results follow. On the other hand, we show that the classical Debord-McGarvey theorem can still be proven two-crossing, implying that any weighted majority tournament is inducible by a two-crossing election. This shows that many voting rules are NP-hard under two-crossing elections, including Kemeny and Slater. This is in contrast to the single-crossing case and outlines an important complexity boundary between single- and two-crossing. Subsequently, we show that for two-crossing elections the Young scores of all candidates can be computed in polynomial time, by formulating a totally unimodular linear program. Finally, we consider the Chamberlin-Courant rule with arbitrary disutilities and show that a winning committee can be computed in polynomial time, using an approach based on dynamic programming.

   @inproceedings{Constantinescu2022TwoCrossing,
     title = {Voting in Two-Crossing Elections},
     author = {Constantinescu, Andrei and Wattenhofer, Roger},
     booktitle = {Proceedings of the 31st International Joint Conference on
                    Artificial Intelligence, Vienna, Austria},
     publisher = {International Joint Conferences on Artificial Intelligence Organization},
     editor = {Raedt, Lud De},
     pages = {208--214},
     year = {2022},
     month = jul,
     doi = {10.24963/ijcai.2022/30},
     url = {https://doi.org/10.24963/ijcai.2022/30},
   }

2021

1. AAAI 21

   Proportional Representation under Single-Crossing Preferences Revisited

   Andrei Constantinescu, and Edith Elkind

   In Proceedings of the 35th AAAI Conference on Artificial Intelligence, Virtual, May 2021

   Abs arXiv Bib Official Slides

   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.

   @inproceedings{Constantinescu2021SingleCrossingCC,
     title = {Proportional Representation under Single-Crossing Preferences Revisited},
     volume = {35},
     number = {6},
     booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence, Virtual},
     author = {Constantinescu, Andrei and Elkind, Edith},
     year = {2021},
     month = may,
     pages = {5286--5293},
     url = {https://ojs.aaai.org/index.php/AAAI/article/view/16667},
     selected = true
   }