{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Games" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "using PGFPlots" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Traveler's Dilemma" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Actions are the dollar amounts (\\\\$2–\\\\$100). A strategy is a distribution over these amounts, represented as a vector. " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "const Action = Integer\n", "const Strategy = Vector{Float64}\n", "actions = collect(2:100)\n", "normalize(a::Vector) = a / sum(a);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$U_i(a_i, a_{-i}) = \\begin{cases}a_i & \\text{if } a_i = a_{-i}\\\\ a_i +2 & \\text{if } a_i < a_{-i}\\\\ a_{-i} - 2 & \\text{if } a_i > a_{-i}\\\\\\end{cases}$" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "function utility(own::Action, opponent::Action)\n", " if own == opponent\n", " return own\n", " elseif own < opponent\n", " return own + 2\n", " else\n", " return opponent - 2\n", " end\n", "end; " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$U_i(a_i, \\pi_{-i}) = \\sum_{a_{-i}} \\pi_{-i}(a_{-i})U(a_i, a_{-i})$" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "function utility(own::Action, opponent::Strategy)\n", " u = 0\n", " for i = 1:length(actions)\n", " u += opponent[i] * utility(own, actions[i])\n", " end\n", " u\n", "end;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quantal best response to opponent strategy $\\pi_{-i}$ is \n", "\n", "$\\pi_i(a_i) \\propto \\exp(\\lambda U_i(a, \\pi_{-i}))$" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "function quantalBestResponse(λ::Real, opponent::Strategy)\n", " s = Float64[exp(λ*utility(a, opponent)) for a in actions]\n", " normalize(s)\n", "end;" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "function logitLevelK(k::Integer, λ::Real)\n", " if k == 0\n", " return normalize(ones(length(actions)))\n", " else\n", " return quantalBestResponse(λ, logitLevelK(k - 1, λ))\n", " end\n", "end; " ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", " \n", "\n", "\n", "\n", "\n" ], "text/plain": [ "GroupPlot(Axis[Axis(PGFPlots.Plots.Plot[PGFPlots.Plots.Linear(Real[2.0 3.0 … 99.0 100.0; 0.010101010101010102 0.010101010101010102 … 0.010101010101010102 0.010101010101010102], \"none\", nothing, \"ycomb\", \"{\\$k = 0, \\\\lambda = 0.3\\$}\", nothing, nothing)], nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, 0, 0.4, nothing, nothing, nothing, nothing, nothing, \"12cm\", nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, \"axis\"), Axis(PGFPlots.Plots.Plot[PGFPlots.Plots.Linear(Real[2.0 3.0 … 99.0 100.0; 0.010101010101010102 0.010101010101010102 … 0.010101010101010102 0.010101010101010102], \"none\", nothing, \"ycomb\", \"{\\$k = 0, \\\\lambda = 0.5\\$}\", nothing, nothing)], nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, 0, 0.4, nothing, nothing, nothing, nothing, nothing, \"12cm\", nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, \"axis\"), Axis(PGFPlots.Plots.Plot[PGFPlots.Plots.Linear(Real[2.0 3.0 … 99.0 100.0; 4.972827736523659e-8 6.611675651484903e-8 … 0.03705025727174033 0.03671496312457856], \"none\", nothing, \"ycomb\", \"{\\$k = 1, \\\\lambda = 0.3\\$}\", nothing, nothing)], nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, 0, 0.4, nothing, nothing, nothing, nothing, nothing, \"12cm\", nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, \"axis\"), Axis(PGFPlots.Plots.Plot[PGFPlots.Plots.Linear(Real[2.0 3.0 … 99.0 100.0; 7.448152149984901e-12 1.1973710356170741e-11 … 0.04560665580358732 0.044920854451766204], \"none\", nothing, \"ycomb\", \"{\\$k = 1, \\\\lambda = 0.5\\$}\", nothing, nothing)], nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, 0, 0.4, nothing, nothing, nothing, nothing, nothing, \"12cm\", nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, \"axis\"), Axis(PGFPlots.Plots.Plot[PGFPlots.Plots.Linear(Real[2.0 3.0 … 99.0 100.0; 3.472022296380489e-12 4.686739481189105e-12 … 0.0610765026268642 0.05907941622485426], \"none\", nothing, \"ycomb\", \"{\\$k = 2, \\\\lambda = 0.3\\$}\", nothing, nothing)], nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, 0, 0.4, nothing, nothing, nothing, nothing, nothing, \"12cm\", nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, \"axis\"), Axis(PGFPlots.Plots.Plot[PGFPlots.Plots.Linear(Real[2.0 3.0 … 99.0 100.0; 1.2631186473690552e-19 2.0825305812871341e-19 … 0.07740936007268823 0.07231565408494554], \"none\", nothing, \"ycomb\", \"{\\$k = 2, \\\\lambda = 0.5\\$}\", nothing, nothing)], nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, 0, 0.4, nothing, nothing, nothing, nothing, nothing, \"12cm\", nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, \"axis\"), Axis(PGFPlots.Plots.Plot[PGFPlots.Plots.Linear(Real[2.0 3.0 … 99.0 100.0; 5.267128131371166e-13 7.109879298720492e-13 … 0.07244324573764323 0.06860968540609338], \"none\", nothing, \"ycomb\", \"{\\$k = 3, \\\\lambda = 0.3\\$}\", nothing, nothing)], nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, 0, 0.4, nothing, nothing, nothing, nothing, nothing, \"12cm\", nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, \"axis\"), Axis(PGFPlots.Plots.Plot[PGFPlots.Plots.Linear(Real[2.0 3.0 … 99.0 100.0; 7.419778029784149e-21 1.2233145861578615e-20 … 0.08923567161753464 0.07965570650562635], \"none\", nothing, \"ycomb\", \"{\\$k = 3, \\\\lambda = 0.5\\$}\", nothing, nothing)], nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, 0, 0.4, nothing, nothing, nothing, nothing, nothing, \"12cm\", nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, nothing, \"axis\")], (2, 4), nothing, nothing)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using Printf\n", "g = GroupPlot(2,4)\n", "lambdas = [0.3,0.5]\n", "ks = 0:3\n", "for k in ks\n", " for λ in lambdas\n", " title = Printf.@sprintf(\"{\\$k = %d, \\\\lambda = %0.1f\\$}\", k, λ)\n", " p = Axis(Plots.Linear(actions, logitLevelK(k, λ), style=\"ycomb\", mark=\"none\", legendentry=title),ymin=0,ymax=0.4, width=\"12cm\")\n", " push!(g, p)\n", " end\n", "end\n", "g" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Julia 1.2.0", "language": "julia", "name": "julia-1.2" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.2.0" } }, "nbformat": 4, "nbformat_minor": 1 }