Deterministic system

From electowiki
(Redirected from Determinate)
Wikipedia has an article on:

According to Wikipedia:[1]

In mathematics, computer science and physics, a deterministic system is a system in which no randomness is involved in the development of future states of the system.[2] A deterministic model will thus always produce the same output from a given starting condition or initial state.[3]

Formally, the output of a given invocation of an algorithm or decision procedure is 'determinate' if and only if it is a pure function of the input. The contrasting term is 'indeterminate'.

Strictly, the term 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. Some voting systems include an element of randomness; for example, a coin toss in the event of a tie. If the output (or termination) is indeterminate for any input, the algorithm is non-deterministic.

Example

Suppose an odd number of co-workers share an office, and that each co-worker 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 deterministic. 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.

Randomness

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 their chosen 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 Arrow's; the above example illustrates that its significance is perhaps more subtle than first appears.

References