Source author record

Mike Paterson

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

5works
10topics
4close collaborators

Published work

5 publications

preprint2021arXiv

More about Exact Slow kk-Nim

Given nn piles of tokens and a positive integer k≤nk \leq n, the game Nimn,=k1^1_{n, =k} of exact slow kk-Nim is played as follows. Two players move alternately. In each move, a player chooses exactly kk non-empty piles and removes one token from each of them. A player whose turn it is to move but has no move loses (if the normal version of the game is played, and wins if it is the misére version). In Integers 20 (2020) 1-19, Gurvich et al gave an explicit formula for the Sprague-Grundy function of Nim4,=21^1_{4, =2}, for both its normal and misére version. Here we extend this result and obtain an explicit formula for the P-positions of the normal version of Nim5,=21^1_{5, =2} and Nim6,=21^1_{6, =2}.

preprint2020arXiv

Globe-hopping

We consider versions of the grasshopper problem (Goulko and Kent, 2017) on the circle and the sphere, which are relevant to Bell inequalities. For a circle of circumference 2π2π, we show that for unconstrained lawns of any length and arbitrary jump lengths, the supremum of the probability for the grasshopper's jump to stay on the lawn is one. For antipodal lawns, which by definition contain precisely one of each pair of opposite points and have length ππ, we show this is true except when the jump length ϕϕ is of the form πpqπ\frac{p}{q} with p,qp,q coprime and pp odd. For these jump lengths we show the optimal probability is 1−1/q1 - 1/q and construct optimal lawns. For a pair of antipodal lawns, we show that the optimal probability of jumping from one onto the other is 1−1/q1 - 1/q for p,qp,q coprime, pp odd and qq even, and one in all other cases. For an antipodal lawn on the sphere, it is known (Kent and Pitalúa-García, 2014) that if ϕ=π/qϕ= π/q, where q∈Nq \in \mathbb N, then the optimal retention probability of 1−1/q1-1/q for the grasshopper's jump is provided by a hemispherical lawn. We show that in all other cases where 0<ϕ<π/20<ϕ< π/2, hemispherical lawns are not optimal, disproving the hemispherical colouring maximality hypotheses (Kent and Pitalúa-García, 2014). We discuss the implications for Bell experiments and related cryptographic tests.

preprint2014arXiv

False-Name Manipulations in Weighted Voting Games

Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. A players power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms. Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index, we describe a new paradox, which we term the Annexation Non-monotonicity Paradox.

preprint2010arXiv

Computing voting power in easy weighted voting games

Weighted voting games are ubiquitous mathematical models which are used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. They model situations where agents with variable voting weight vote in favour of or against a decision. A coalition of agents is winning if and only if the sum of weights of the coalition exceeds or equals a specified quota. The Banzhaf index is a measure of voting power of an agent in a weighted voting game. It depends on the number of coalitions in which the agent is the difference in the coalition winning or losing. It is well known that computing Banzhaf indices in a weighted voting game is NP-hard. We give a comprehensive classification of weighted voting games which can be solved in polynomial time. Among other results, we provide a polynomial (O(k(nk)k)O(k{(\frac{n}{k})}^k)) algorithm to compute the Banzhaf indices in weighted voting games in which the number of weight values is bounded by kk.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.