local rational = require( "Module:Rational" ) local yesno = require( "Module:Yesno" ) local G = require( "Module:G" )
local T_NUMBER = 0 local T_STRING = 1 local T_SYMBOL = 2 local T_LBRACE = 3 local T_RBRACE = 4 local T_COMMA = 5 local T_EOF = 6
local p = {}
-- NFG parsing based on https://github.com/gambitproject/gambit/blob/master/library/src/file.cc
p._nfgLexer = function(nfg) local i = 1 local line = 1 local len = string.len( nfg ) local fail = function (reason) if reason == nil then reason = "Invalid NFG syntax" end error(reason .. " at line " .. line .. "\nc=" .. string.sub( nfg, i, i ) .. " around=" .. string.sub(nfg, i-5, i+5)) end local currToken = nil local nextToken = nil local prevToken = nil local step = function () -- Consume any space chars local _, r, spaces = string.find( nfg, "(%s+)", i ) if r ~= nil then i = r+1 for space in string.gmatch( spaces, "\n" ) do line = line+1 end end
-- End of string if i > len then return { T_EOF, "" } end
local c = string.sub( nfg, i, i ) if c == "{" then i = i+1 return { T_LBRACE, c } elseif c == "}" then i = i+1 return { T_RBRACE, c } elseif c == "," then i = i+1 return { T_COMMA, c } elseif string.match(c, "%d") or c == "-" or c == "+" or c == "." then -- Number local _, r = string.find( nfg, "^[-+]?%d*", i ) if r == nil then fail("Invalid number") end
if string.sub( nfg, r+1, r+1 ) == "." then local p, q = string.find( nfg, "^%d+", r+2 ) if p == nil then fail("Decimal with no digits") end r = q elseif ((c == "-" or c == "+") and i == r) then fail("Sign with no number") end
if string.match( nfg, "^[eE]", r+1 ) then local p, q = string.find( nfg, "^%d+", r+2 ) if p == nil then fail("Invalid exponent") end r = q end
if string.sub( nfg, r+1, r+1 ) == "/" then local p, q = string.find( nfg, "^%d+", r+2 ) if p == nil then fail("Invalid quotient") end r = q end
local ret = string.sub( nfg, i, r ) i = r+1 return { T_NUMBER, ret } elseif c == '"' then -- String if string.sub( nfg, i+1, i+1 ) == '"' then i = i+2 return { T_STRING, "" } else local l, r = string.find( nfg, '^".-[^\\]"', i) if l == nil then fail("Invalid string") end i = r+1 return { T_STRING, string.sub(nfg, l+1, r-1):gsub('\\"', '"') } end else -- Symbol, consume all non-space chars local l, r = string.find( nfg, "^%S+", i ) if r ~= nil then i = r+1 return { T_SYMBOL, string.sub( nfg, l, r ) } else return { T_EOF, "" } end end end
return { peek = function () if nextToken == nil then nextToken = step() end return nextToken end, next = function () if currToken ~= nil then prevToken = currToken end if nextToken ~= nil then currToken = nextToken nextToken = nil else currToken = step() end return currToken end, curr = function () return currToken end, prev = function () return prevToken end, } end
p._ratParse = function (s) local r = mw.text.split(s, "/") n = r[1]+0 d = (r[2] ~= nil and r[2] ~= 0) and (r[2]+0) or 1 return rational(n,d) end
p._nfgParse = function (nfg) local lexer = p._nfgLexer(nfg) local fail = function (reason) if reason == nil then reason = "Invalid NFG" end curr = lexer.curr() error(reason .. " on token type " .. curr[1] .. ": " .. curr[2]) end local game = { players = {}, outcomes = {}, map = {}, strats = {}, comment = "", } local token
-- Heading token = lexer.next() if token[1] ~= T_SYMBOL or token[2] ~= "NFG" then fail("NFG missing from start of NFG") end token = lexer.next() if token[1] ~= T_NUMBER or token[2] ~= "1" then fail("NFG version 1 not specified") end token = lexer.next() if token[1] ~= T_SYMBOL or token[2] ~= "R" then fail("Number type R not specified") end token = lexer.next() if token[1] ~= T_STRING then fail("Title missing from header") end game.title = token[2]
-- Players if lexer.next()[1] ~= T_LBRACE then fail("Expecting { before players") end while lexer.peek()[1] == T_STRING do table.insert( game.players, lexer.next()[2] ) end if #game.players ~= 2 then fail("Game has " .. #game.players .. " players, only 2 are supported") end if lexer.next()[1] ~= T_RBRACE then fail("Expecting } after players") end
-- Strats if lexer.next()[1] ~= T_LBRACE then fail("Expecting { before strategies") end for i, p in ipairs(game.players) do if lexer.next()[1] ~= T_LBRACE then fail("Expecting { for player " .. i .. " strategies") end game.strats[i] = {} while lexer.peek()[1] == T_STRING do table.insert(game.strats[i], lexer.next()[2]) end if lexer.next()[1] ~= T_RBRACE then fail("Expecting } for player " .. i .. " strategies") end end if lexer.next()[1] ~= T_RBRACE then fail("Expecting } after strategies") end
-- Comment if lexer.peek()[1] == T_STRING then game.comment = lexer.next()[2] end
-- Outcomes if lexer.next()[1] ~= T_LBRACE then fail("Expecting { before outcomes") end while lexer.next()[1] == T_LBRACE do if lexer.next()[1] ~= T_STRING then fail("Expecting string for outcome") end local outcome = {} for i = 1,2 do token = lexer.next() if token[1] == T_COMMA then token = lexer.next() end if token[1] ~= T_NUMBER then fail("Expecting number for outcome") end table.insert(outcome, p._ratParse(token[2])) end if (outcome[1] + outcome[2]).num ~= 0 then local sum = outcome[1] + outcome[2] fail("Expecting only zero-sum outcomes, " .. outcome[1].num .. "/" .. outcome[1].den .. " - " .. outcome[2].num .. "/" .. outcome[2].den .. " = " .. sum.num .. "/" .. sum.den ) end if lexer.next()[1] ~= T_RBRACE then fail("Expecting } after outcome") end table.insert(game.outcomes, outcome[1]) end if lexer.prev()[1] ~= T_RBRACE then fail("Expecting } after outcomes") end
-- If an outcome hasn't been filled in, it has index 0 -- Hopefully making a 0-indexed array here doesn't break anything >,< game.outcomes[0] = rational(0,1)
-- Outcome mapping for j,p2 in ipairs(game.strats[2]) do local row = {} for i,p1 in ipairs(game.strats[1]) do if lexer.next()[1] ~= T_NUMBER then fail("Expecting number for outcome index") end local index = lexer.curr()[2] + 0 if game.outcomes[index] == nil then fail("Index to undefined outcome") end table.insert(row, index) end table.insert(game.map, row) end
return game end
p.render = function(frame) local page = frame.args[1] local collapsed = yesno( frame.args["collapsed"] ) return p._render(page, collapsed) end
p._render = function(page, collapsed) -- All .gbt files belong in the Mixup: namespace local title = mw.title.makeTitle('Mixup', page) local gbt = title:getContent() if gbt == nil then error("Mixup:" .. page .. " doesn't exist", 0) end
local nfg = string.match(gbt, "<nfgfile[^>]->(.-)</nfgfile[^>]->") local game = p._nfgParse(nfg) --mw.logObject(game)
-- -- Create HTML for payoffs table -- local h_payoffs = mw.html.create('table') local h_payoffs_cols = mw.html.create('tr'):node( mw.html.create('th'):addClass('bg-white') :node(mw.html.create('div'):attr('class', 'border-hack bottom border-black')) :node(mw.html.create('div'):attr('class', 'border-hack right border-black')) ) for i,strat in ipairs(game.strats[2]) do h_payoffs_cols:node( mw.html.create('th'):attr('class', 'fg-p2 bg-white'):wikitext(strat) :node(mw.html.create('div'):attr('class', 'border-hack bottom border-black')) ) end h_payoffs:node(h_payoffs_cols) for i,strat in ipairs(game.strats[1]) do local h_row = mw.html.create('tr'):node( mw.html.create('th'):attr('class', 'fg-p1 bg-white'):wikitext(strat) :node(mw.html.create('div'):attr('class', 'border-hack right border-black')) ) for j,_ in ipairs(game.strats[2]) do local rat = game.outcomes[ game.map[j][i] ] h_row:node(mw.html.create('td') :attr( 'class', G._main(rat.num / rat.den, -100, 100) ) :wikitext(string.format("%.1f", rat.num / rat.den)) ) end h_payoffs:node(h_row) end
-- -- Create HTML for equilibrium, if it exists -- local profile = string.match(gbt, "<profile[^>]->(.-)</profile[^>]->") local h_profile = nil if profile ~= nil then local r_profile = {} local split = mw.text.split(mw.text.trim(profile), ",") if #split ~= #game.strats[1] + #game.strats[2] then error("Profile has mismatched number of probabilities: " .. #split .. " vs " .. (#game.strats[1] + #game.strats[2])) end local n = 1 for q = 1,2 do r_profile[q] = {} for i,v in ipairs(game.strats[q]) do r_profile[q][i] = p._ratParse(split[n]) n = n+1 end end
local F = function (rat) if rat == nil then return "0" end -- Turn e.g. 15/-4 into -15/4 local n,d = rat.num, rat.den if d < 0 then n = n * -1 d = d * -1 end return mw.getCurrentFrame():expandTemplate{ title = "F", args = { n, d } } end
-- Calculate the payoff for p1 of this equilibrium -- -- I believe you can get the payoff of any individual non-dominated -- outcome, since for an equilibrium they're all the same, but I'm not -- entirely surely this is a guaranteed property. local payoff = 0 for i = 1,#game.strats[1] do for j = 1,#game.strats[2] do local outcome = game.outcomes[ game.map[j][i] ] payoff = payoff + outcome * r_profile[2][j] * r_profile[1][i] end end
-- Calculate the payoff of each strategy of this equilibrium -- -- Used to display the payoff of the dominated options local s_payoff = {} for p = 1,2 do local q = (p == 1 and 2 or 1) s_payoff[p] = {} for i = 1,#game.strats[p] do local payoff = 0 for j = 1,#game.strats[q] do local outcome = (p == 1) and game.outcomes[ game.map[j][i] ] or (game.outcomes[ game.map[i][j] ] * -1) payoff = payoff + outcome * r_profile[q][j] end s_payoff[p][i] = payoff end end --mw.logObject(s_payoff)
h_profile = mw.html.create('div'):attr('class', 'profile') local h_elib = mw.html.create('div'):attr('class', 'equilibrium') :node( mw.html.create('p'):wikitext( "Nash equilibrium with payoff " .. F(payoff)) ) local h_pair = mw.html.create('div'):attr('class', 'strategy-pair') local dominated_strats_exist = false local h_dominated = {} local n = 1 for p = 1,2 do h_dominated[p] = mw.html.create('dl'):attr('class', 'strategy') local h_strat = mw.html.create('dl'):attr('class', 'strategy') for i,s in ipairs(game.strats[p]) do local prob = r_profile[p][i] local h_prob = mw.html.create('dd') local h_option = mw.html.create('div') :node(mw.html.create('dt'):attr('class', 'fg-p' .. p):wikitext(s)) :node(h_prob) if prob.num == 0 then dominated_strats_exist = true h_prob:wikitext( F(s_payoff[p][i]) ) h_dominated[p]:node(h_option) else h_prob:wikitext( F(prob) ) h_strat:node(h_option) end end h_pair:node(h_strat) end h_profile:node(h_elib:node(h_pair)) if dominated_strats_exist then local h_pair = mw.html.create('div'):attr('class', 'strategy-pair') for p = 1,2 do h_pair:node(h_dominated[p]) end h_profile:node(mw.html.create('div'):attr('class', 'dominated') :node(mw.html.create('p'):wikitext("Payoff for dominated options")) :node(h_pair) ) end end
-- Put it together local header = mw.html.create('div'):attr('class', 'mixup-header') :node(mw.html.create('div'):attr('class', 'mixup-title') :wikitext( "" .. title.fullText .. "" .. " ([" .. title:fullUrl() .. "?action=raw download])" .. " What is this?" ) )
local body = mw.html.create('div') :attr('class', 'mixup-body mw-collapsible-content border-blue-30') :node(mw.html.create('div'):attr('class', 'payoffs'):node(h_payoffs)) :node(h_profile)
local ret = mw.html.create('div') :attr('class', 'mixup mw-collapsible border-blue-30') :node(header)
if collapsed then ret:addClass('mw-collapsed') end
if game.comment ~= "" then ret:node(mw.html.create('div') :attr('class', 'mixup-descr') :wikitext( mw.getCurrentFrame():preprocess( "\n" .. game.comment .. "\n" ) ) ) end
ret:node(body)
--mw.logObject(ret) return ret end
return p