Luke Riley

Terry R. Payne, Luke Riley

A key challenge in distributed coalition formation within characteristic function games is determining how to allocate the calculation of coalition values across a set of agents. The number of possible coalitions grows exponentially with the number of agents, and existing distributed approaches may produce uneven or redundant allocations, or assign coalitions to agents that are not themselves members. In this article, we present the \emph{Necklace-based Distributed Coalition Algorithm} (N-DCA), a communication-free algorithm in which each agent independently determines its own coalition value calculation allocation using only its identifier and the total number of agents. The approach builds on the notion of Increment Arrays (IAs), for which we develop a complete mathematical framework: equivalence classes under circular shifts, periodic IAs, and a rotated designation scheme with formal load-balance guarantees (tight bounds). We establish a bijection between canonical representative IAs and two-colour combinatorial necklaces, enabling the use of efficient necklace generation algorithms to enumerate allocations in constant amortised time. N-DCA is, to the best of our knowledge, the only distributed coalition value calculation algorithm for unrestricted characteristic function games to provably satisfy five desirable properties: no inter-agent communication, equitable allocation, no redundancy, balanced load, and self-interest. An empirical evaluation against DCVC (Rahwan and Jennings 2007) demonstrates that, although DCVC is faster by a constant factor, this difference becomes negligible under realistic characteristic-function evaluation costs, while N-DCA offers advantages in working memory, scalability, and the self-interest guarantee.

Mohammed Alsadi, Matthew Casey, Constantin Catalin Dragan et al.

Online voting for independent elections is generally supported by trusted election providers. Typically these providers do not offer any way in which a voter can verify their vote, so the providers are trusted with ballot privacy and ensuring correctness. Despite the desire to offer online voting for political elections, this lack of transparency and verifiability is often seen as a significant barrier to the large-scale adoption of online elections. Adding verifiability to an online election increases transparency and integrity, allowing voters to verify that their vote has been recorded correctly and included in the tally. However, replacing existing online systems with those that provide verifiable voting requires new algorithms and code to be deployed, and this presents a significant business risk to commercial election providers. In this paper we present the first step in an incremental approach which minimises the business risk but demonstrates the advantages of verifiability, by developing an implementation of key elements of a Selene-based verifiability layer and adding it to an operational online voting system. Selene is a verifiable voting protocol that uses trackers to enable voters to confirm that their votes have been captured correctly while protecting voter anonymity. This results in a system where even the election authority running the system cannot change the result in an undetectable way, and gives stronger guarantees on the integrity of the election than were previously present. We explore the challenges presented by adding a verifiability layer to an operational system. We describe the results of two initial trials, which obtained that survey respondents found this form of verifiability easy to use and that they broadly appreciated it. We conclude by outlining the further steps in the road-map towards the deployment of a fully trustworthy online voting system.