Deterministic system

Formally, the output of an algorithm or decision procedure is 'determinate' if and only if it is a pure function of the input.

Strictly, determinate applies only to invocations: if, regardless of the input, the output of an algorithm is always determinate whenever the algorithm terminates, then the algorithm is 'deterministic' if and only if its termination is also determinate. (This latter condition is trivially satisfied if the algorithm always terminates.)

Voting algorithms are intended always to terminate; if so, the algorithm is deterministic if and only if the output is always determinate.

For example: suppose an odd number of co-workers share an office, and that each co-worker 'votes' for (ie expresses a preference for) the office temperature to be maintained at some level they each find comfortable. The preferences are ordered and the median value is declared the 'winner'. Here, other than in the degenerate case of no votes being cast at all, the outcome is always determinate. Notice too that, with an odd number of 'electors' all voting, it is not possible to vote tactically: no purpose is served by voting other than for the temperature level one wishes to have prevail.

Whenever someone joins or leaves the team, the parity (odd- or even-ness) of the voting population flips; abstentions can also result in an even number of votes being tallied. In this case, the mathematical median can be shifted by expressing an insincere preference, so immunity from tactical voting is lost.

Whenever an even number of votes are cast and the two middle-values differ, tactical immunity can be restored by flipping a coin to decide which of the two values 'wins'. However, this procedure is no longer deterministic.

Determinism can be restored without loss of tactical immunity by having each elector independently choose a cryptographic nonce (one-time value) and writing it down on their ballot paper; then, a cryptographic hash of all the nonces (thereby amounting to a pseudo-random value) can substitute for the flipped coin. Even if all but one of the electors attempt to collude to deprive the victim of a preference, the victim can thwart them by choosing a nonce that is not predictable and is kept secret until all the ballots have been collected.

Determinism is an important axiom and/or assumption of several well-known impossibility theora, including Arrows; the above example illustrates that its significance is perhaps more subtle than first appears.