A Semantic Game (SG) is a two-party debate of the truth of a particular interpreted logic sentence, or claim for short. The debate is structured as a two-person game with two distinguished participants, the verifier and the falsifier. The party taking the position that the underlying claim is true (respectively false) becomes the verifier (respectively falsifier). The rules of the game are derived from the syntax of the underlying sentence such that the game gives a meaning to the underlying claim in the sense that if there is a winning strategy for the verifier (respectively falsifier) then the underlying claim is true (respectively false).
Semantic games are best explained through an analogy to formal debates between a proponent and opponent. A decision has to be made about a claim. A debate has the purpose of testing whether the claim is indeed true. We have two debate participants whom we ask the question: is a given claim true?
Let's assume one participant says yes and the other says no. We choose the participant who said "yes" as proponent and the participant who said "no" as opponent. They engage in the debate following a defined protocol. If the proponent (opponent) loses she has made a mistake and the opponent (proponent) participant wins a point.
Let's assume both participants make the same choice, e.g., they both say "yes". Then we choose a participant to be proponent and we force another participant to be the opponent, taking on the role of devil's advocate. If the opponent wins, the proponent must have made a mistake and the opponent wins a point. If the proponent wins, we cannot blame the opponent because she was forced.
Here is the correspondence to semantic games:
Debate Semantic Game proposition claim proponent verifier opponent falsifier winning strategy for proponent winning strategy for verifier dialog dialog, game mistake mistake, contradiction debating rules semantic game rules debate depends on proposition game depends on claim
First Alice and Bob analyze the claim and they come up with a defense strategy for the side they take. The defense strategy might be vague and might not work. The result of the analysis is a truth value: true means verifier, false means falsifier.
aA = analyse(Alice,H(c0)) aB = analyse(Bob,H(c0))
If Alice and Bob are taking different sides, they play a regular semantic game SG(H(c0),verifier,falsifier).
if aA and !aB then r=SG(H(c0),Alice,Bob) if !aA and aB then r=SG(H(c0),Bob,Alice)
If Alice and Bob are taking the same sides, they play a semantic game where one player is forced. The forced party is determined randomly. In SG1 the verifier is forced. In SG2 the falsifier is forced.
if !aA and !aB then r1=SG1(H(c0),Alice,Bob) if aA and aB then r2=SG2(H(c0),Alice,Bob)Being a forced player is not bad. You can never lose as the forced player and you might be able to score a point by bringing the verifier into a contradiction.
Possible semantic games:
falsifier c=1 verifier n0=9 falsifier n=10 0 <= 2*n < c*n^2 0 <= 20 < 100: true verifier wins.
falsifier c=10^-3 verifier n0=-1+ 3*10^3 falsifier n=3*10^3 0 <= 6*10^3 < 9*10^3: true verifier wins.
Possible semantic game: crossover = 2.08 * 10^65 for c=1, n0=1000
verifier provides c=1,n0=1000 falsifier provides large n = 2.08 * 10^66 falsifier chooses f(n) <= c*g(n) which is false so the falsifier wins. Use: plot n^0.1 and 1000+(log(n))^3 for n from 1..10^66
Note that there are quantifiers hidden in O(n^c)? What is the detailed protocol? Verifier provides M and c > 0 and n0 > 0. Falsifier provides input i larger than size n0. M is run on i.
How small can we make c?
Which side do you take on this claim? What is your defense strategy?