Nimrod Talmon

Ehud Shapiro, Nimrod Talmon

We propose a framework for the fair democratic governance of federated digital communities that form and evolve dynamically, where small groups self-govern and larger groups are represented by assemblies selected via sortition. Prior work addressed static fairness conditions; here, we formalize a dynamic setting where federations evolve over time through communities forming, joining, and splitting, in all directions -- bottom-up, top-down, and middle-out -- and adapt the fairness guarantees. The main technical challenge is reconciling integral seat allocations with dynamic, overlapping federations, so that child communities always meet their persistent floors while long-run averages converge to proportional fairness. Overcoming these challenges, we introduce a protocol that ensures fair participation and representation both persistently (at all times) and eventually (in the limit after stabilization), extending the static fairness properties to handle structural changes. Prior work shows how grassroots federations can be specified via atomic transactions among assembly members, Constitutional Consensus can realize these transactions and the democratic processes leading to them, and Constitutional Governance in Metric Spaces lets a community govern itself and amend its own constitution. Together, these works form a comprehensive design for an egalitarian, fairly governed, large-scale decentralized sovereign digital community platform.

Ehud Shapiro, Nimrod Talmon

While the physical lives of many of us are in democracies (one person, one vote - e.g., the EU and the US), our digital lives are mostly in autocracies (one person, all votes - e.g., Facebook). Cryptocurrencies promise liberation but stop short, at plutocracy (one coin, one vote). What would it take for us to live our digital lives in a digital democracy? This paper offers a vision, a theoretical framework, and an architecture for a grassroots network of autonomous, people-owned, people-operated, and people-governed digital communities, namely a grassroots democratic metaverse. It also charts a roadmap towards realizing it, and identifies unexplored territory for further research.

Eyal Briman, Ehud Shapiro, Nimrod Talmon

The challenge of finding compromises between agent proposals is fundamental to AI subfields such as argumentation, mediation, and negotiation. Building on this tradition, Elkind et al. (2021) introduced a process for coalition formation that seeks majority-supported proposals preferable to the status quo, using a metric space where each agent has an ideal point. A crucial step in this process involves identifying compromise proposals around which agent coalitions can unite. How to effectively find such compromise proposals remains an open question. We address this gap by formalizing a model that incorporates agent bounded rationality and uncertainty, and by developing AI methods to generate compromise proposals. We focus on the domain of collaborative document writing, such as the democratic drafting of a community constitution. Our approach uses natural language processing techniques and large language models to induce a semantic metric space over text. Based on this space, we design algorithms to suggest compromise points likely to receive broad support. To evaluate our methods, we simulate coalition formation processes and show that AI can facilitate large-scale democratic text editing, a domain where traditional tools are limited.

Oghenekaro Elem, Nimrod Talmon

Decentralized protocols claim immutable, rule-based execution, yet many embed emergency mechanisms such as chain-level freezes, protocol pauses, and account quarantines. These overrides are crucial for responding to exploits and systemic failures, but they expose a core tension: when does intervention preserve trust and when is it perceived as illegitimate discretion? With approximately \$10 billion in technical exploit losses potentially addressable by onchain intervention (2016-2026), the design of these mechanisms has high practical stakes, but current approaches remain ad hoc and ideologically charged. We address this gap by developing a Scope $\times$ Authority taxonomy that maps the design space of emergency architectures along two dimensions: the precision of the intervention and the concentration of trigger authority. We formalize the resulting tradeoffs of standing centralization cost, containment speed, and collateral disruption as a stochastic decision support framework, and derive three empirical hypotheses from it. Assessing the framework against 705 documented exploit incidents, we find that containment time varies systematically by authority type, that losses follow a heavy-tailed distribution ($α\approx 1.33$) concentrating risk in rare catastrophic events, and that community sentiment plausibly modulates the effective cost of maintaining intervention capability. Using scope breadth as a practical proxy for blast potential, we also find that narrower interventions (Account/Module) do not underperform broader ones (Protocol/Network) on containment success and are slightly faster at the median, giving partial empirical support to the scope-blast hypothesis. The analysis yields design guidance for emergency governance and reframes the problem as one of engineering tradeoffs rather than ideological debate.

Ehud Shapiro, Nimrod Talmon

Computational social choice and algorithmic decision theory offer rich aggregation theory but no end-to-end, polynomial-time process for egalitarian self-governance: prior work treats aggregation, deliberation, amendment, and consensus in isolation, and key metric-space aggregators are NP-hard. We propose constitutional governance in metric spaces, integrating these stages into one polynomial-time process. The constitution assigns, per amendable component, a metric space, aggregation rule, and supermajority threshold. Each member submits an ideal element -- both vote and personal proposal. Any member may then submit a public proposal carrying supermajority public support under the revealed votes -- sourced from coalition deliberation, optimization, or AI mediation. The constitutional rule scores proposals against the status quo, adopting the supported proposal of positive maximal score (else retaining the status quo); the same rule, possibly with a higher threshold, amends the constitution itself. We develop the generalised median as the worked rule, establish framework-level guarantees, prove no misreport weakly dominates sincere voting, and study the compromise gap between best peak and unconstrained optimum -- zero in one dimension, bounded in general, narrowed in simulation by a simple heuristic. We instantiate the framework on seven canonical settings; the mean appears as a utilitarian alternative in the appendix. By unifying metric-space aggregation, reality-aware social choice, supermajority amendment, constitutional consensus, deliberative coalition formation, and AI mediation, this work delivers a comprehensive solution to the constitutional democratic governance of digital communities and organisations.

Zahi Mizrahi, Shai Berkovitz, Nimrod Talmon et al.

Keeping track of how lawmakers vote is essential for government transparency. While many parliamentary voting records are available online, they are often difficult to interpret, making it challenging to understand legislative behavior across parliaments and predict voting outcomes. Accurate prediction of votes has several potential benefits, from simplifying parliamentary work by filtering out bills with a low chance of passing to refining proposed legislation to increase its likelihood of approval. In this study, we leverage advanced machine learning and data analysis techniques to develop a comprehensive framework for predicting parliamentary voting outcomes across multiple legislatures. We introduce the Voting Prediction Framework (VPF) - a data-driven framework designed to forecast parliamentary voting outcomes at the individual legislator level and for entire bills. VPF consists of three key components: (1) Data Collection - gathering parliamentary voting records from multiple countries using APIs, web crawlers, and structured databases; (2) Parsing and Feature Integration - processing and enriching the data with meaningful features, such as legislator seniority, and content-based characteristics of a given bill; and (3) Prediction Models - using machine learning to forecast how each parliament member will vote and whether a bill is likely to pass. The framework will be open source, enabling anyone to use or modify the framework. To evaluate VPF, we analyzed over 5 million voting records from five countries - Canada, Israel, Tunisia, the United Kingdom and the USA. Our results show that VPF achieves up to 85% precision in predicting individual votes and up to 84% accuracy in predicting overall bill outcomes. These findings highlight VPF's potential as a valuable tool for political analysis, policy research, and enhancing public access to legislative decision-making.

Carter Blair, Ben Armstrong, Shiri Alouf-Heffetz et al.

A primary goal of online deliberation platforms is to identify ideas that are broadly agreeable to a community of users through their expressed preferences. Yet, consensus elicitation should ideally extend beyond the specific statements provided by users and should incorporate the relative salience of particular topics. We address this issue by modelling consensus as an interval in a one-dimensional opinion space derived from potentially high-dimensional data via embedding and dimensionality reduction. We define an objective that maximizes expected agreement within a hypothesis interval where the expectation is over an underlying distribution of issues, implicitly taking into account their salience. We propose an efficient Empirical Risk Minimization (ERM) algorithm and establish PAC-learning guarantees. Our initial experiments demonstrate the performance of our algorithm and examine more efficient approaches to identifying optimal consensus regions. We find that through selectively querying users on an existing sample of statements, we can reduce the number of queries needed to a practical number.

Stanisław Szufa, Niclas Boehmer, Robert Bredereck et al.

Our main contribution is the introduction of the map of elections framework. A map of elections consists of three main elements: (1) a dataset of elections (i.e., collections of ordinal votes over given sets of candidates), (2) a way of measuring similarities between these elections, and (3) a representation of the elections in the 2D Euclidean space as points, so that the more similar two elections are, the closer are their points. In our maps, we mostly focus on datasets of synthetic elections, but we also show an example of a map over real-life ones. To measure similarities, we would have preferred to use, e.g., the isomorphic swap distance, but this is infeasible due to its high computational complexity. Hence, we propose polynomial-time computable positionwise distance and use it instead. Regarding the representations in 2D Euclidean space, we mostly use the Kamada-Kawai algorithm, but we also show two alternatives. We develop the necessary theoretical results to form our maps and argue experimentally that they are accurate and credible. Further, we show how coloring the elections in a map according to various criteria helps in analyzing results of a number of experiments. In particular, we show colorings according to the scores of winning candidates or committees, running times of ILP-based winner determination algorithms, and approximation ratios achieved by particular algorithms.

Itay Asher Zimet, Shiri Alouf-Heffetz, Nimrod Talmon

Purpose: Multiwinner voting rules typically require full knowledge of voter preferences, which becomes impractical in large-scale or attention-limited settings. This paper investigates how accurately a winning committee can be approximated when voter preferences are elicited using a limited budget of structured queries. Methods: We introduce a query-based framework for multiwinner elections in which voter preferences are elicited through refinement queries over subsets of candidates under a limited budget. We analyse several cost functions that model the cognitive effort needed to answer such queries, propose axiomatic properties for evaluating them, and experimentally evaluate simple query-based committee selection rules across multiple election models. Results: Experimental results show that strategies based on recursively splitting candidate sets provide the best trade-off between elicitation cost and committee accuracy. Across several statistical models, these strategies approximate the outcome of k-Borda elections significantly more efficiently than alternative query types. Conclusion: The results demonstrate that well-designed query strategies can substantially reduce the amount of preference information required while still producing high-quality committee outcomes, suggesting that query-based elicitation is a promising approach for scalable multiwinner decision-making.

Eyal Briman, Ehud Shapiro, Nimrod Talmon

The challenge of finding compromises between agent proposals is fundamental to AI sub-fields such as argumentation, mediation, and negotiation. Building on this tradition, Elkind et al. (2021) introduced a process for coalition formation that seeks majority-supported proposals preferable to the status quo, using a metric space where each agent has an ideal point. The crucial step in this iterative process involves identifying compromise proposals around which agent coalitions can unite. How to effectively find such compromise proposals, however, remains an open question. We address this gap by formalizing a holistic model that encompasses agent bounded rationality and uncertainty and developing AI models to generate such compromise proposals. We focus on the domain of collaboratively writing text documents -- e.g., to enable the democratic creation of a community constitution. We apply NLP (Natural Language Processing) techniques and utilize LLMs (Large Language Models) to create a semantic metric space for text and develop algorithms to suggest suitable compromise points. To evaluate the effectiveness of our algorithms, we simulate various coalition formation processes and demonstrate the potential of AI to facilitate large-scale democratic text editing, such as collaboratively drafting a constitution, an area where traditional tools are limited.

Lior Ashkenazy, Nimrod Talmon

Attention-Aware Social Choice tackles the fundamental conflict faced by some agent communities between their desire to include all members in the decision making processes and the limited time and attention that are at the disposal of the community members. Here, we investigate a combination of two techniques for attention-aware social choice, namely Natural Language Processing (NLP) and Sampling. Essentially, we propose a system in which each governance proposal to change the status quo is first sent to a trained NLP model that estimates the probability that the proposal would pass if all community members directly vote on it; then, based on such an estimation, a population sample of a certain size is being selected and the proposal is decided upon by taking the sample majority. We develop several concrete algorithms following the scheme described above and evaluate them using various data, including such from several Decentralized Autonomous Organizations (DAOs).

Ariel Rosenfeld, Nimrod Talmon

Participatory Budgeting (PB) is a process in which voters decide how to allocate a common budget; most commonly it is done by ordinary people -- in particular, residents of some municipality -- to decide on a fraction of the municipal budget. From a social choice perspective, existing research on PB focuses almost exclusively on designing computationally-efficient aggregation methods that satisfy certain axiomatic properties deemed "desirable" by the research community. Our work complements this line of research through a user study (N = 215) involving several experiments aimed at identifying what potential voters (i.e., non-experts) deem fair or desirable in simple PB settings. Our results show that some modern PB aggregation techniques greatly differ from users' expectations, while other, more standard approaches, provide more aligned results. We also identify a few possible discrepancies between what non-experts consider \say{desirable} and how they perceive the notion of "fairness" in the PB context. Taken jointly, our results can be used to help the research community identify appropriate PB aggregation methods to use in practice.

Piotr Faliszewski, Piotr Skowron, Nimrod Talmon

We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) and the bribery actions are limited to: adding an approval to a vote, deleting an approval from a vote, or moving an approval within a vote from one candidate to the other. We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV). We find the landscape of complexity results quite rich, going from polynomial-time algorithms through NP-hardness with constant-factor approximations, to outright inapproximability. Moreover, in general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee (i.e., adding approvals only for this preferred candidate, or moving approvals only to him or her). We also study parameterized complexity of our problems, with a focus on parameterizations by the numbers of voters or candidates.

Pallavi Jain, Krzysztof Sornat, Nimrod Talmon et al.

We study a generalization of the standard approval-based model of participatory budgeting (PB), in which voters are providing approval ballots over a set of predefined projects and -- in addition to a global budget limit, there are several groupings of the projects, each group with its own budget limit. We study the computational complexity of identifying project bundles that maximize voter satisfaction while respecting all budget limits. We show that the problem is generally intractable and describe efficient exact algorithms for several special cases, including instances with only few groups and instances where the group structure is close to be hierarchical, as well as efficient approximation algorithms. Our results could allow, e.g., municipalities to hold richer PB processes that are thematically and geographically inclusive.

Piotr Faliszewski, Nimrod Talmon

We define and study a general framework for approval-based budgeting methods and compare certain methods within this framework by their axiomatic and computational properties. Furthermore, we visualize their behavior on certain Euclidean distributions and analyze them experimentally.

Gal Shahaf, Ehud Shapiro, Nimrod Talmon

Sybil attacks, in which fake or duplicate identities (\emph{sybils}) infiltrate an online community, pose a serious threat to such communities, as they might tilt community-wide decisions in their favor. While the extensive research on sybil identification may help keep the fraction of sybils in such communities low, it cannot however ensure their complete eradication. Thus, our goal is to enhance social choice theory with effective group decision mechanisms for communities with bounded sybil penetration. Inspired by Reality-Aware Social Choice, we use the status quo as the anchor of \emph{sybil resilience}, characterized by \emph{sybil safety} -- the inability of sybils to change the status quo against the will of the genuine agents, and \emph{sybil liveness} -- the ability of the genuine agents to change the status quo against the will of the sybils. We consider the social choice settings of deciding on a single proposal, on multiple proposals, and on updating a parameter. For each, we present social choice rules that are sybil-safe and, under certain conditions, satisfy sybil-liveness.

Palash Dey, Nimrod Talmon, Otniel van Handel

We consider elections where the voters come one at a time, in a streaming fashion, and devise space-efficient algorithms which identify an approximate winning committee with respect to common multiwinner proportional representation voting rules; specifically, we consider the Approval-based and the Borda-based variants of both the Chamberlin-- ourant rule and the Monroe rule. We complement our algorithms with lower bounds. Somewhat surprisingly, our results imply that, using space which does not depend on the number of voters it is possible to efficiently identify an approximate representative committee of fixed size over vote streams with huge number of voters.

Tomer Ashur, Orr Dunkelman, Nimrod Talmon

An election is a process through which citizens in liberal democracies select their governing bodies, usually through voting. For elections to be truly honest, people must be able to vote freely without being subject to coercion; that is why voting is usually done in a private manner. In this paper we analyze the security offered by a paper-ballot voting system that is used in Israel, as well as in several other countries around the world. we provide an algorithm which, based on publicly available information, breaks the privacy of the voters participating in such elections. Simulations based on real data collected in Israel show that our algorithm performs well, and can correctly recover the vote of up to 96% of the voters.

Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier et al.

Given an election, a preferred candidate p, and a budget, the SHIFT BRIBERY problem asks whether p can win the election after shifting p higher in some voters' preference orders. Of course, shifting comes at a price (depending on the voter and on the extent of the shift) and one must not exceed the given budget. We study the (parameterized) computational complexity of S HIFT BRIBERY for multiwinner voting rules where winning the election means to be part of some winning committee. We focus on the well-established SNTV, Bloc, k-Borda, and Chamberlin-Courant rules, as well as on approximate variants of the Chamberlin-Courant rule, since the original rule is NP-hard to compute. We show that SHIFT BRIBERY tends to be harder in the multiwinner setting than in the single-winner one by showing settings where SHIFT BRIBERY is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. Moreover, we show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin-Courant rule sometimes affects the complexity of SHIFT BRIBERY.

Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier et al.

We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.