Publications
Preprints
2025
- Logarithmic Approximation for Road Pricing on GridsAndrei Constantinescu, Andrzej Turko, and Roger WattenhoferFeb 2025
Consider a graph \(G = (V, E)\) and some commuters, each specified by a tuple \((u, v, b)\) consisting of two nodes in the graph \(u, v \in V\) and a non-negative real number \(b\), specifying their budget. The goal is to find a pricing function \(p\) of the edges of \(G\) that maximizes the revenue generated by the commuters. Here, each commuter \((u, v, b)\) either pays the lowest-cost of a \(u\!-\!v\) path under the pricing \(p\), or \(0\), if this exceeds their budget \(b\). We study this problem for the case where \(G\) is a bounded-width grid graph and give a polynomial-time approximation algorithm with approximation ratio \(O(\log |E|)\). Our approach combines existing ideas with new insights. Most notably, we employ a rather seldom-encountered technique that we coin under the name "assume-implement dynamic programming." This technique involves dynamic programming where some information about the future decisions of the dynamic program is guessed in advance and 'assumed' to hold, and then subsequent decisions are forced to 'implement' the guess. This enables computing the cost of the current transition by using information that would normally only be available in the future.
@misc{Constantinescu2025RoadPricing, author = {Constantinescu, Andrei and Turko, Andrzej and Wattenhofer, Roger}, title = {Logarithmic Approximation for Road Pricing on Grids}, year = {2025}, month = feb, }
Conference Articles
2025
- Validity in Network-Agnostic Byzantine Agreement (Highlighted Paper)Andrei Constantinescu, Marc Dufay, Diana Ghinea, and 1 more authorIn Proceedings of the 39th International Symposium on Distributed Computing, Oct 2025
Byzantine Agreement (BA) considers a setting of \(n\) parties, out of which up to \(t\) can exhibit byzantine (malicious) behavior. Honest parties must decide on a common value (agreement), which must belong to a set determined by the honest inputs (validity). Depending on the use case, this set can grow or shrink, leading to various possible desiderata collectively known as validity conditions. Varying the validity property requirement can affect the regime under which BA is solvable. Our work investigates how the selected validity property impacts BA solvability in the network-agnostic model, where the network can either be synchronous with up to \(t_s\) byzantine parties or asynchronous with up to \(t_a \le t_s\) byzantine parties. We give necessary and sufficient conditions for a validity property to render BA solvable, both for the case with cryptographic setup and for the one without. This traces the precise boundary of solvability in the network-agnostic model for every validity property. Our proof of sufficiency provides a universal protocol, that achieves BA for a given validity property whenever the provided conditions are satisfied. We note that, for any non-trivial validity property, the condition \(2 \cdot t_s + t_a < n\) is necessary for BA to be solvable, even with cryptographic setup. Specializing this claim to \(t_a = 0\) gives that \(t < n/2\) is required whenever one expects a purely synchronous protocol to also work in an asynchronous network when there are no corruptions. This is especially surprising given that, for some validity properties, \(t < n\) is a sufficient condition without the last stipulation.
@inproceedings{Constantinescu2025Validity, author = {Constantinescu, Andrei and Dufay, Marc and Ghinea, Diana and Wattenhofer, Roger}, title = {{Validity in Network-Agnostic Byzantine Agreement}}, booktitle = {Proceedings of the 39th International Symposium on Distributed Computing}, pages = {24:1--24:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, isbn = {978-3-95977-402-4}, issn = {1868-8969}, year = {2025}, volume = {356}, editor = {Kowalski, Dariusz R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.24}, urn = {urn:nbn:de:0030-drops-248413}, doi = {10.4230/LIPIcs.DISC.2025.24}, annote = {Keywords: byzantine agreement, validity, network-agnostic protocols}, month = oct, } - Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal CommunicationAndrei Constantinescu, Marc Dufay, Anton Paramonov, and 1 more authorIn Proceedings of the 39th International Symposium on Distributed Computing, Oct 2025
We study the problem of Strong Byzantine Agreement and establish tight upper and lower bounds on communication complexity, parameterized by the actual number of Byzantine faults. Specifically, for a system of \(n\) parties tolerating up to \(t\) Byzantine faults, out of which only \(f \le t\) are actually faulty, we obtain the following results: In the partially synchronous setting, we present the first Byzantine Agreement protocol that achieves adaptive communication complexity of \(\mathcal{O}(n + t \cdot f)\) words, which is asymptotically optimal. Our protocol has an optimal resilience of \(t < n/3\). In the asynchronous setting, we prove a lower bound of \(\Omega(n + t^2)\) on the expected number of messages, and design an almost matching protocol with an optimal resilience that solves agreement with \(\mathcal{O}((n + t^2)\cdot \log n)\) words. Our main technical contribution in the asynchronous setting is the utilization of a bipartite expander graph that allows for low-cost information dissemination.
@inproceedings{Constantinescu2025AdaptiveBA, author = {Constantinescu, Andrei and Dufay, Marc and Paramonov, Anton and Wattenhofer, Roger}, title = {{Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication}}, booktitle = {Proceedings of the 39th International Symposium on Distributed Computing}, pages = {52:1--52:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, isbn = {978-3-95977-402-4}, issn = {1868-8969}, year = {2025}, volume = {356}, editor = {Kowalski, Dariusz R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.52}, urn = {urn:nbn:de:0030-drops-248680}, doi = {10.4230/LIPIcs.DISC.2025.52}, annote = {Keywords: Byzantine Agreement, Communication Complexity, Adaptive Communication Complexity, Resilience}, month = oct, } - Transaction Fee Market Design for Parallel ExecutionBahar Acilan, Andrei Constantinescu, Lioba Heimbach, and 1 more authorIn Proceedings of the 7th Conference on Advances in Financial Technologies, Oct 2025
Given the low throughput of blockchains like Bitcoin and Ethereum, scalability - the ability to process an increasing number of transactions - has become a central focus of blockchain research. One promising approach is the parallelization of transaction execution across multiple threads. However, achieving efficient parallelization requires a redesign of the incentive structure within the fee market. Currently, the fee market does not differentiate between transactions that access multiple high-demand storage keys (i.e., unique identifiers for individual data entries) versus a single low-demand one, as long as they require the same computational effort. Addressing this discrepancy is crucial for enabling more effective parallel execution. In this work, we aim to bridge the gap between the current fee market and the need for parallel execution by exploring alternative fee market designs. To this end, we propose a framework consisting of two key components: a Gas Computation Mechanism (GCM), which quantifies the load a transaction places on the network in terms of parallelization and computation, measured in units of gas, and a Transaction Fee Mechanism (TFM), which assigns a price to each unit of gas. We additionally introduce a set of desirable properties for a GCM, propose several candidate mechanisms, and evaluate them against these criteria. Our analysis highlights two strong candidates: the weighted area GCM, which integrates smoothly with existing TFMs such as EIP‑1559 and satisfies a broad subset of the outlined properties, and the time-proportional makespan GCM, which assigns gas costs based on the context of the entire block’s schedule and, through this dependence on the overall execution outcome, captures the dynamics of parallel execution more accurately.
@inproceedings{Acilan2025TFM, author = {Acilan, Bahar and Constantinescu, Andrei and Heimbach, Lioba and Wattenhofer, Roger}, title = {{Transaction Fee Market Design for Parallel Execution}}, booktitle = {Proceedings of the 7th Conference on Advances in Financial Technologies}, pages = {23:1--23:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, isbn = {978-3-95977-400-0}, issn = {1868-8969}, year = {2025}, volume = {354}, editor = {Avarikioti, Zeta and Christin, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.23}, urn = {urn:nbn:de:0030-drops-247426}, doi = {10.4230/LIPIcs.AFT.2025.23}, annote = {Keywords: blockchain, transaction fee mechanism, parallel execution}, month = oct, } - Byzantine Stable Matching (Best Paper Award)Andrei Constantinescu, Marc Dufay, Diana Ghinea, and 1 more authorIn Proceedings of the 44th ACM Symposium on Principles of Distributed Computing, Jun 2025
In stable matching, one must find a matching between two sets of agents, commonly men and women, or job applicants and job positions. Each agent has a preference ordering over who they want to be matched with. Moreover a matching is said to be stable if no pair of agents prefer each other over their current matching. We consider solving stable matching in a distributed synchronous setting, where each agent is its own process. Moreover, we assume up to \(t_L\) agents on one side and \(t_R\) on the other side can be byzantine. After properly defining the stable matching problem in this setting, we study its solvability. When there are as many agents on each side with fully-ordered preference lists, we give necessary and sufficient conditions for stable matching to be solvable in the synchronous setting. These conditions depend on the communication model used, i.e., if parties on the same side are allowed to communicate directly, and on the presence of a cryptographic setup, i.e., digital signatures.
@inproceedings{Constantinescu2025ByzantineStableMatching, author = {Constantinescu, Andrei and Dufay, Marc and Ghinea, Diana and Wattenhofer, Roger}, title = {Byzantine Stable Matching}, year = {2025}, isbn = {9798400718854}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3732772.3733525}, doi = {10.1145/3732772.3733525}, booktitle = {Proceedings of the 44th ACM Symposium on Principles of Distributed Computing}, pages = {181--191}, numpages = {11}, keywords = {stable matching, byzantine faults, distributed protocol}, location = {Hotel Las Brisas Huatulco, Huatulco, Mexico}, series = {PODC '25}, month = jun, } - Byzantine Game Theory: Sun Tzu's BoxesAndrei Constantinescu, and Roger WattenhoferIn Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, May 2025
We introduce the Byzantine Selection Problem, living at the intersection of game theory and fault-tolerant distributed computing. Here, an event organizer is presented with a group of \(n\) agents, and wants to select \(\ell < n\) of them to form a team. For these purposes, each agent \(i\) self-reports a positive skill value \(v_i\), and a team's value is the sum of its members' skill values. Ideally, the value of the team should be as large as possible, which can be easily achieved by selecting agents with the highest \(\ell\) skill values. However, an unknown subset of at most \(t < n\) agents are byzantine and hence not to be trusted, rendering their true skill values as \(0\). In the spirit of the distributed computing literature, the identity of the byzantine agents is not random but instead chosen by an adversary aiming to minimize the value of the chosen team. Can we still select a team with good guarantees in this adversarial setting? As it turns out, deterministically, it remains optimal to select agents with the highest \(\ell\) values. Yet, if \(t \ge \ell\), the adversary can choose to make all selected agents byzantine, leading to a team of value zero. To provide meaningful guarantees, one hence needs to allow for randomization, in which case the expected value of the selected team needs to be maximized, assuming again that the adversary plays to minimize it. For this case, we provide linear-time randomized algorithms that maximize the expected value of the selected team.
@inproceedings{Constantinescu2025ByzantineBoxes, author = {Constantinescu, Andrei and Wattenhofer, Roger}, title = {Byzantine Game Theory: Sun Tzu's Boxes}, year = {2025}, isbn = {9798400714269}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, booktitle = {Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems}, pages = {519--528}, numpages = {10}, keywords = {algorithms, byzantine fault tolerance, game theory, mechanism design, robust optimization}, location = {Detroit, MI, USA}, series = {AAMAS '25}, month = may, } - Condorcet Winners and Anscombe’s Paradox Under Weighted Binary VotingCarmel Baharav, Andrei Constantinescu, and Roger WattenhoferIn Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, May 2025
We consider voting on multiple independent binary issues. In addition, a weighting vector for each voter defines how important they consider each issue. The most natural way to aggregate the votes into a single unified proposal is issue-wise majority (IWM): taking a majority opinion for each issue. However, in a scenario known as Ostrogorski’s Paradox, an IWM proposal may not be a Condorcet winner, or it may even fail to garner majority support in a special case known as Anscombe’s Paradox. We show that it is co-NP-hard to determine whether there exists a Condorcet-winning proposal even without weights. In contrast, we prove that the single-switch condition provides an Ostrogorski-free voting domain under identical weighting vectors. We show that verifying the condition can be achieved in linear time and no-instances admit short, efficiently computable proofs in the form of forbidden substructures. On the way, we give the simplest linear-time test for the voter/candidate-extremal-interval condition in approval voting and the simplest and most efficient algorithm for recognizing single-crossing preferences in ordinal voting. We then tackle Anscombe’s Paradox. Under identical weight vectors, we can guarantee a majority-supported proposal agreeing with IWM on strictly more than half of the overall weight, while with two distinct weight vectors, such proposals can get arbitrarily far from IWM. The severity of such examples is controlled by the maximum average topic weight \(\tilde{w}_{\max}\): a simple bound derived from a partition-based approach is tight on a large portion of the range \(\tilde{w}_{\max} \in (0,1)\). Finally, we extend Wagner’s rule to the weighted setting: an average majority across topics of at least \(3/4\) precludes Anscombe’s paradox from occurring.
@inproceedings{Baharav2025CondorcetWeightedAnscombe, author = {Baharav, Carmel and Constantinescu, Andrei and Wattenhofer, Roger}, title = {{Condorcet Winners and Anscombe's Paradox Under Weighted Binary Voting}}, booktitle = {Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems}, pages = {179--187}, numpages = {9}, year = {2025}, month = may, isbn = {9798400714269}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, location = {Detroit, MI, USA}, series = {AAMAS '25}, keywords = {anscombe, complexity, condorcet, forbidden substructures, multiple referenda, ostrogorski, restricted domains, single-crossing}, }
2024
- Convex Consensus with Asynchronous FallbackAndrei Constantinescu, Diana Ghinea, Roger Wattenhofer, and 1 more authorIn Proceedings of the 38th International Symposium on Distributed Computing, Madrid, Spain, Oct 2024
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.
@inproceedings{Constantinescu2024Convex, author = {Constantinescu, Andrei and Ghinea, Diana and Wattenhofer, Roger and Westermann, Floris}, title = {Convex Consensus with Asynchronous Fallback}, booktitle = {Proceedings of the 38th International Symposium on Distributed Computing, Madrid, Spain}, year = {2024}, month = oct, url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.15}, } - Brief Announcement: Unifying Partial SynchronyAndrei Constantinescu, Diana Ghinea, Jakub Sliwinski, and 1 more authorIn Proceedings of the 38th International Symposium on Distributed Computing, Madrid, Spain, Oct 2024
The distributed computing literature considers multiple options for modeling communication. Most simply, communication is categorized as either synchronous or asynchronous. Synchronous communication assumes that messages get delivered within a publicly known timeframe and that parties' clocks are synchronized. Asynchronous communication, on the other hand, only assumes that messages get delivered eventually. A more nuanced approach, or a middle ground between the two extremes, is given by the partially synchronous model, which is arguably the most realistic option. This model comes in two commonly considered flavors: (i) The Global Stabilization Time (GST) model: after an (unknown) amount of time, the network becomes synchronous. This captures scenarios where network issues are transient. (ii) The Unknown Latency (UL) model: the network is, in fact, synchronous, but the message delay bound is unknown. This work formally establishes that any time-agnostic property that can be achieved by a protocol in the UL model can also be achieved by a (possibly different) protocol in the GST model. By time-agnostic, we mean properties that can depend on the order in which events happen but not on time as measured by the parties. Most properties considered in distributed computing are time-agnostic. The converse was already known, even without the time-agnostic requirement, so our result shows that the two network conditions are, under one sensible assumption, equally demanding.
@inproceedings{Constantinescu2024KobisClocks, author = {Constantinescu, Andrei and Ghinea, Diana and Sliwinski, Jakub and Wattenhofer, Roger}, title = {Brief Announcement: Unifying Partial Synchrony}, booktitle = {Proceedings of the 38th International Symposium on Distributed Computing, Madrid, Spain}, year = {2024}, month = oct, url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.43}, } - Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic GamesAndrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, and 2 more authorsIn Proceedings of the 51st International Colloquium on Automata, Languages and Programming, Tallinn, Estonia, Jul 2024
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}, url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.48}, selected = true } - Unravelling Expressive Delegations: Complexity and Normative AnalysisGiannis Tyrovolas, Andrei Constantinescu, and Edith ElkindIn Proceedings of the 38th AAAI Conference on Artificial Intelligence, Vancouver, Canada, Feb 2024
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}, url = {https://ojs.aaai.org/index.php/AAAI/article/view/28853}, booktitle = {Proceedings of the 38th AAAI Conference on Artificial Intelligence, Vancouver, Canada}, year = {2024}, month = feb, }
2023
- A Fair and Resilient Decentralized Clock Network for Transaction OrderingAndrei Constantinescu, Diana Ghinea, Lioba Heimbach, and 2 more authorsIn Proceedings of the 27th International Conference on Principles of Distributed Systems, Tokyo, Japan, Dec 2023
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}, } - Stable Dinner Party Seating Arrangements (Best Paper Award)Damien Berriaud, Andrei Constantinescu, and Roger WattenhoferIn Proceedings of the 19th Conference on Web and Internet Economics, Shanghai, China, Dec 2023
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 } - Recovering Single-Crossing Preferences From Approval BallotsAndrei Constantinescu, and Roger WattenhoferIn Proceedings of the 19th Conference on Web and Internet Economics, Shanghai, China, Dec 2023
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}, } - Computing the Best Policy That Survives a VoteAndrei Constantinescu, and Roger WattenhoferIn Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, London, United Kingdom, Jun 2023
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
- Voting in Two-Crossing ElectionsAndrei Constantinescu, and Roger WattenhoferIn Proceedings of the 31st International Joint Conference on Artificial Intelligence, Vienna, Austria, Jul 2022
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
- Proportional Representation under Single-Crossing Preferences RevisitedAndrei Constantinescu, and Edith ElkindIn Proceedings of the 35th AAAI Conference on Artificial Intelligence, Virtual, May 2021
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 }