Documentation for this module may be created at Module:Mixup/doc
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
token = lexer.next()
if token[1] ~= T_STRING then
fail("Expecting string for outcome")
end
local outcome = {}
outcome_label = token[2]
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
table.insert(outcome, outcome_label)
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)
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), 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)
local maxVal = 0
for i,strat in ipairs(game.strats[1]) do
for j,_ in ipairs(game.strats[2]) do
local rat = game.outcomes[ game.map[j][i] ][1]
local val = rat.num / rat.den
maxVal = math.max(maxVal, math.abs(val))
end
end
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] ][1]
local label = game.outcomes[ game.map[j][i] ][3]
local tdNode = mw.html.create('td')
:attr('class', G._main(rat.num / rat.den, -maxVal, maxVal))
if label ~= "" then
tdNode:node(mw.html.create('div')
:wikitext(mw.getCurrentFrame():expandTemplate{ title = "tt", args = { math.floor(rat.num / rat.den), mw.getCurrentFrame():preprocess(label) } }))
else
tdNode:wikitext(string.format("%d", math.floor(rat.num / rat.den)))
end
h_row:node(tdNode)
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] ][1]
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] ][1]
or (game.outcomes[ game.map[i][j] ][1] * -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])" ..
" <sup>[[Template:Mixup#Explanation|What is this?]]</sup>"
)
)
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