Documentation for this module may be created at Module:Mixup/doc
local rational = require( "Module:Rational" )
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 C_HEADER = 0
local C_OUTCOMES = 1
local C_MAPPING = 2
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 ctx = C_HEADER
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
-- 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]
return p._render(page)
end
p._render = function(page)
-- 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('tbody')
local h_payoffs_cols = mw.html.create('tr'):tag('th')
for i,strat in ipairs(game.strats[2]) do
h_payoffs_cols:node(mw.html.create('th'):wikitext(strat))
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'):wikitext(strat)
)
for j,_ in ipairs(game.strats[2]) do
local rat = game.outcomes[ game.map[j][i] ]
h_row:node(mw.html.create('td'):wikitext(
"{{G|" .. string.format("%.0f", rat.num / rat.den) .. "}}"
))
end
h_payoffs:node(h_row)
end
local h_payoffs_table = mw.html.create('html')
:node(mw.html.create('caption'):wikitext('Payoffs'))
:node(h_payoffs)
--
-- 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 "{{F|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 "{{F|" .. 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', 'equilibrium')
:node(mw.html.create('p'):wikitext(
"Nash equilibrium with average payoff " .. F(payoff) .. "</p>")
)
local dominated_strats_exist = {}
local h_dominated = {}
local n = 1
for p = 1,2 do
dominated_strats_exist[p] = false
h_dominated[p] = {
heads = mw.html.create('tr'),
payoffs = mw.html.create('tr')
}
local h_heads = mw.html.create('tr')
local h_probs = mw.html.create('tr')
for i,s in ipairs(game.strats[p]) do
local prob = r_profile[p][i]
local h_head = mw.html.create('th'):wikitext(s)
if prob.num == 0 then
dominated_strats_exist[p] = true
h_dominated[p].heads:node( h_head )
h_dominated[p].payoffs:node(
mw.html.create('td'):wikitext( F(s_payoff[p][i]) )
)
else
h_heads:node( h_head )
h_probs:node( mw.html.create('td'):wikitext( F(prob) ) )
end
end
h_profile:node(mw.html.create('table')
:attr('class', 'strategy p' .. p)
:node( mw.html.create('tbody'):node(h_headings):node(h_probs) )
)
end
if dominated_strats_exist[1] or dominated_strats_exist[2] then
h_profile:node(mw.html.create('p'):wikitext("Payoff for dominated strategies"))
end
for p = 1,2 do
if dominated_strats_exist[p] then
h_profile:node(mw.html.create('table')
:attr('class', 'strategy p' .. p)
:node( mw.html.create('tbody')
:node(h_dominated[p].heads)
:node(h_dominated[p].payoffs)
)
)
end
end
end
-- Put it together
local ret = mw.html.create('div')
:attr('class', 'mixup')
:node(h_payoffs_table)
:node(h_profile)
if game.comment ~= "" then
ret:node(mw.html.create('div')
:attr('class', 'mixup-descr')
:wikitext(game.comment)
)
end
mw.logObject(ret)
return ret
end
return p