tag:blogger.com,1999:blog-42125538887835417512024-03-12T21:29:37.396-07:00Un peu de math...My name is Vince Knight and I'm a lecturer in Operational Research at Cardiff University with interests in game theory and queueing theory. I'll be using this blog to post about various things mainly including math and software...
www.vincent-knight.comUnknownnoreply@blogger.comBlogger91125tag:blogger.com,1999:blog-4212553888783541751.post-83714348450983689792014-06-27T11:10:00.000-07:002014-06-27T11:10:01.296-07:00Pointing at a blog post about Sage and a treasure huntIt looks like I might be moving... I've been playing with jekyll + github and really love the workflow so it looks like I might be moving this blog over there.<br />
<br />
It's not official yet as I still need to think about a couple of things but in the meantime here's a post I just wrote over there about how the team I was in used Sage in a mathematical treasure hunt: <a class="ot-anchor aaTEdf" href="http://goo.gl/iLgGnL" rel="nofollow" style="-webkit-transition: color 0.218s; background-color: white; color: #427fed; cursor: pointer; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.200000762939453px; text-decoration: none; transition: color 0.218s;" target="_blank">http://goo.gl/iLgGnL</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-23806152316466699602014-05-19T15:10:00.001-07:002014-05-19T23:19:49.309-07:00Reflecting On Evidence For The Benefits Of Active LearningA paper entitled '<a href="http://www.pnas.org/content/early/2014/05/08/1319030111" target="_blank">Active Learning Increases Student Performance in Science, Engineering and Mathematics'</a> (by Freeman and 6 co-authors) was recently published and got a fair bit of quasi-popular press exposure as the message seemed to be quite simple: <em>Students learn better when they are not simply an audience during contact time</em> (or in other words: lectures aren't the best). I decided that this was a paper that I really wanted to read so I went through the pain of having to google twice (thus making it 'officially' hard to find) and have just finished reading it.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-nv3JLPbMq2U/U3p88UHGv8I/AAAAAAABH4A/asRxRc4ohq0/s1600/2014-05-19+18.31.12.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-nv3JLPbMq2U/U3p88UHGv8I/AAAAAAABH4A/asRxRc4ohq0/s1600/2014-05-19+18.31.12.jpg" height="240" width="320" /></a></div>
<br />
<strong><br /></strong>
<strong>This is a great paper.</strong><br />
<br />
Firstly there is a nice definition of what active learning is:<br />
<blockquote>
"Active learning engages students in the process of learning through activities and/or discussion in class, as opposed to passively listening to an expert. It emphasizes higher-order thinking and often involves group work."</blockquote>
The definition given in the paper for a <em>traditional lecture</em> is given as:<br />
<blockquote>
"[...] student activity is assumed to be limited to taking notes and/or occasional and unprompted questions of the instructor." </blockquote>
The definition for active learning is not obtained out of thin air but takes in to account over 300 audience members at departmental seminars on active learning throughout North America.<br />
<br />
What I particularly like about the definition is that it specifically makes a point of mentioning the higher-order thinking.<br />
<br />
I was recently lucky enough to attend a talk by <a href="https://twitter.com/tasdevilcol">Dr. Collin Jones</a> who teaches in Tasmania using an active learning approach. Here is a diagram that I've put together trying (humbly) to get across what he said on the subject of active learning (you might want to open the image in a new tab...):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-CD2xUBYJjAM/U3p9uJ8OzHI/AAAAAAABH4I/NnAhG3PBRPo/s1600/bloomtaxonmyasadimensionforlearning.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-CD2xUBYJjAM/U3p9uJ8OzHI/AAAAAAABH4I/NnAhG3PBRPo/s1600/bloomtaxonmyasadimensionforlearning.png" height="115" width="640" /></a></div>
<br />
<br />
In that I'm trying to say that if we want students to access the higher levels of <a href="http://drvinceknight.blogspot.co.uk/2013/10/blooms-taxonomy-drawn-in-tikz.html">Bloom's taxonomy</a> across the various topics in a course, with <strong>our help</strong> through contact time then a more active learning approach seems logical.<br />
<br />
It looks like Freeman's paper confirms this.<br />
<div>
<br /></div>
<strong>It tells us lots of great stuff.</strong><br />
<br />
The first section quickly summarsies the findings of rigorously (as far as I can tell the rigour in this paper is great) analysing the results of 225 studies that obeyed the following criteria:<br />
<ol style="list-style-type: decimal;">
<li>Involved a comparison between traditional lecturing and active learning;</li>
<li>Involved a regular class;</li>
<li>Only looked at comparison where the delivery method was the main change;</li>
<li>Involved a STEM subject;</li>
<li><strong>Included an evaluation of academic performance</strong></li>
</ol>
This later point is what has made this paper really stand up and get noticed. In fact this and 2 other papers (<a href="http://www.sciencemag.org/content/331/6022/1269.summary">here</a> and <a href="http://www.jstor.org/discover/10.2307/1170643?uid=3738032&uid=2&uid=4&sid=21104187485553">here</a>) are the only papers that offer a meta analysis of student performances. <strong>This is not a paper reflecting on teaching methodologies but on the actual effects that teaching methodologies have on student learning.</strong><br />
<strong><br /></strong>
There are a variety of well presented findings and I will try and summarise them very briefly here:<br />
<ol style="list-style-type: decimal;">
<li>Students will perform by just under half a standard deviation <em>better</em> in an active learning environment;</li>
<li>Students are 1.5 times more likely to fail in a traditional lecture environment;</li>
<li>1. and 2. are not affected by the particular STEM subject;</li>
<li>The gain in 1. for concept inventory style assessment are <em>lower</em> than for 'instructor-written' type assessment. This is argued (and I think I agree) to be in line with my arrows going through Bloom's taxonomy. In an active learning environment students are more likely to perform well on tasks that require a deeper learning;</li>
<li>The gain in 1. is more prominent in smaller classes. This also makes sense (taking a class with a minimum number of students of 1, it would be idiotic to lecture and similarly for an infinite class perhaps an active learning approach would not be appropriate).</li>
</ol>
All of the above is just plain cool to have a rigorous basis for. Potential weaknesses of the study are confidently rebutted in the manuscript itself (for example the number of papers showing no improvement whatsoever that would be needed to lower the impact of the work is shown to be high).<br />
<br />
<b>Evidence</b><br />
<br />
<a class="g-profile" href="https://plus.google.com/104386712472263535860" target="_blank">+Stan Yoshinobu</a> has written a brief post about Freeman's paper at <a href="http://theiblblog.blogspot.co.uk/2014/05/data-points-toward-active-learning.html">The IBL blog</a> and I really like:<br />
<blockquote>
"The perspective I like to take is one that is used in medicine. When new techniques or treatments are shown through evidence to provide better care for patients, then the medical community adopts those new practices."</blockquote>
This is something alluded to by Freeman et al. They talk about their paper (and others) being the 'first generation' of research in to active learning and that now that there is evidence for the benefits perhaps the second generation of research would start looking at <em>best</em> types of active learning for given students etc...<br />
<strong><br /></strong>
<strong>1 last thing.</strong><br />
<br />
The final thing I want to talk about is the potential weakness of this research. This is pointed out by the authors:<br />
<blockquote>
"The instructors who implemented active learning in these studies did so as volunteers. It is an open question whether student performance would increase as much if all faculty were required to implement active learning approaches."</blockquote>
My personal opinion is that that really hits the issue on the head. Instructors who innovate with their teaching so as to move away from the tried and tested lecture that has been in place for 100s of years are most probably the academics who have the energy and conviction to put a lot of effort in to their teaching.<br />
<br />
Often in academia where the pressure to publish and obtain funding are <strong>immense</strong> it is sad to say that it's very easy to simply reach for the same set of notes that has always passed down and lecture. This leaves students to attempt to reach deeper levels of learning on their own.<br />
<br />
It must also be said though, (as alluded to in the paper) <em>active learning</em> means a variety of things. For example I use problem based learning, flipped classrooms and a combination of <a href="http://goo.gl/m7K4fn">active game playing</a> (that I would like to think has some element of inquiry based learning) in my own teaching <em>however</em> active learning in Freeman's paper has a breadth of meanings which include the simple use of clickers to get some form of student engagement with the learning. So I don't <i>necessarily</i> think that an active learning approach implies a huge distancing from classic lecturing for all instructors (see the earlier definitions of the active learning and traditional lecture).<br />
<br />
As the authors' state it's a case of now identifying the best pedagogic approaches for instructors as well as students: getting that pairing right.<br />
<br />
<b>Fun</b><br />
<br />
I really enjoyed something that <a href="http://www.ed.ac.uk/schools-departments/principals-office/vice-principals-smgt/rigby">Dr Sue Rigby</a> said at the opening of the 2014 HEA STEM conference:<br />
<blockquote>
"We have to teach in a way that is fun. We get to choose how we teach"</blockquote>
As educators I think it's <strong>very</strong> important to remember that we do indeed get to choose how we teach and ultimately active learning is often simply far more fun than traditional lectures (I sure had a smile on my face when trying to teaching cooperative game theory by <a href="http://drvinceknight.blogspot.co.uk/2014/03/basketball-and-cooperative-games-in.html" target="_blank">having students play waste paper basketball</a>).<br />
<br />
We should always choose a pedagogic approach for a better reason than "that's how it has always been done". Sound research like the one in this paper seems like a good a reason as any.<br />
<br />
-----<br />
<br />
Edit: On the 7 and 8th of July (2014) <a class="g-profile" href="https://plus.google.com/103137876942082024919" target="_blank">+Paul Harper</a> and I are hosting <a href="http://mathsevents.cf.ac.uk/mathedworkshop/index.html" target="_blank">a workshop on active learning techniques</a>. Please take a look :)Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-1460189172442672002014-05-11T08:52:00.001-07:002014-05-11T09:06:53.184-07:00Wizards, Giants, Linear Programming and Sage<script src="https://sagecell.sagemath.org/static/jquery.min.js"></script>
<script src="https://sagecell.sagemath.org/static/embedded_sagecell.js"></script>
<script>sagecell.makeSagecell({"inputLocation": ".sage"});</script>
I've been playing a game on my phone for a couple of months now called <a href="http://www.supercell.net/games/view/clash-of-clans">Clash of clans</a>. It's one of those freemium games that tells me to do something on my phone every now and then:<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/YSdJtNen-EA?feature=player_embedded' frameborder='0'></iframe></div>
<br />
<br />
In essence during the game you build your base with buildings to obtain resources, create troops and defend against attacks.<br />
<br />
Here's a screen shot of my base at the moment:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-05XkgbpBpwY/U2-Onr9afqI/AAAAAAABGug/8bItwhSzy9s/s1600/2014-05-11+08.47.19.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-05XkgbpBpwY/U2-Onr9afqI/AAAAAAABGug/8bItwhSzy9s/s1600/2014-05-11+08.47.19.png" height="225" width="400" /></a></div>
<br />
As well as building your base, you can also put together a raiding party and attacking other bases.<br />
<strong>In this post, I'll describe the use of a mathematical technique called <a href="http://en.wikipedia.org/wiki/Integer_programming" target="_blank">linear programming</a> so as to get the best combination of Giants, Wizards etc in a raiding party.</strong><br />
<strong><br /></strong>
To train a warrior costs Elixir (a resource that you mine and/or plunder) but also costs space in your army camps.<br />
<br />
Here are the various warriors available to me at the moment (as you build better buildings you get more warriors etc...).<br />
<br />
1. Barbarian (Damage per second: 18, Hitpoints: 78, Housing Space: 1, Elixir Cost: 80):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-74FEWc0dfmU/U2-O6Cmx_TI/AAAAAAABGuo/iEJQIokRnHk/s1600/2014-05-11+08.47.28.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-74FEWc0dfmU/U2-O6Cmx_TI/AAAAAAABGuo/iEJQIokRnHk/s1600/2014-05-11+08.47.28.png" height="225" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
2. Archer (Damage per second: 16, Hitpoints: 33, Housing Space: 1, Elixir Cost: 160)</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-WoSOrbUH1-A/U2-O6Nf3sjI/AAAAAAABGu0/IgGY18tDl8s/s1600/2014-05-11+08.47.35.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-WoSOrbUH1-A/U2-O6Nf3sjI/AAAAAAABGu0/IgGY18tDl8s/s1600/2014-05-11+08.47.35.png" height="225" width="400" /></a></div>
<br />
<div class="separator" style="clear: both;">
3. Goblin (Damage per second: 19, Hitpoints: 36, Housing Space: 1, Elixir Cost: 60)</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-r1-TeRDN3_I/U2-O6BjIC2I/AAAAAAABGus/ZiRo3UBjqqs/s1600/2014-05-11+08.47.40.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-r1-TeRDN3_I/U2-O6BjIC2I/AAAAAAABGus/ZiRo3UBjqqs/s1600/2014-05-11+08.47.40.png" height="225" width="400" /></a></div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
4. Giant (Damage per second: 24, Hitpoints: 520, Housing Space: 5, Elixir Cost: 2000) </div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-Z5Wbe2TtjLE/U2-O7iQUbKI/AAAAAAABGu8/DMaHMtV-wM0/s1600/2014-05-11+08.47.45.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-Z5Wbe2TtjLE/U2-O7iQUbKI/AAAAAAABGu8/DMaHMtV-wM0/s1600/2014-05-11+08.47.45.png" height="225" width="400" /></a></div>
<br />
5. Wall Breaker (Damage per second: 32, Hitpoints: 35, Housing Space: 2, Elixir Cost: 2500)<br />
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-mBmMiKhrn5Y/U2-O8AghqyI/AAAAAAABGvI/ePSukV83GTs/s1600/2014-05-11+08.47.49.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-mBmMiKhrn5Y/U2-O8AghqyI/AAAAAAABGvI/ePSukV83GTs/s1600/2014-05-11+08.47.49.png" height="225" width="400" /></a></div>
<br />
<div class="separator" style="clear: both;">
6. Balloon (Damage per second: 72, Hitpoints: 280, Housing Space: 5, Elixir Cost: 3500)</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-Xz-_oM4xaQs/U2-O8o8pboI/AAAAAAABGvM/9p4PuRA6S48/s1600/2014-05-11+08.47.55.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-Xz-_oM4xaQs/U2-O8o8pboI/AAAAAAABGvM/9p4PuRA6S48/s1600/2014-05-11+08.47.55.png" height="225" width="400" /></a></div>
<br />
<div class="separator" style="clear: both;">
7. Wizards (Damage per second: 125, Hitpoints: 130, Housing Space: 4, Elixir Cost: 3000)</div>
<div>
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-ulkostyA6zc/U2-O9d70XXI/AAAAAAABGvU/8r0jTooCkSI/s1600/2014-05-11+08.47.59.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-ulkostyA6zc/U2-O9d70XXI/AAAAAAABGvU/8r0jTooCkSI/s1600/2014-05-11+08.47.59.png" height="225" width="400" /></a></div>
<br />
8. Healer (Damage per second: NA, Hitpoints: 600, Housing Space: 14, Elixir Cost: 6000)<br />
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-cbpk44b6d14/U2-O-E3MMLI/AAAAAAABGvY/YO-Bao2rmrI/s1600/2014-05-11+08.48.03.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-cbpk44b6d14/U2-O-E3MMLI/AAAAAAABGvY/YO-Bao2rmrI/s1600/2014-05-11+08.48.03.png" height="225" width="400" /></a></div>
<br />
9. Dragon (Damage per second: 140, Hitpoints: 1900, Housing Space: 20, Elixir Cost: 25000)<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-arjGyemg2oI/U2-O-wjMm0I/AAAAAAABGvg/fZl1IB7NhCc/s1600/2014-05-11+08.48.08.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-arjGyemg2oI/U2-O-wjMm0I/AAAAAAABGvg/fZl1IB7NhCc/s1600/2014-05-11+08.48.08.png" height="225" width="400" /></a></div>
<br />
<br />
<br />
To summarise the information about the players I'm going to put the costs in a vector \(c\) and the housing space in a vector \(h\) (indexed using the same order as the images above):<br />
<br />
\[c=(80,160,60,2000,2500,3500,3000,6000,25000)\]<br />
\[h=(1,1,1,5,2,5,4,14,20)\]<br />
<br />
Currently I have a capacity of 50 housing spaces per camp and I have 4 camps so I have an upper bound on the total amount of housing space of \(K=200\).<br />
<br />
If I let the vector \(x\) denote a raiding party so that \(x_i\) is the number of warriors of type \(\i) (using the ordering above) then we have the corresponding <strong>housing space</strong> constraint:<br />
<br />
\[\sum_{i=1}^9h_ix_i\leq K\]<br />
<br />
I can now try and do two things:<br />
<ol style="list-style-type: decimal;">
<li><b>Get a full set of camps by minimising the overall cost.</b></li>
<li><b>Get the most powerful raiding party that can fit in my camps.</b></li>
</ol>
I will solve both of these problems using what is called Integer Linear Programming. The <strong>integer</strong> part of that is due to the fact that I must have whole parts of warriors.<br />
<h3>
<ol style="list-style-type: decimal;">
<li><strong>Minimising my costs</strong></li>
</ol>
</h3>
The cost of a given rading party \(x\) is given by:<br />
<br />
\[C(x) = \sum_{i=1}^9c_ix_i \]<br />
<br />
Thus to minimise this cost <strong>and</strong> fill the camps we need to solve the following minimisation problem:<br />
<br />
\[\text{minimise }C(x) = \sum_{i=1}^9c_ix_i\]<br />
<br />
such that:<br />
<br />
\[H(x)=\sum_{i=1}^9h_ix_i= K\]<br />
and<br />
\[x_i\in\mathbb{Z}_{\geq0}\]<br />
<br />
How do we solve this? I've blogged about a similar type of optimisation problem that I use to schedule my class assessment and for that I used the awesome <a href="http://sagemath.org/">sagemath</a>. You can read that blog post <a href="http://drvinceknight.blogspot.co.uk/2014/03/scheduling-group-presentations-using.html">here</a>. Here I will do the same thing.<br />
<br />
The following Sage code is what is needed to create the linear program and also obtain the solution:<br />
<pre><code>
</code></pre>
<pre><code><span style="font-family: Courier New, Courier, monospace;"># Set up parameters:
K = 200 # Set the upper bound
c = [80,160,60,2000,2500,3500,3000,6000,25000] # The the cost vector
h = [1,1,1,5,2,5,4,14,20] # Set the 'housing space' constraints vector
n = len(c) # Get the number of warriors
C = lambda x: sum([x[i]*c[i] for i in range(n)]) # Define the cost function
H = lambda x: sum([x[i]*h[i] for i in range(n)]) # Define the housing capacity function
# Create and solve the optimisation problem
p = MixedIntegerLinearProgram(maximization=False) # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True) # Create a variable with the requirement that it must be integer
p.add_constraint(H(x)==K) # Set the housing constranit
p.set_objective(C(x)) # Set the objective function
p.show() # Show the optimisation problem
p.solve() # Solve the optimisation problem</span></code></pre>
<pre><code><span style="font-family: Courier New, Courier, monospace;">
</span></code></pre>
<pre><code><span style="font-family: Courier New, Courier, monospace;"># Solve the optimisation problem</span></code></pre>
<pre><code><span style="font-family: Courier New, Courier, monospace;">
</span></code></pre>
<span style="font-family: Courier New, Courier, monospace;">print 'Has solution:' </span><br />
<span style="font-family: Courier New, Courier, monospace;">for i, v in p.get_values(x).iteritems(): </span><br />
<span style="font-family: Courier New, Courier, monospace;"> print 'x_%s = %s' % (i, int(round(v))) </span><br />
<span style="font-family: Courier New, Courier, monospace;">print 'Housing spaces used: %s' % H(p.get_values(x))</span><br />
<br />
The output is (disappointing but expected): \(x=(0,0,200,0,0,0,0,0)\) which implies that I should have 200 Goblins.<br />
<br />
If you're familiar with the game this is not a very sensible way to go as Goblins are really only good at getting loot from defenceless bases.<br />
<br />
We can add a couple more constraints so that we don't have too many goblins (let's limit it to 10) and also so that we have at least one healer:<br />
<br />
<pre><code><span style="font-family: Courier New, Courier, monospace;">p = MixedIntegerLinearProgram(maximization=False) # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True) # Create a variable with the requirement that it must be integer
p.add_constraint(H(x)==K)
p.add_constraint(x[2]<=10) # Don't want more than 10 goblins
p.add_constraint(x[7]>=1) # Want 1 healer at least
p.set_objective(C(x))
p.show()
p.solve()
print 'Has solution:'
for i, v in p.get_values(x).iteritems():
print 'x_%s = %s' % (i, int(round(v)))
print 'Housing spaces used: %s' % H(p.get_values(x))</span></code></pre>
<br />
This gives us \(x=(176,0,10,0,0,0,0,1,0)\).<br />
<br />
This is again not very satisfying as we're basically filling our raiding party with the cheapest options. <b>That was the purpose of this approach though. </b><br />
<b><br /></b>
The next thing we'll look at is how to actually get a good raiding part.<br />
<h3>
<ol start="2" style="list-style-type: decimal;">
<li>Getting the 'best' raiding party.</li>
</ol>
</h3>
As you can see on the images, every warrior is different: some fly, some are better against buildings, some have more hitpoints than others etc...<br />
<br />
One way of getting the 'best' raiding party could be to maximise the damage per second of the raiding party. To do this, let's define the following vector (which is just the damage per second that can be read off of the images above):<br />
<br />
\[d=(18, 16, 19, 24, 32, 72, 125, 0, 140)\]<br />
<br />
Now our maximisation problem can be written as:<br />
<br />
\[\text{maximise } \sum_{i=1}^9d_ix_i\]<br />
<br />
such that:<br />
<br />
\[H(x)=\sum_{i=1}^9h_ix_i\leq K\]<br />
and<br />
\[x_i\in\mathbb{Z}_{\geq0}\]<br />
<br />
Here's the Sage code to do this:<br />
<pre><code>
</code></pre>
<pre><code><span style="font-family: Courier New, Courier, monospace;">damagepersecond = [18, 16, 19, 24, 32, 72, 125, 0, 140]
C = lambda x: sum([x[i]*damagepersecond[i] for i in range(n)])
p = MixedIntegerLinearProgram() # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True) # Create a variable with the requirement that it must be integer
p.add_constraint(H(x)<=K)
p.add_constraint(x[2]<=10) # Don't want more than 10 goblins
p.add_constraint(x[7]>=1) # Want 1 healer at least
p.set_objective(C(x))
p.show()
p.solve()
print 'Has solution:'
for i, v in p.get_values(x).iteritems():
print 'x_%s = %s' % (i, int(round(v)))
print 'Housing spaces used: %s' % H(p.get_values(x))</span></code></pre>
<pre><code><span style="font-family: Courier New, Courier, monospace;">
</span></code></pre>
The result of the above is \(x=(0,0,2,0,0,0,46,1,0)\). I.e take 2 goblins, 46 wizards and 1 healer.<br />
The problem with this raiding party is that wizards are actually quite fragile (archers towers and cannons can pretty much just pick them off).<br />
<strong><br /></strong>
<strong>So perhaps instead of maximising the damage per second we could maximise the total hit points of the party</strong>.<br />
<br />
To do this we need to define the vector of hitpoints:<br />
<br />
\[p=(78, 33, 36, 520, 35, 280, 130, 600, 1900)\]<br />
<br />
Now our maximisation problem can be written as:<br />
<br />
\[\text{maximise } \sum_{i=1}^9p_ix_i\]<br />
<br />
such that:<br />
<br />
\[H(x)=\sum_{i=1}^9h_ix_i\leq K\]<br />
and<br />
\[x_i\in\mathbb{Z}_{\geq0}\]<br />
<br />
This gives us \(x=(0,0,0,0,93,0,0,1,0)\): a raiding part of wall breakers.<br />
<br />
The problem with this is that wall breakers are good for just that: breaking walls. They carry a bomb up to a wall and then they explode. So let's add some more constraints to our optimisation problem so as to get something a bit more useful.<br />
<ul>
<li>Let's make sure that we always have at least 20 housing capacity worth of distance attackers (Archers or Wizards):</li>
</ul>
\[x_1h_1+x_6h_6 \geq 20 \]<br />
<ul>
<li>Let's ensure that we have at least 1 air attacker (so that once the air defenses are out of the way we can finish off the base):</li>
</ul>
\[x_5+x_8\geq1\]<br />
<ul>
<li>Let's ensure that we always have some wall breakers to clear the walls for our ground units (1 per 5 giants and 1 per 20 barbarians say):</li>
</ul>
\[5x_4\geq x_3\]<br />
<div>
<br /></div>
<div>
\[20x_4\geq x_0\]<br />
<ul>
</ul>
The code to solve this is given here:<br />
<pre><code>
</code></pre>
<pre><code><span style="font-family: Courier New, Courier, monospace;">p = MixedIntegerLinearProgram() # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True) # Create a variable with the requirement that it must be integer
p.add_constraint(H(x) <= K)
p.add_constraint(x[2] <= 10) # Don't want more than 10 goblins
p.add_constraint(x[7] >= 1) # Want 1 healer at least
p.add_constraint(x[1] * h[1] + x[6] * h[6]>=20) # Want at least 20 capacity worth of distance attackers
p.add_constraint(x[5] + x[8]>=1) # Want at least 1 of air attackers
p.add_constraint(5 * x[4] >= x[3]) # Want at least 1 wall breaker per 5 giants
p.add_constraint(20 * x[4] >= x[0]) # Want at least 1 wall breaker per 20 barbarians
p.set_objective(C(x))
p.show()
p.solve()
print 'Has solution:'
for i, v in p.get_values(x).iteritems():
print 'x_%s = %s' % (i, int(round(v)))
print 'Housing spaces used: %s' % H(p.get_values(x))</span></code></pre>
<br />
This gives \(x=(1,20,0,23,5,0,0,1,2)\): so take 1 Barbarian, 20 Archers, 23 Giants, 5 Wall Breakers, 1 Healer and 2 Dragons.<br />
<br />
The above would give us the most hit points but now we're missing out on the damage power of wizards.<br />
<br />
<strong>Perhaps we could try and balance both hitpoints damage.</strong><br />
<br />
In essence we have what's called a <a href="http://en.wikipedia.org/wiki/Multi-objective_optimization">multi objective optimisation problem</a>. One approach to solve this is to simply weight both objectives.<br />
<br />
<b>We're going to use \(\alpha\) to denote the importance of the hitpoints and \(1-\alpha\) the importance of the damage.</b><br />
<br />
Our optimisation function then becomes:<br />
<br />
\[\alpha\sum_{i=1}^9p_ix_i+(1-\alpha)\sum_{i=1}^9d_ix_i\]<br />
<br />
Using the same constraints as before and taking \(\alpha=.5\) (so that both damage and hit points have equal weighting) we get \(x=(11,0,0,25,5,0,5,1,1)\). Thus we should be taking in to battle: 11 Barbarians, 25 Giants, 5 Wall Breakers, 5 Wizards, 1 Healer and 1 Dragon.<br />
<br />
This feels much more balanced than anything we've had so far and not far off what I've been using as my own raiding party.<br />
<br />
Given that everything is nicely coded we can quickly obtain the make up of the optimal raiding party for a range of values of \(\alpha\):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-88EzBa6neBs/U2-S42dYbDI/AAAAAAABGwI/dqoLTWhSi88/s1600/sage0+.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-88EzBa6neBs/U2-S42dYbDI/AAAAAAABGwI/dqoLTWhSi88/s1600/sage0+.png" height="297" width="400" /></a></div>
<br />
<br />
We see that as \(\alpha\) increases (so that we care more about hit points) the number of Wizards we should use slowly decreases (at one point the constraint for ranged attacking units kicks in and we replace the Wizards with Archers).<br />
<br />
You could easily tweak the constraints to perhaps ensure your party always has <em>some</em> Goblins or otherwise. I think this is a nice example where a mathematical model can be used to solve a problem but at the same time must not be taken far from the problem itself. There might be some players who only choose to attack bases with a particular type of defence so they can tweak/add constraints to the problem accordingly.<br />
<br />
Feel free to play around with the code in the Sage cell below:<br />
<br />
<div class="sage">
<script type="text/x-sage">
K = 200 # Set the upper bound
c = [80,160,60,2000,2500,3500,3000,6000,25000] # The the cost vector
h = [1,1,1,5,2,5,4,14,20] # Set the 'housing space' constraints vector
n = len(c) # Get the number of warriors
H = lambda x: sum([x[i]*h[i] for i in range(n)]) # Define the housing capacity function
hitpoints = [78, 33, 36, 520, 35, 280, 130, 600, 1900]
damagepersecond = [18, 16, 19, 24, 32, 72, 125, 0, 140]
alpha = .5
C = lambda x: sum([x[i]*(alpha * hitpoints[i] + (1-alpha)*damagepersecond[i]) for i in range(n)])
p = MixedIntegerLinearProgram() # Create an optimisation problem with minimization as the goal
x = p.new_variable(integer=True) # Create a variable with the requirement that it must be integer
p.add_constraint(H(x) <= K)
p.add_constraint(x[2] <= 10) # Don't want more than 10 goblins
p.add_constraint(x[7] >= 1) # Want 1 healer at least
p.add_constraint(x[1] * h[1] + x[6] * h[6] >=20) # Want at least 20 capacity worth of distance attackers
p.add_constraint(x[5] + x[8] >=1) # Want at least 1 of air attackers
p.add_constraint(5 * x[4] >= x[3]) # Want at least 1 wall breaker per 5 giants
p.add_constraint(20 * x[4] >= x[0]) # Want at least 1 wall breaker per 20 barbarians
p.set_objective(C(x))
p.show()
p.solve()
print 'Has solution:'
for i, v in p.get_values(x).iteritems():
print 'x_%s = %s' % (i, int(round(v)))
print 'Housing spaces used: %s' % H(p.get_values(x))
</script>
</div>
<br />
The mathematical techniques used in this post rely on Linear Algebra, Higher Dimensional Geometry and obviously the ability to write code :)<br />
<br />
(On another note I'm still not in a clan on the game so if anyone has any space in a clan let me know!)</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-61772306467965707002014-05-03T11:16:00.003-07:002014-05-03T11:16:31.743-07:00Debugging Python with pdb at the command line I've just put up a short video (7 mins) describing one way of debugging in Python using the pdb module (<a href="https://docs.python.org/2/library/pdb.html">here's the docs</a>):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/jOPOFCl6AFU?feature=player_embedded' frameborder='0'></iframe></div>
<br />
In this video I show how to step through code, view values of variables and also insert various types of break points.<br />
<br />
All this is done interactively at the command line but you can also use the pdb library to include debugging commands in your Python script itself.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-78265337146965840372014-05-02T01:18:00.003-07:002014-05-02T01:22:50.611-07:00Reflecting on Pechu KuchaIn <a href="http://drvinceknight.blogspot.co.uk/2014/04/my-thoughts-on-pechu-kucha-presentation.html">this</a> previous blog post I described my frustration with the fact that the <a href="http://en.wikipedia.org/wiki/PechaKucha">Pechu Kucha</a> presentation style was imposed on all speakers at the <a href="http://www.heacademy.ac.uk/stem-conference-2014">#HEASTEM14</a> conference.<br />
<br />
That was 3 days ago and with the conference behind me, I am going to write down my thoughts.<br />
First of all: <strong>the whole conference was awesome</strong>. I had a great time and learnt a lot through the awesome discussions that arose after a session of talks. Each session involved a triplet of Pechu Kuchas (with no gaps) followed by a lengthy discussion.<br />
<br />
<b>These discussion were awesome.</b><br />
<br />
<strong>Sadly I don't believe these discussions had anything to do what so ever with Pechu Kuchas.</strong><br />
<strong><br /></strong>
I actually enjoyed my own Pechu Kucha but didn't really feel that it was anything different to a normal presentation (apart from no interaction with the audience and that it was shorter than usual).<br />
I overheard a few speakers say things like: 'it really makes you rehearse' but personally rehearsing is something I always do (I probably rehearsed less for this as I was only talking for 3 minutes and 20 seconds).<br />
<br />
The reason the discussions were so awesome was simply that there was enough time for them. The reason there was enough time for them was that Pechu Kucha ensured that everyone spoke for no more than 7 minutes.<br />
<br />
This could have been achieved by ensuring that sessions were chaired <strong>strictly</strong> without the need to further constrain the speakers.<br />
<br />
One comment on my previous post said:<i> 'Talks overrun because moderators are not doing their job'</i>.<br />
<br />
I realise that it's not always easy to be a chair but I think that <b>imposing</b> Pechu Kucha is not the right solution.<br />
<br />
One private comment on my previous post said that <i>'I also think that this format is not helpful for speakers with slight speech impediments'</i>. Indeed, forcing everyone to use a given delivery style is not terribly inclusive.<br />
<br />
I mentioned my opinion to a couple of organisers (again: <b>who did a truly awesome job with the conference</b>) and after clarifying that I wasn't worried about my personal experience of Pechu Kucha but more that I didn't think it was great that everyone <b>had</b> to use it, I received responses along the lines of:<br />
<br />
- 'Well I suppose people knew that this was the way so they could choose to not give a presentation';<br />
- 'There are other options such as presenting a poster'.<br />
<br />
I perhaps misunderstood and/or am taking that out of context (in which case I apologise) but at an education conference attended by people for whom inclusivity is a high priority I can't say I was terribly satisfied with that response.<br />
<br />
Finally to return to the great thing about this conference: <b>the post talk discussions.</b> These were truly awesome and it was so great to be in a place where everyone cared and these discussions offered a great opportunity to transfer ideas and opinions.<br />
<br />
Sadly (as is to be expected) having a single discussion session at the end of 3 talks often meant that 1 or 2 of the talks received no discussion what so ever. This could of course be because the talk in question did not instigate enough interest for any questions but I also think that it could be because after the first question is asked and answered, further discussion just snowballed it's way through the room (which is awesome). This is a minor point for me, as in a way if the discussion didn't cover a particular talk but was very interesting perhaps it's not a problem (people could always approach the speakers after the talk).<br />
<br />
<b>To summarise:</b><br />
<b><br /></b>
- It was fun to try out the Pechu Kucha style.<br />
- It worked (indeed there is no need for long talks, short talks are awesome)<br />
- I don't think it should be enforced (this is NOT inclusive, what if I did not want to use PowerPoint? 'Not presenting' or 'presenting a poster' are not acceptable alternatives)<br />
<br />
I would (<b>humbly</b>) suggest that next time Pechu Kucha is not imposed (perhaps a Pechu Kucha session or 2 would be a good idea) <b>but </b>I certainly think having a <b>7 minute limit on talks is a GREAT idea</b>.<br />
<br />
This would require strict chairs that kept the conference to time. Something similar to the 'Grand Council' I used in my first year class this year. It involved 40 1 minute pitches from my students: they each had a minute and I was quite brutal in my chairing of the session. I had a timer go off and would yell "YOU'RE DONE!" but mostly it was the next student talking that would usher the previous off the stage. In practice I think I actually only cut 5 students short as all the others kept to time brilliantly. <a class="g-profile" href="https://plus.google.com/103137876942082024919" target="_blank">+Paul Harper</a> wrote<a href="http://goo.gl/VPa8OG"> this post</a> about it.<br />
<br />
<b>I loved the conference. </b><br />
<br />
<b>Pechu Kucha certainly didn't make it worse than it would have been otherwise as everyone made the system work.</b><br />
<br />
I just don't feel that it was an inclusive way of doing things (nor that it was necessary). Next year I will hopefully attend and either use one of the Pechu Kucha workarounds (discussed in the comments on my previous post), present using the delivery system of my choice or I suppose: present a poster.<!-----><!-----><br />
<br />
Finally similar to my image of Machu Picchu in my other post here is a picture of Pickachu (which is what I have been calling Pechu Kucha for the past 3 days):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://cdn.bulbagarden.net/upload/thumb/0/0d/025Pikachu.png/250px-025Pikachu.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://cdn.bulbagarden.net/upload/thumb/0/0d/025Pikachu.png/250px-025Pikachu.png" /></a></div>
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-9372321612180042242014-04-29T07:45:00.000-07:002014-04-29T10:40:16.752-07:00My thoughts on the Pechu Kucha presentation style BEFORE the HEA STEM ConferenceThis week I'm attending the <a href="http://www.heacademy.ac.uk/stem-conference-2014">HEA STEM Conference 2014</a>.<br />
<br />
<a class="g-profile" href="https://plus.google.com/103137876942082024919" target="_blank">+Paul Harper</a> and I will be presenting some work we undertook with <a class="g-profile" href="https://plus.google.com/117482832260700056568" target="_blank">+Louise Orpin</a> and <a class="g-profile" href="https://plus.google.com/114777160247741016418" target="_blank">+Noel-Ann Bradshaw</a> (the title of the talk is 'Operational research ambassadors in schools' but that's for another time).<br />
<strong><br /></strong>
<strong>All of the presenters have been given strict constraints to use the '<a href="http://en.wikipedia.org/wiki/PechaKucha" target="_blank">Pechu Kucha</a>' style.</strong><br />
<br />
This involves using 20 slides that are set on a timer so that every slide is shown for 20 seconds with no control from the speaker. (All slides have had to be sent to the organisers quite a while ago and will be ran from a central computer.)<br />
<br />
I am writing this post <strong>before</strong> the conference so perhaps my opinion will change but at present: <b>I don't like it</b>.<br />
<br />
There are obvious benefits to using this style:<br />
<ul>
<li>It's something different;</li>
<li>It will be fast paced;</li>
<li>It is easy to control (I have heard that this format was chosen because multiple talks overran in past conferences).</li>
</ul>
I'm sure I'm missing other good points (feel free to add them in the comments).<br />
<br />
Here comes my negative points:<br />
<h2 id="from-a-technical-point-of-view-its-a-shame-to-not-be-trusted">
<br /></h2>
<h2 id="from-a-technical-point-of-view-its-a-shame-to-not-be-trusted">
From a technical point of view it's a shame to not be trusted</h2>
We had a virtual meeting yesterday where <a class="g-profile" href="https://plus.google.com/114777160247741016418" target="_blank">+Noel-Ann Bradshaw</a> suggested something that really should have been on our slides but we cannot modify them.<br />
<h2 id="forcing-everyone-to-use-a-given-content-delivering-format-is-not-appropriate.">
<br /></h2>
<h2 id="forcing-everyone-to-use-a-given-content-delivering-format-is-not-appropriate.">
Forcing everyone to use a given content delivering format is not appropriate.</h2>
This is an education conference with talks entitled: 'Dancing statistics - communicating statistical ideas to non-mathematical students' and 'iLectures - designing and developing interactive lectures using cloud-based broadcasting solutions'. These talks sound like they will be discussing various <strong>innovative</strong> content delivery formats. There is (in my opinion) no single best content delivery format but usually an ok content-audience-speaker triplet.<br />
<br />
Why should everyone have to use the same format? (For some Pechu Kechu might be great but for others it might be terrible).<br />
<h2 id="this-is-enforcing-a-lecture-style-delivery-with-a-disconnection-between-audience-and-speaker">
<br /></h2>
<h2 id="this-is-enforcing-a-lecture-style-delivery-with-a-disconnection-between-audience-and-speaker">
This is enforcing a lecture style delivery with a disconnection between audience and speaker</h2>
I try my best to make my presentations (and lectures) as interactive as possible. I encourage interruptions and if we (the audience and I) go down a particular lane that isn't what I had planned: that's often just fine!<br />
<br />
There is time planned for questions at the end of the session but what if I want to ask the audience a question or if I welcomed a discussion midway through the presentation? Without being able to carefully ensure that this fits in the 20 second per slide constraint this is something that I simply won't be able to use.<br />
<h2 id="why-am-i-here">
<br /></h2>
<h2 id="why-am-i-here">
Why am I here?</h2>
When my frustrations with the format first began I thought that perhaps Paul and I should simply screencast our talk which would enable us to edit it carefully and have the 6 minutes and 40 seconds perfectly cut to a high standard. Thus, when it was our turn to 'talk' we could simply press play and sit back.<br />
<br />
Sadly this is not an option as everything is being run from a central computer through PowerPoint. In essence though, there is no point in us being here apart from taking the potential questions towards the end of the entire session (by which time the audience as a whole will have completely disconnected from our talk).<br />
<h2 id="looking-forward-to-the-conference">
<br /></h2>
<h2 id="looking-forward-to-the-conference">
Looking forward to the conference</h2>
I suppose this post stems from the fact that I'm a spoilt only child and don't like being told what to do. I think that I'm just unsure about everyone having to use the same thing (whatever that thing may be). We are all different with different presentation skills and styles. We should be 'allowed' to express ourselves.<br />
<br />
Ultimately <b>I am very much looking forward</b> to the conference and also am (despite what this post might indicate) optimistic about trying a different delivery format. I will try and <b>write a reflective post after the conference</b>: it would be awesome if I'm completely incorrect and Pechu Kechu is actually a <b>great initiative from the organisers </b>(who I'm sure have worked extremely hard to put on what will be a great conference).<br />
<br />
I have spoken to Paul about this but in no way mean to bring my co-authors in to this rant: this is my personal opinion :)<br />
<br />
Finally, so that there's something nice to look at here is a picture of Machu Picchu (from wikipedia) as that's what I've been calling Pechu Kucha for the past month or so as I've not been able to remember it's correct name:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://upload.wikimedia.org/wikipedia/commons/thumb/0/01/80_-_Machu_Picchu_-_Juin_2009_-_edit.2.jpg/285px-80_-_Machu_Picchu_-_Juin_2009_-_edit.2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://upload.wikimedia.org/wikipedia/commons/thumb/0/01/80_-_Machu_Picchu_-_Juin_2009_-_edit.2.jpg/285px-80_-_Machu_Picchu_-_Juin_2009_-_edit.2.jpg" /></a></div>
<br />Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-4212553888783541751.post-28789752706206194242014-04-26T03:57:00.002-07:002014-04-26T03:58:04.284-07:00Thinking about moving my blog...Over the Christmas break I moved my website that sat on a Google sites page to my own server and did this mainly to learn Django. I'm now really happy with my <a href="http://www.vincent-knight.com/" target="_blank">personal site</a> (modulo css which I'll fix when I have time) and like the workflow involved with updating the underlying database and the templates taking care of everything (a lot of my students in particular have commented on the ease of access to teaching resources on there).<br />
<br />
<b>I'm thinking of moving this blog over there too.</b><br />
<br />
The way I see it there are <b>good points </b>and <b>bad points </b>to this.<br />
<br />
Here is how I see the <b>bad points</b>:<br />
<br />
<ul>
<li>It'll be 'hard': blogger just takes care of everything for me.</li>
<li>I have a modest number of readers and it would be a shame to 'lose' them.</li>
<li>Disqus.com comments are great but I'm a huge <a class="g-profile" href="https://plus.google.com/101560853443212199687" target="_blank">+Google+</a> fan and like the interaction I get on comments with the <a class="g-profile" href="https://plus.google.com/110587955497525318489" target="_blank">+Blogger</a> / G+ thing.</li>
</ul>
<div>
Here is how I see the <b>good points:</b></div>
<div>
<ul>
<li>It'll be 'hard': I have a slight addiction to putting myself out of my comfort zone so learning how to set up my own RSS feed (which in practice should take 20 minutes of googling) would be good fun. A part from that it will actually be very easy.</li>
<li>I'll have more control: I've had issues with <a class="g-profile" href="https://plus.google.com/114096530864036991751" target="_blank">+MathJax</a> not playing nice with <a class="g-profile" href="https://plus.google.com/110587955497525318489" target="_blank">+Blogger</a> so if it's all on my server I won't have these problems.</li>
<li>I'll prefer the workflow: at the moment I write my posts in markdown, pandoc them and then copy the html and fix it in <a class="g-profile" href="https://plus.google.com/110587955497525318489" target="_blank">+Blogger</a>. With my own site, posting will be a simple git push away...</li>
</ul>
<div>
On reflection I think the only real <b>bad side</b> would be through potential loss of interaction / engagement but I also think that by simple sharing on Twitter and G+ not much would be lost.</div>
</div>
<div>
<br /></div>
<div>
Perhaps I'm wrong, if anyone has moved their blog and could offer me some advice that would be great. Also, how important is the RSS feed nowadays (personally most of the blogs I read get pushed to me by social networks and/or Google Now - I wonder how many people wouldn't have read this if it hadn't gotten to them via RSS)?</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-14792875841781238752014-04-04T10:34:00.002-07:002014-04-04T10:57:35.219-07:00A list of stuff for my student to look at before getting down to some Sage development<div style="color: #222222; font-family: arial; font-size: small;">
<a class="g-profile" href="https://plus.google.com/103944008095354003273" target="_blank">+James Campbell</a> will be <a href="http://www.vincent-knight.com/research/researchstudents/list/Summer/" target="_blank">working with me this Summer</a> on a project aimed at developing game theoretical stuff in to <a class="g-profile" href="https://plus.google.com/113421169347512599264" target="_blank">+Sage Mathematical Software System</a>. James just emailed me asking for a list of stuff he could/should read up on before he starts. I thought more knowledgeable people than me might be able to contribute so I've lazily copied my email to him here: </div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
------------ email ------------</div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<b>Code:</b></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
- git</div>
<div style="color: #222222; font-family: arial; font-size: small;">
- github (do <a class="g-profile" href="https://plus.google.com/104981548746793503207" target="_blank">+Daniele Procida</a>'s tutorial: <a href="https://dont-be-afraid-to-commit.readthedocs.org/en/latest/" style="color: #1155cc;" target="_blank">https://dont-be-<wbr></wbr>afraid-to-commit.readthedocs.<wbr></wbr>org/en/latest/</a>)</div>
<div style="color: #222222; font-family: arial; font-size: small;">
- sage development (tickets, documentation etc... This is something I don't know much about myself so read about it on the Safe site and watch videos on youtube there are a bunch of them)</div>
<div style="color: #222222; font-family: arial; font-size: small;">
- cython (<a href="http://cython.org/" style="color: #1155cc;" target="_blank">http://cython.org/</a> - watch this intro to Sage lecture by <a class="g-profile" href="https://plus.google.com/115360165819500279592" target="_blank">+William Stein</a>: <a href="https://www.youtube.com/watch?v=fI4NlMfGHC0" style="color: #1155cc;" target="_blank">https://www.youtube.<wbr></wbr>com/watch?v=fI4NlMfGHC0</a> that's the first lecture in a class he's currently giving you also could watch the rest)</div>
<div style="color: #222222; font-family: arial; font-size: small;">
- C (to help with cython - you don't necessarily need to be an expert I think)</div>
<div style="color: #222222; font-family: arial; font-size: small;">
- markdown (<a href="https://www.youtube.com/watch?v=6A5EpqqDOdk" style="color: #1155cc;" target="_blank">https://www.youtube.com/<wbr></wbr>watch?v=6A5EpqqDOdk</a>)</div>
<div style="color: #222222; font-family: arial; font-size: small;">
- <span style="font-family: arial, sans-serif; font-size: 13px;">Test driven development: (watch all this and you will know what I mean: </span><a href="https://www.youtube.com/playlist?list=PL5859017B018F03F4" style="color: #1155cc; font-family: arial, sans-serif; font-size: 13px;" target="_blank">https://www.youtube.com/<wbr></wbr>playlist?list=<wbr></wbr>PL5859017B018F03F4</a><span style="font-family: arial, sans-serif; font-size: 13px;">)</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif; font-size: 13px;">- ssh and *nix (so that you're comfortable to jump on to one of my machines if necessary - depending on time we might also get you to tweak the Cardiff server)</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif; font-size: 13px;">- matplotlib (the python library that Sage uses to plot stuff, good to know it from a python pov so as to be able to get Sage to make it do what we want - we might or might not use this)</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif; font-size: 13px;">- How Sage plots graphs (graph theory graphs like I used for this: </span><span style="font-family: arial, sans-serif;">http://goo.gl/KHGYk7 - we might or might not need this)</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;"><b>Game Theory:</b></span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;"><br /></span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;">- Matching games (<a href="http://www.vincent-knight.com/teaching/gametheory/matchinggames/" style="color: #1155cc;" target="_blank">http://www.vincent-knight.<wbr></wbr>com/teaching/gametheory/<wbr></wbr>matchinggames/</a>)</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;">- Cooperative game theory (<a href="http://www.vincent-knight.com/teaching/gametheory/cooperativegames/" style="color: #1155cc;" target="_blank">http://www.vincent-knight.<wbr></wbr>com/teaching/gametheory/<wbr></wbr>cooperativegames/</a>)</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;">We'll talk about this but 1 of the above </span><span style="font-family: arial, sans-serif;">(easy to code: 30 minutes of work)</span><span style="font-family: arial, sans-serif;"> will be a gentle appetiser to the 'piece de resistance': normal form games,</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;"><br /></span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;">- Normal form games (first 6 chapters of <a href="http://www.vincent-knight.com/teaching/gametheory/" style="color: #1155cc;" target="_blank">http://www.vincent-knight.<wbr></wbr>com/teaching/gametheory/</a>)</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;">- The lrs algorithm (there is an implementation of this written in c that we either want to re-write to get working in Sage so you'll need to understand it or get Sage to talk to it / use it, I know Sage kind of has this as an optional library but I'm not entirely sure how to 'get at it' <a href="http://cgm.cs.mcgill.ca/~avis/C/lrs.html" style="color: #1155cc;" target="_blank">http://cgm.cs.mcgill.ca/~avis/<wbr></wbr>C/lrs.html</a>)</span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<span style="font-family: arial, sans-serif;">- Polytopes, you want to be comfortable-ish with the vocabulary around polytopes to be able to understand the lrs algorithm a bit. </span></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<b>Books:</b></div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
- In general I'd say don't spend much money on Python books. Like most OSS stuff there's an awesome amount of stuff online. Take a look at: <a href="http://pythonbooks.revolunet.com/" style="color: #1155cc;" target="_blank">http://pythonbooks.<wbr></wbr>revolunet.com/</a> (a list of free Python books). There are various exceptions to this rule though.</div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
- With regards to Sage I don't think you need a book for this project (as it's about building stuff for Sage so mainly reading about the development process and watching youtube videos is the way to go), I have a kindle copy of <a href="http://goo.gl/q9s9da" style="color: #1155cc;" target="_blank">http://goo.gl/q9s9da</a>, it's not bad but really everything is online. If you haven't already take a look at <a href="http://sagemath.org/help.html" style="color: #1155cc;" target="_blank">http://sagemath.org/help.<wbr></wbr>html</a> and join the relevant discussion groups on there.</div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
- With regards to Game Theory there's a reading list on my website (all that follow are linked to on there). Webb's book is a gentle introduction, Algorithmic Game Theory is great and more about what you will be looking at. Finally there's a newish book by Maschler which looks really nice but I've not had time to work through it yet. In general my course site should suffice (reading/working through those books could take you years) with regards to what you need to know for game theory and I am certainly not asking you to spend money on a book. If there's a book (GT or code) that you really think would be useful let's talk.</div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
------------</div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
James is a pretty good coder with a good knowledge of a git based workflow already as his first year project (during which he actually learnt to code) has led his group to develop: <a href="http://thefightclub.herokuapp.com/">http://thefightclub.herokuapp.com/</a> which is also on github (if you've made your way this far, please click on that and waste a minute or 2 of your life).</div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
If there's anything missing from this list please add it to the comments :)</div>
<div style="color: #222222; font-family: arial; font-size: small;">
<br /></div>
<div style="color: #222222; font-family: arial; font-size: small;">
I'm looking forward to this project.</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-64152923569090786192014-03-27T14:13:00.001-07:002014-03-27T14:35:25.355-07:00Scheduling group presentations using Graph Theory and Sage.Yesterday (2014-03-26) I spoke at the <a href="http://www.enterprise.ac.uk/index.php/events/event/85-the-embedded-enterprise-exchange" target="_blank">Embedded Enterprise Exchange</a> about my new first year module. I used a Hangout on air during the talk and you can see it here:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/X6BrM3Tp4vE?feature=player_embedded' frameborder='0'></iframe></div>
That's not what I'm going to talk about here though. The course I talked baout ends with all the 'companies' (groups of 4 students) giving a $\approx 25$ minute talk.<br />
<br />
I need to schedule 40ish talks and this needs to fit around the student availability as well as my own. In this post I'll describe how I did this using a combination of Doodle, <a class="g-profile" href="https://plus.google.com/113421169347512599264" target="_blank">+Sage Mathematical Software System</a> and <a href="http://en.wikipedia.org/wiki/Graph_theory" target="_blank">Graph Theory</a>.<br />
<br />
The beginning of this post will be some of the boring details but towards the end I start talking about the mathematics (so feel free to skip to there...).<br />
<br />
<b>First of all I needed to know my students availability.</b><br />
<b><br /></b>
For this I simply used Doodle: <a href="https://doodle.com/">https://doodle.com</a>. I kind of use Doodle for every meeting I have to schedule (they also offer a cool tool that lets you show your availability so students/colleagues have an indication of when I might be able to meet with them).<br />
<br />
Here's a screenshot of the responses:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-KlgEzZCL-a4/UzR0FCMgDvI/AAAAAAABESM/9TYWiVqUsxU/s1600/Screenshot+2014-03-27+08.15.20.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-KlgEzZCL-a4/UzR0FCMgDvI/AAAAAAABESM/9TYWiVqUsxU/s1600/Screenshot+2014-03-27+08.15.20.png" height="116" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
You can't really see anything there as I had to zoom out a lot to grab the whole picture. Doodle allows you to download the information for any given poll in .xls format so I could relatively easily obtain the <b>biadjacency matrix </b>$M$<b> </b>for my problem. Where $M_{ij}$ is 1 if group $i$ is available for schedule slot $j$ and 0 otherwise.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<b>The mathematics and code needed.</b></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Once I've got a .csv file (by tweaking the .xls file) of the biadjacency matrix I import that in to <a class="g-profile" href="https://plus.google.com/113421169347512599264" target="_blank">+Sage Mathematical Software System</a> and convert it to an instance of the `Matrix` class using the following:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<code>import csv </code><br />
<code>f=open(DATA+'availabilitymatrix','r') </code><br />
<code>data = [[int(j) for j in row] for row in csv.reader(f)] </code><br />
<code>f.close() </code><br />
<code>M = Matrix(data)</code><br />
<br />
I then need to remove any particular scheduled slots that are not picked by any company:<br />
<br />
<span style="font-family: monospace;">M = matrix([row for row in M.transpose() if max(row) != 0]).transpose()</span><br />
<span style="font-family: monospace;"><br /></span>
Once I've done this I can define the <a href="http://en.wikipedia.org/wiki/Bipartite_graph" target="_blank">bi-partite graph</a> (bi-partite simply means that the vertices can be separated in to 2 non adjacent collections):<br />
<br />
<span style="font-family: monospace;">g = BipartiteGraph(M)</span><br />
<div>
<br /></div>
<div>
We can then get a get a picture of this, I do this using a 'partition' (a graph colouring) that will colour the groups (red) and the schedule slots (blue):</div>
<div>
<br /></div>
<div>
<span style="font-family: monospace;">g = BipartiteGraph(M</span><span style="font-family: monospace;">)</span><br />
<span style="font-family: monospace;">p = g.coloring()</span><br />
<span style="font-family: monospace;">g.show(layout='circular',dist=1,vertex_size=250, graph_border=True, figsize=[15,15],partition=p)</span></div>
<div>
<span style="font-family: monospace;"><br /></span></div>
<div>
The various options I pass to the `show` command are simply to get the circular arrangement (and other minor things):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-m2UyUkbBIUs/UzSY3gSByQI/AAAAAAABETk/01KEIUMI0Bg/s1600/sage0+(1).png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-m2UyUkbBIUs/UzSY3gSByQI/AAAAAAABETk/01KEIUMI0Bg/s1600/sage0+(1).png" height="400" width="400" /></a></div>
<br />
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div>
The above looks quite messy and what I essentially want is get as many pairwise matchings between the blue vertices (slots) and red vertices (companies) so that each schedule slot is attributed at most 1 company and every company has at least 1 schedule slot.</div>
<div>
<br /></div>
<div>
On any given graph $G=(V,E)$ this problem is known as looking for a maximal matching and can be written down mathematically:</div>
<div>
<br /></div>
<div>
<div>
<div style="text-align: center;">
Max: $\sum_{e \in E(G)} m_e$</div>
</div>
<div>
<div style="text-align: center;">
Such that: $\forall v$ $\sum_{e \in E(G) \atop v \sim e} m_e \leq 1$</div>
</div>
</div>
<div>
<br /></div>
<div>
We are in essence finding a subset of edges of our original graph in such a way as to maximise the number of edges such that no vertex has more than 1 edge.</div>
<div>
<br /></div>
<div>
This is all explained extremely well at the <a class="g-profile" href="https://plus.google.com/113421169347512599264" target="_blank">+Sage Mathematical Software System</a> documentation pages <a href="http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html#matching" target="_blank">here</a>.</div>
<div>
<br /></div>
<div>
Furthermore at the documentation the code needed to solve the problem is also given:</div>
<div>
<br />
<span style="font-family: monospace;">p = MixedIntegerLinearProgram() </span><br />
<span style="font-family: monospace;">matching = p.new_variable(binary=True)</span><br />
<span style="font-family: monospace;">p.set_objective(sum(matching[e] for e in g.edges(labels=False)))</span><br />
<span style="font-family: monospace;">for v in g:</span><br />
<span style="font-family: monospace;"> p.add_constraint(sum(matching[e]</span><br />
<span style="font-family: monospace;"> for e in g.edges_incident(v, labels=False)) <= 1)</span><br />
<span style="font-family: monospace;">p.solve()</span></div>
<div>
<span style="font-family: monospace;"><br /></span></div>
<div>
<div>
When I run the above, `p` is now a solved Mixed Integer Linear Program (corresponding to the matching problem described). To obtain the solution:</div>
</div>
<div>
<br /></div>
<div>
<span style="font-family: monospace;">matching = p.get_values(matching)</span><br />
<span style="font-family: monospace;">schedule = [e for e,b in matching.iteritems() if b == 1]</span><br />
<br />
<div>
Calling `schedule` gives a set of edges (denoted by the corresponding vertex numbers):</div>
</div>
<div>
<br /></div>
<div>
<span style="font-family: monospace;">[(5, 57), (0, 45), (23, 50), (4, 42), (38, 60), (26, 56), (34, 62), (16,</span></div>
<div>
<span style="font-family: monospace;">68), (1, 43), (7, 40), (9, 44), (36, 58), (12, 49), (35, 71), (28, 66),</span><br />
<span style="font-family: monospace;">(25, 47), (24, 53), (6, 46), (3, 64), (39, 67), (17, 69), (22, 55), (13,</span><br />
<span style="font-family: monospace;">48), (33, 41), (10, 63), (21, 61), (30, 52), (29, 65), (37, 70), (15,</span><br />
<span style="font-family: monospace;">54), (19, 51), (11, 59)]</span></div>
<div>
<span style="font-family: monospace;"><br /></span></div>
<div>
<div>
It is then really easy to draw another graph:</div>
</div>
<div>
<br /></div>
<div>
<span style="font-family: monospace;">B=Graph(schedule)</span><br />
<span style="font-family: monospace;">p = B.coloring()</span><br />
<span style="font-family: monospace;">B.show(layout='circular',dist=1,vertex_size=250, graph_border=True, figsize=[15,15],partition=p)</span></div>
<div>
<br /></div>
<div>
<div>
Which gives:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-f3-GJkXVxK0/UzSYuHrhepI/AAAAAAABETc/rVUfLnQ66Q8/s1600/sage0+(2).png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-f3-GJkXVxK0/UzSYuHrhepI/AAAAAAABETc/rVUfLnQ66Q8/s1600/sage0+(2).png" height="400" width="400" /></a></div>
<br />
<br /></div>
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div>
You can see that the obtained graph has all the required properties and most importantly is a lot less congested.</div>
<div>
<br /></div>
<div>
<b>Some details.</b></div>
<div>
<b><br /></b></div>
<div>
I'm leaving out some details, for example I kept track of the names of the companies and also the slots so that the final output of all this looked like this:</div>
<div>
<br /></div>
<div>
<div>
<div>
4InARow: Fri1100</div>
<div>
Abacus: Tue0930</div>
<div>
Alpha1: Thu1130</div>
<div>
Alpha2: Mon0930</div>
<div>
AusfallLtd: Fri1230</div>
<div>
AxiomEnterprise: Thu1000</div>
<div>
Batduck: Thu1430</div>
<div>
CharliesAngles: Thu1500</div>
<div>
CwmniRhifau: Mon1330</div>
<div>
EasyasPi: Fri1130</div>
<div>
Evolve: Thu1300</div>
<div>
HSPLLtd.: Mon1030</div>
<div>
JECT: Tue1200</div>
<div>
JJSL: Thu1030</div>
<div>
JNTL: Mon1400</div>
<div>
JennyCash: Tue1630</div>
<div>
KADE: Fri1330</div>
<div>
MIAS: Fri1300</div>
<div>
MIPE: Thu1100</div>
<div>
MLC: Tue1600</div>
<div>
Nineties: Mon0900</div>
<div>
Promis: Fri1400</div>
<div>
R.A.C.H: Tue1530</div>
<div>
RYLR: Tue1230</div>
<div>
SBTP: Fri1030</div>
<div>
Serendipity: Mon1230</div>
<div>
UniMath: Tue1300</div>
<div>
VectorEnterprises: Tue1330</div>
<div>
Venus: Thu1400</div>
<div>
codeX: Mon1300</div>
<div>
dydx: Wed1630</div>
<div>
eduMath: Thu0930</div>
<div>
</div>
</div>
<div>
<br /></div>
</div>
<div>
(BatDuck is my favourite company name by far...)</div>
<div>
<br /></div>
<div>
<div>
<b>Why did I do this this way?</b></div>
</div>
<div>
<b><br /></b></div>
<div>
There are 3 reasons:</div>
<div>
<br /></div>
<div>
1. I shared the schedule with my students through a published Sage sheet on our server. That way they can see a direct applied piece of mathematics and can also understand some of the code if they wanted to.</div>
<div>
2. "<b>Point and click doesn't scale" </b>- I'm sure I could have solved this one instance of my problem with pen and paper and some common sense faster than it took me to write the code to solve the problem. The thing is next year when I need to schedule these talks again it will at most take me 3 minutes as the code is all here and ready to go. (Most readers of this blog won't need that explained but if any of my students find their way here: that's an important message for you).</div>
<div>
3. It was fun.</div>
<div>
<b><br /></b></div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-59969984702090830612014-03-23T10:21:00.001-07:002014-03-23T13:26:39.548-07:00Basketball and cooperative games in classHere is the state of my class after my students learnt about cooperative game theory (<a href="http://www.vincent-knight.com/teaching/gametheory/cooperativegames/" target="_blank">Chapter 16 of my course</a>):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-bs5ybOY1o7Q/Uy8HBYKtKmI/AAAAAAABD-U/-44tWAgxW6I/s1600/IMG_20140321_160249.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-bs5ybOY1o7Q/Uy8HBYKtKmI/AAAAAAABD-U/-44tWAgxW6I/s1600/IMG_20140321_160249.jpg" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Cooperative game theory is concerned with situations where coalitions are allowed to form in game theoretic situations. In my class the particular aspect we consider is the Shapley value which is of interest when sharing a particular commodity amongst a group of player who each contribute to the commodity differently.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
I use this in practice when dealing with attributing individual marks to a group project: you can read about that <a href="http://goo.gl/qD6KJX" target="_blank">here</a>.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
To introduce this I asked 3 students to come down and play a game: $S$, $L$ and $C$ volunteered (or at least gave a lazy nod when I asked if anyone had played basketball before) to come down.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
They had 20 seconds to get as many crumpled up pieces of paper as possible in the bin above (it was on the table). The paper was stapled and it needed to be separated and crumpled so I suggested that perhaps 1 or 2 of them could spend some of the 20 seconds separating and crumpling.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
We played this 3 times and it was all good fun. After $S$, $L$ and $C$ had their go 3 other students thought they could do better (no comment).</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
After that I asked the class how we could share out the 10 chocolates between $S$, $L$ and $C$: what would be the fair way? After some discussion it was clear that L had made the biggest contribution to the group for example and so this was not a trivial question.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
After a little while I started to ask 'how many do you think $L$ and $C$ would have had together? etc... We wrote down the <b>characteristic function</b> for our game:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
$$v(C)=\begin{cases}4, & C=\{S\}\\2, & C=\{C\}\\6, & C=\{L\}\\4, & C=\{S,C\}\\8, & C=\{S,L\}\\10, & C=\{C,L\}\\10, & C=\Omega\end{cases}$$</div>
<br />
<br />
where $\Omega$ denotes the grand coalition.<br />
<br />
At this point one student suggested that we somehow needed to take all this information in to account. He couldn't quite articulate how to do that but he's completely correct.<br />
<br />
The way to share the chocolates 'fairly' is to consider all permutations of the players and consider <b>marginal contributions </b>for each permutation (<a href="http://vincent-knight.com/teaching/gametheory/cooperativegames/" target="_blank">take a look at my notes</a> to read about that some more).<br />
<br />
Let me try and explain with an example:<br />
<br />
For the first permutation $\pi=(S,C,L)$ we calculate the contribution of $S$ first: $4$. We then calculate the marginal contribution of $C$ to the coalition $\{S,C\}$, which from above has value $4$ so $C$ <i>needs </i>to contribute 0. Finally $L$ needs to contribute $6$.<br />
<br />
For the second permutation $\pi=(S,L,C)$ we calculate the contribution of $S$ first: $4$ (again). We then calculate the marginal contribution of $L$ to the coalition $\{S,L\}$, which from above has value $8$ so $L$ <i>needs </i>to contribute 4. Finally $C$ needs to contribute $2$.<br />
<br />
Here's all the marginal contributions for each permutation:<br />
<br />
<ul>
<li>$(S,C,L)$ gives: $(4,0,6)$</li>
<li>$(S,L,C)$ gives: $(4,2,4)$</li>
<li>$(C,S,L)$ gives: $(2,2,6)$</li>
<li>$(C,L,S)$ gives: $(0,2,8)$</li>
<li>$(L,S,C)$ gives: $(2,2,6)$</li>
<li>$(L,C,S)$ gives: $(0,4,6)$</li>
</ul>
<div>
We calculate the average values of the contribution vector (indexed by the players) to give the Shapley value:</div>
<div>
<br /></div>
<div>
$$\phi=(2,2,6)$$</div>
<div>
<br /></div>
<div>
This was good fun and I'm really happy with the discussion that lead us to the calculations and it was also fun to get students to mess around in class.<br />
<br />
Here's one (of my most viewed!) <a class="g-profile" href="https://plus.google.com/115229808208707341778" target="_blank">+YouTube</a> videos that I put together on it:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/aThG4YAFErw?feature=player_embedded' frameborder='0'></iframe></div>
<br /></div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-73703949238115326272014-03-22T05:59:00.000-07:002014-03-22T06:18:04.081-07:00Matching games in classLast week after looking at <a href="http://drvinceknight.blogspot.co.uk/2014/03/playing-stochasticmarkov-games-in-class.html" target="_blank">stochastic games</a> we looked at matching games (corresponding to <a href="http://goo.gl/Ur0Pbw" target="_blank">Chapter 15 </a>of my course). There's an awesome video on <a class="g-profile" href="https://plus.google.com/115229808208707341778" target="_blank">+YouTube</a> describing the problem:<br />
<div style="text-align: center;">
<br /></div>
<div style="text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="315" src="//www.youtube.com/embed/w1leqkpDaRw" width="560"></iframe><br /></div>
<div style="text-align: center;">
<br /></div>
I thought about possibly getting 6 students to form two groups (a set of reviewers and a set of suitors); ranking each other and then getting the class to put together a stable matching. I thought twice about this though as I'm sure it's the kind of thing that could get me fired so instead I brought 3 toys along to class with me:<br />
<br />
<br />
<ul>
<li>A tech deck (finger skateboard: <a href="http://www.techdeck.com/">http://www.techdeck.com/</a>)</li>
<li>The best teenage mutant ninja turtle: Donatello</li>
</ul>
<div>
Both of those you can see in this picture:</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-nY40b_Q9WmU/UaSA0h7nICI/AAAAAAAAuCw/SCo9r-kygWY/w854-h641-no/IMG_20130528_105148.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-nY40b_Q9WmU/UaSA0h7nICI/AAAAAAAAuCw/SCo9r-kygWY/w854-h641-no/IMG_20130528_105148.jpg" height="298" width="400" /></a></div>
<br />
<ul>
<li>The third toy I brought was my favourite nerf gun (the 'Praxis'):</li>
</ul>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-Ab2rbOd6G2g/Tk6L_jXo5kI/AAAAAAAADx8/Engsc6tLlw0/s1600/Nerf+Vortex+Praxis+-+03.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-Ab2rbOd6G2g/Tk6L_jXo5kI/AAAAAAAADx8/Engsc6tLlw0/s1600/Nerf+Vortex+Praxis+-+03.JPG" height="240" width="320" /></a></div>
<div>
<br /></div>
<br />
<br />
I actually named 'her' Zoe; after my wife (<a class="g-profile" href="https://plus.google.com/118015436149244712749" target="_blank">+Zoë Prytherch</a>).<br />
<br />
Three students ('A', 'S' and 'R') came down and agreed to put together their ranking of which toy they preferred:<br />
<br />
- A: Donatello, Zoe, Deck<br />
- S: Zoe, Donatello, Deck<br />
- R: Donatello, Zoe, Deck<br />
<br />
I came up with a pretty random preference for the toys:<br />
<br />
- Donatello: R, S, A<br />
- Deck: A, R, S<br />
- Zoe: R, S, A<br />
<br />
<br />
We then discussed possible matchings and allocations of the toys (if we came to a stable one A, R and S could stick with that toy for the rest of the lesson). Here is one example that's close to what was suggested (I didn't record it and I don't quite remember it):<br />
<br />
- A gets Donatello;<br />
- S gets Zoe;<br />
- R gets Deck<br />
<br />
The thing with this is that Donatello prefers R and R prefers Donatello to their current match so the above is <b>not stable</b>.<br />
<br />
After some more discussion we came up with the following stable matching:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-jLS8p1dgObo/UyrBZCq-T0I/AAAAAAABDvk/ghXYrJ5-XTw/s1600/IMG_20140318_115804.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-jLS8p1dgObo/UyrBZCq-T0I/AAAAAAABDvk/ghXYrJ5-XTw/s1600/IMG_20140318_115804.jpg" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
We see that whilst A is with his 'least preferred' option (the Deck): no one prefers A to their current matching so A does not have an incentive to change his current matching.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The entire matching is stable because we can't find any pair that has an incentive to move.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
In class we then went over the Gale-Shapley algorithm which is an algorithm that guarantees a stable matching. A cool thing is that this algorithm gives (out of all possible stable matchings) the one that is optimal from the suitors point of view and also the worst possible one from the reviewers point of view.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
In our case above the matching found is also the matching found through the Gale-Shapley algorithm so sadly for 'A' there is no stable way of matching him to anything but his worst preferred toy and 'S' gets my wife no matter what.</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-1402799115483726162014-03-20T03:02:00.003-07:002014-03-20T03:53:44.874-07:00Playing Stochastic/Markov games in classIn class on Monday my students and I looked at Stochastic games (<a href="http://www.vincent-knight.com/teaching/gametheory/stochasticgame/" target="_blank">Chapter 14 of my course notes</a>). I decided to play a tournament similar to the iterated games that we played previously (corresponding to Chapters <a href="http://www.vincent-knight.com/teaching/gametheory/finitelyrepeatedgames/" target="_blank">9</a> and <a href="http://www.vincent-knight.com/teaching/gametheory/infinitelyrepeatedgames/" target="_blank">10</a>). I've blogged about them <a href="http://drvinceknight.blogspot.co.uk/2014/02/iterated-prisoners-dilemma-tournament.html" target="_blank">here</a> and <a href="http://drvinceknight.blogspot.co.uk/2014/02/iterated-prisoners-dilemma-tournament.html" target="_blank">here</a>.<br />
<br />
In short, a stochastic game is a collection of states that themselves correspond to games. After players select strategies at a given state/game the next game they play (or state they are in) is given by a probability distribution.<br />
<br />
This is a bit like playing in a casino where the table you play at depends on what happened at the previous table you played.<br />
<br />
*The game we played in class corresponds to a casino with two tables:*<br />
<br />
- At the first table we play a simple prisoner's dilemma (players aiming to <b>maximise</b>) their utility:<br />
<br />
$$\begin{pmatrix}<br />
(2,2)&(0,3)\\<br />
(3,0)&(1,1)<br />
\end{pmatrix}$$<br />
<br />
The probability distribution at this table (indicating what game we played next) is given by:<br />
<br />
$$\begin{pmatrix}<br />
(.75,.25)&(0,1)\\<br />
(0,1)&(.5,.5)<br />
\end{pmatrix}$$<br />
<br />
- If both players cooperate (getting a utility of $2$ each) then there is a 75% chance that they play at this same table again.<br />
- If only one player cooperates and the other defects (the defector getting a utility of $3$ and the cooperator a utility of $0$) then the players move to the other game with 100% probability.<br />
- If both players defect (each getting a utility of $1$) then they will play the same game with 50% chance.<br />
<br />
- The second table was a <b>dummy game</b> that basically ended the game:<br />
<br />
$$\begin{pmatrix}<br />
(0&0)<br />
\end{pmatrix}$$<br />
<br />
The probability distribution for this game is $(0,1)$.<br />
<br />
The assumption made in this class is that the games are played infinitely and as such a discounting factor $\delta$ is used. When playing this in class we interpreted the discounting factor as the probability of the game continuing. So the game ended when the probabilities indicated that we were in the second game <b>or </b>when the discounting factor said so (we used $\delta=1/2$).<br />
<br />
<b>The class formed 4 teams and we played a round robin.</b><br />
<b><br /></b>
The first round had <i>Tom's Team </i>go up against <i>Team Roy</i> and <i>Barmy </i>go up against <i>4:</i><br />
<i><br /></i>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-7KqQGby0h9M/Uyq441j1c4I/AAAAAAABDuM/Cm6TV6xU_mY/s1600/IMG_20140318_103800.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-7KqQGby0h9M/Uyq441j1c4I/AAAAAAABDuM/Cm6TV6xU_mY/s1600/IMG_20140318_103800.jpg" height="300" width="400" /></a></div>
<i><br /></i>
We see that <i>Tom's team</i> and <i>Team Roy</i> cooperated both times before the game ended whilst <i>4</i> defected from the start against <i>Barmy.</i><br />
<br />
The next round had <i>Barmy</i> go up against <i>Tom's Team </i>and <i>Team Roy </i>go up against <i>4:</i><br />
<i><br /></i>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-cHFmzK3Tc6U/Uyq5vLA5AKI/AAAAAAABDuc/53FvVSmFhPU/s1600/IMG_20140318_103803.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-cHFmzK3Tc6U/Uyq5vLA5AKI/AAAAAAABDuc/53FvVSmFhPU/s1600/IMG_20140318_103803.jpg" height="228" width="400" /></a></div>
<i><br /></i>
We see that <i>Barmy </i>and <i>Team Roy </i>both cooperated before the game ended and <i>Team Roy </i>and <i>4 </i>both defected before the game ended.<br />
<br />
The last game had <i>Tom's Team</i> go up against <i>4 </i>and <i>Team Roy</i> go up against <i>Barmy. </i>Below you can also see the final cumulative scores:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-DVtYbh2u-Co/Uyq6WzI0OhI/AAAAAAABDus/Dwcsafer3u0/s1600/IMG_20140318_103748.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-DVtYbh2u-Co/Uyq6WzI0OhI/AAAAAAABDus/Dwcsafer3u0/s1600/IMG_20140318_103748.jpg" height="400" width="251" /></a></div>
<br />
As you can see <i>Tom's Team </i>won <i>(</i><a href="http://goo.gl/m7K4fn" target="_blank">the name is after +Paul Harper son Tom joined the class during which we played the iterated prisonder's dilemma</a>).<br />
<br />
To decide who came second (they could choose the second prize to either be apples or party rings) a best of three game of <a href="http://goo.gl/7Vv2sB" target="_blank">Rock, Paper, Scissors, Lizard, Spock </a>was played with Joe winning the party rings for <i>Team Roy </i>('Scissors decapitates lizard').<br />
<i><br /></i>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-9GwE3nAiK6o/Uyq7Nuz4vzI/AAAAAAABDvA/deKKsY1tlzw/s1600/IMG_20140318_103750.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-9GwE3nAiK6o/Uyq7Nuz4vzI/AAAAAAABDvA/deKKsY1tlzw/s1600/IMG_20140318_103750.jpg" height="257" width="400" /></a></div>
<i><br /></i>
<br />
I think this was good fun and hopefully enabled the students to have a sound grasp of what is meant by a state, a transition, etc..<br />
<br />
Interestingly all teams happened to play <b>Markov Strategies</b> (i.e. in any given game they all did the same thing in each state) although this might have been different if the probabilities allowed the game to last longer. In the course we are restricting ourselves to Markov strategies.<br />
<br />
After playing this we went through obtaining 2 equilibria for this game (both players defecting <b>and </b>both players cooperating).<br />
<br />
Here are some photos that a student grabbed during the class and also a re-share of the gif of <a class="g-profile" href="https://plus.google.com/103137876942082024919" target="_blank">+Paul Harper</a>'s son Tom using a Nerf gun on those who defected against his team during the Prisoner's dilemma tournament:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-w92ZA35laww/Uyq8caKOtpI/AAAAAAABDvQ/cQyzESwM3RE/s1600/20140318_103442.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-w92ZA35laww/Uyq8caKOtpI/AAAAAAABDvQ/cQyzESwM3RE/s1600/20140318_103442.jpg" height="225" width="400" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-h7h6edXymJE/Uyq8cR_OI1I/AAAAAAABDvM/S-NhmO6Xods/s1600/20140318_103820.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-h7h6edXymJE/Uyq8cR_OI1I/AAAAAAABDvM/S-NhmO6Xods/s1600/20140318_103820.jpg" height="225" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-nTA0fMmURnU/Uwpkm61xHEI/AAAAAAABCNQ/mmvFrvOxQIU/s1600/IMG_20140221_154617-MOTION.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-nTA0fMmURnU/Uwpkm61xHEI/AAAAAAABCNQ/mmvFrvOxQIU/s1600/IMG_20140221_154617-MOTION.gif" height="298" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-64470846165522239402014-03-10T14:55:00.000-07:002014-03-10T14:59:33.964-07:00Playing a game with incomplete information in classIn class today we took a look at games of incomplete information. Loosely this relates to any kind of game that involves the players not knowing 'everything'.<br />
<br />
Next week we'll be looking at stochastic/Markov games (<a href="http://www.vincent-knight.com/teaching/gametheory/stochasticgame/" target="_blank">C13</a> of my course) but this week we took a look at incomplete information in extensive form games (<a href="http://www.vincent-knight.com/teaching/gametheory/incompleteinformation/" target="_blank">C12</a> of my course).<br />
<br />
We played the following game (a generalization of the matching pennies game that I've <a href="http://goo.gl/vc0BYz" target="_blank">blogged about before</a>):<br />
<br />
"Player 1 picks Heads or Tails, a coin is flipped and Player 2 is aware of the result of that coin (but not the choice of Player 1), Player 2 then picks Heads or Tails. The is akin to a matching pennies game except that if Player 2 loses whilst picking the same as the random coin then the outcome is $(0,0)$."<br />
<br />
Here is a game tree that describes the game:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://drvinceknight.github.io/Year_3_game_theory_course/Activities/matchingpenniesunderuncertainty.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://drvinceknight.github.io/Year_3_game_theory_course/Activities/matchingpenniesunderuncertainty.png" height="226" width="400" /></a></div>
<br />
On a slight tangent our School operates a mid-module feedback system which is not 'official' but allows us to get some feedback from students with regards to how the course is going so far. One piece of feedback I got was something like:<br />
<br />
<div style="text-align: center;">
<i>"The chocolates are making me fat bring fruit instead."</i></div>
<div style="text-align: center;">
<i><br /></i></div>
<div style="text-align: left;">
I'm pretty sure this was tongue in cheek but I brought in the following as a prize for the winner of a 3 player round robin (using the above game):</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/--UyTdPHJC2k/Ux3Rw7IRVGI/AAAAAAABDD8/0bFQnalRAKw/w426-h320/IMG_20140310_145144.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/--UyTdPHJC2k/Ux3Rw7IRVGI/AAAAAAABDD8/0bFQnalRAKw/w426-h320/IMG_20140310_145144.jpg" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="font-size: x-small;">(A melon and some fizzy cherries)</span></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="font-size: x-small;"><br /></span></div>
<div class="separator" style="clear: both; text-align: left;">
As I said, I got 3 students (referred to as S, A. R) to play a round robin tournament where each would play each other twice (swapping being player 1).</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The results are here (thanks to <a class="g-profile" href="https://plus.google.com/104243854554833157722" target="_blank">+Jason Young</a> for collecting them):</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-HLNaWwmXcR8/Ux4xVlhiJwI/AAAAAAABDEk/AcaKed3rkF8/s1600/IMG_20140310_172233.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-HLNaWwmXcR8/Ux4xVlhiJwI/AAAAAAABDEk/AcaKed3rkF8/s1600/IMG_20140310_172233.jpg" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
In that photo we see the following match ups:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
- Game 1 and Game 2: A versus S</div>
<div class="separator" style="clear: both; text-align: left;">
- Game 3 and Game 4: R versus S</div>
<div class="separator" style="clear: both; text-align: left;">
- Game 5 and Game 6: A versus R</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
What we see is that R actually won with a final cumulative score of 3, A finished with -1 and S with -2. Looking through the details we see that A and S both went "against" the coin both times whereas R went "against" the coin once.</div>
<br />
I asked the class if anyone had an idea of how one <b>should</b> play the game. One student (<a href="http://drvinceknight.blogspot.co.uk/2014/02/iterated-prisoners-dilemma-tournament.html" target="_blank">who I think was from the team Roy crowd</a>) yelled out that one should always go with the coin.<br />
<br />
This is exactly correct, the way to 'prove it' it is to obtain the corresponding normal form game for the extensive form game. We do this by using <b>expected values over the random nodes:</b><br />
<b><br /></b>
We have $S_1=\{H,T\}$ and $S_2=\{HH, HT, TH, TT\}$. The strategy set for player 2 indicates what player 2 should do for each possible flip of the random coin: so $HT$ indicates playing $H$ if the coin flips Heads and playing $T$ if the coin flips Tails (so $HT$ corresponds to agreeing with the coin, $TH$ corresponds to going against the coin etc...).<br />
<b><br /></b>
<b>Using the above strategy ordering we get the following normal form game:</b><br />
<b><br /></b>
$$<br />
\begin{pmatrix}<br />
(1/2,-1/2)&(-1/2,1/2)&(0,0)&(-1,1)\\<br />
(-1,1)&(-1/2,1/2)&(0,0)&(1/2,-1/2)<br />
\end{pmatrix}<br />
$$<br />
<br />
I will skip the analysis of this game (which we did in class) but it can be shown that the Nash equilibrium is for player 1 to play Heads with probability between 1/3 and 2/3 and player 2 to agree with the random coin.<br />
<br />
<b>Importantly, </b>at the end of the game the victor: R gave the melon to A. I hope he enjoys it and also that my students found this exercise slightly useful and perhaps slightly more memorable.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-70143541057348737932014-03-09T11:37:00.001-07:002014-03-09T11:40:54.208-07:00A (very) brief interactive look at evolutionary game theory in classIn class last week my students and I started looking at evolutionary game theory (Chapters <a href="http://goo.gl/BeMXDt" target="_blank">11</a> and <a href="http://www.vincent-knight.com/teaching/gametheory/essandne/" target="_blank">12</a> of my class). One concept of evolutionary game theory that is important to understand is that in a sense the barrier between strategies and players becomes a bit fuzzy.<br />
<br />
To try and illustrate this in class I brought in 2 packs of cards. I actually ended up only using the cards as binary markers (whether or not they were facing 'UP' or 'DOWN'). I then proceeded to describe the following:<br />
<br />
"If an UP card interacts with a DOWN card in any given round the DOWN card changes to UP on the next round. Otherwise everything else stays the same."<br />
<br />
I used this game to illustrate how a strategy $\sigma$ can induce a population vector $\chi$ and I also touched upon what we would mean by $\sigma$ being stable.<br />
<br />
We played the following games:<br />
<br />
---------------<br />
<br />
The left half the class was told to play UP and the other half to play DOWN. Thus our initial value of $\chi=(.5,.5)$. This was given by the fact that half the population was playing $\sigma=(1,0)$ and the other half playing $\sigma(0,1)$.<br />
<br />
<div>
<br /></div>
<div>
We played a couple of rounds (which was fairly academic as the outcome is obvious) and arrived at a final population vector of $\chi=(1,0)$ (all the DOWN cards had been changed to UP cards). This is a <b>stable</b> population.</div>
<div>
<br /></div>
<div>
I asked what would happen if I nudged the population by introducing some more DOWN cards in to the population, to perhaps $\chi=(.9,1)$. Everyone realised that the population would swiftly move right back to $\chi=(1,0)$.</div>
<div>
<br /></div>
<div>
We also talked about what would happen if we started with $\chi=(0,1)$ (all cards started as DOWN), everyone realised that $\chi$ would not change over time as we played (since there were no UP cards to force a change). This is also a stable population.</div>
<div>
<br /></div>
<div>
It's obvious though that if we introduce some UP cards (say nudging the population to $\chi=(.1,.9)$) then the population would swiftly move to $\chi=(1,0)$.</div>
<div>
<br /></div>
<div>
<b>The difference between these two stable populations is that one stays stable under evolutionary conditions.</b></div>
<div>
<b><br /></b></div>
<div>
That basically leads us to the definition of an evolutionary stable strategy.</div>
<div>
<br /></div>
<div>
<div>
</div>
</div>
<br />
---------------<br />
<div>
<br /></div>
<div>
The next game we played was to ask students to randomly (with equal probability) assign themselves a strategy: so everyone was playing a strategy $\sigma=(.5,.5)$.</div>
<div>
<br /></div>
<div>
I won't go in to the details of what we did with that (mainly re-confirming the above conclusions) but the important part is to see that any given population vector $\chi$ can be induced by a strategy vector $\sigma$. This leads to the idea of considering whether or not a strategy is evolutionary stable which corresponds to whether or not it is stable in the population that it induces.</div>
<div>
<br /></div>
<div>
---------------</div>
<div>
<br /></div>
<div>
With more time I would have liked to do more with the cards and played more games...</div>
<div>
<br /></div>
<div>
---------------</div>
<div>
<br /></div>
<div>
Tomorrow we'll be talking about pairwise contest games and the connection between normal form games and evolutionary games.</div>
<div>
<br /></div>
<div>
Here's a video that I put together a while ago that shows some code that allows us to investigate emergent behaviour:</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/Tz-lZy0AKRI?feature=player_embedded' frameborder='0'></iframe></div>
<div>
<br /></div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-77019090513619420212014-02-27T13:18:00.002-08:002014-02-27T13:31:42.574-08:00Iterated Prisoner's Dilemma with a twist in ClassIn my last blog post I described the iterated prisoner's dilemma tournament that my students played in class: '<a href="http://drvinceknight.blogspot.co.uk/2014/02/iterated-prisoners-dilemma-tournament.html" target="_blank">Iterated Prisoner's Dilemma Tournament in Class</a>'. This was great fun and one team even got the idea of how to define a strategy in a repeated game.<br />
<br />
That class activity corresponded to <a href="http://www.vincent-knight.com/teaching/gametheory/finitelyrepeatedgames/" target="_blank">this chapter</a> of my class during which we looked at subgame perfect Nash equilibrium.<br />
<br />
Let us look at the Prisoner's dilemma that we played:<br />
<br />
\[\begin{pmatrix}<br />
(2,2)&(5,0)\\<br />
(0,5)&(4,4)<br />
\end{pmatrix}\]<br />
<br />
If both players cooperate for 3 rounds then they both get a utility of \(2\times3=6\).<br />
<br />
The <a href="http://goo.gl/nW9j68" target="_blank">next chapter</a> of my class looks at what is called 'infinitely repeated games', in this it is assumed that players play an infinite number of rounds. We use the usual mathematical trick to handle infinite sums so that we can compute finite utilities.<br />
<br />
For example the utility to both players for always cooperating is given by:<br />
<br />
\[\sum_{t=1}^{\infty}\delta^{t-1}2=\frac{2}{1-\delta}\]<br />
<br />
Where \(0 < \delta < 1\).<br />
<br />
The utility to both players always defecting is given by:<br />
<br />
\[\sum_{t=1}^{\infty}\delta^{t-1}4=\frac{4}{1-\delta}\]<br />
<br />
The 'discounting factor' \(\delta\) allows us to compare these two strategies: if both players defect they do worse then if they both cooperated.<br />
<br />
There are various interpretations for \(\delta\), one of which is the probability with which a game continues (ie we allow for the possibility for the game to end at each round), thus the above calculation become an expected value calculation.<br />
<br />
To illustrate this I brought a dice in to class and had <a class="g-profile" href="https://plus.google.com/104243854554833157722" target="_blank">+Jason Young</a> run a tournament during which the game could end based on a chosen probability.<br />
<br />
Here are the first set of results (we played with \(\delta=.75\) so we carried on as long as my <a href="http://goo.gl/mZgNzA" target="_blank">d20</a> < 16):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-LhKIZS-4lt8/Uw-m5HWTE5I/AAAAAAABCXY/CXVaKgQ7Vak/s1600/IMG_20140224_163207.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-LhKIZS-4lt8/Uw-m5HWTE5I/AAAAAAABCXY/CXVaKgQ7Vak/s1600/IMG_20140224_163207.jpg" height="300" width="400" /></a></div>
<br />
Team Laurence got pretty lucky (players are here trying to reduce the 'amount of time they spend in prison') with their roles and twice only had to play one round!<br />
<br />
Here's the overall standings (as well as some other details):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-bjzILFC8QY4/Uw-oCbgR1iI/AAAAAAABCXk/0Rs82EmSekg/s1600/IMG_20140224_163202.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-bjzILFC8QY4/Uw-oCbgR1iI/AAAAAAABCXk/0Rs82EmSekg/s1600/IMG_20140224_163202.jpg" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Team Cymru's huge score can be explained by two factors: lack of luck with the dice and they also formed a coalition with team Laurence.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
After this we still had 30 minutes spare in the class so I offered ending there or playing another round. My students made me smile by mostly staying and playing another round. In fact they even pointed out that technically they shouldn't be able to watch the progression of the game (ie seeing how other teams were acting). So they suggested that the teams who weren't playing would go stand in the corridor (I thought this was cool to come from them).</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
We also changed the value of \(\delta\) to \(.25\) (so games only continued 25% of the time). Here are the results:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-OU0d4Bot1Uk/Uw-plBe2IEI/AAAAAAABCXw/piXKXcG8zag/s1600/IMG_20140224_165518.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-OU0d4Bot1Uk/Uw-plBe2IEI/AAAAAAABCXw/piXKXcG8zag/s1600/IMG_20140224_165518.jpg" height="320" width="240" /></a></div>
<br />
This is the last round (they're on separate boards because I had to hide/erase/etc...):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-wjNMdGE3CB4/Uw-plFBVedI/AAAAAAABCXw/3Vuk-VVB3PA/s1600/IMG_20140224_165521.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-wjNMdGE3CB4/Uw-plFBVedI/AAAAAAABCXw/3Vuk-VVB3PA/s1600/IMG_20140224_165521.jpg" height="320" width="240" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
The outcome was team Roy and Cymru both tied for the win at 8 (Roy did this with well timed defections and Cymru managed to cooperate successfully a couple of times).<br />
<br />
At this point I wasn't really sure what to use as a tie breaker but someone in class yelled: 'Rock, Paper, Scissors, Lizard, Spock'. We actually played this in class a while back when we started looking at mixed strategies, I blogged about it here: <a href="http://goo.gl/7Vv2sB" target="_blank">'A Rock, Paper, Scissors, Lizard, Spock Tournament in class'</a><br />
<br />
Here's the outcome of that:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-YJqo0QrZBKI/Uw-qvCpL6wI/AAAAAAABCX8/HvfiGaM2mgE/s1600/IMG_20140224_165320.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-YJqo0QrZBKI/Uw-qvCpL6wI/AAAAAAABCX8/HvfiGaM2mgE/s1600/IMG_20140224_165320.jpg" height="240" width="320" /></a></div>
<br />
Joe won it for team Roy.<br />
<br />
This was great fun and will hopefully be useful to help my students contextualise one of the ideas of this chapter: it's actually possible to find a value of \(\delta\) for which students should cooperate. I'm not sure this was made evident by the activity but we did see more cooperation for lower values of \(\delta\).Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-39551483900135251932014-02-23T13:32:00.002-08:002014-02-23T14:11:11.374-08:00Iterated Prisoner's Dilemma Tournament in ClassOn Friday my students and I played an iterated <a href="http://en.wikipedia.org/wiki/Prisoner's_dilemma" target="_blank">Prisoner's Dilemma</a> tournament in class.<br />
<br />
This is something that I've run many times before with <a class="g-profile" href="https://plus.google.com/103137876942082024919" target="_blank">+Paul Harper</a> during outreach events and I've blogged about it <a href="http://goo.gl/5u6Ic" target="_blank">here</a> and <a class="g-profile" href="https://plus.google.com/107135522210834007871" target="_blank">+Dana Ernst</a> ran something similar and blogged about it <a href="http://danaernst.com/tag/game-theory/" target="_blank">here</a> (both those posts also talk about 2/3rds of the average games).<br />
<br />
The way I do this is to split the class in to 4 teams and play a round robin of a set of 5 to 8 repetitions of the Prisoner's Dilemma:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/ED9gaAb2BEw?feature=player_embedded' frameborder='0'></iframe></div>
<br />
<br />
The particular version of the game I usually use is given below:<br />
<br />
\[<br />
\begin{pmatrix}<br />
(2,2)&(5,0)\\<br />
(0,5)&(4,4)<br />
\end{pmatrix}<br />
\]<br />
<br />
The utilities represent 'years in prison' and over the 3 matches that each team will play (against every other team) the goal is to reduce the <b>total</b> amount of time spent in prison.<br />
<br />
This is always good fun and my final year students were no exception (more so that <a class="g-profile" href="https://plus.google.com/103137876942082024919" target="_blank">+Paul Harper</a> leant me a sidekick who was allowed to use a Nerf gun when the opposite team defected - <a href="http://goo.gl/5J7cGE" target="_blank">more about that here</a>):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-id3VjiYDlVU/Uwpkm6LW9zI/AAAAAAABCNQ/s6pooseE_xY/s1600/IMG_20140221_154338.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-id3VjiYDlVU/Uwpkm6LW9zI/AAAAAAABCNQ/s6pooseE_xY/s1600/IMG_20140221_154338.jpg" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-Ev05LIBKwmA/Uwpkm1lLKoI/AAAAAAABCNQ/80bUuT8BnI4/s1600/IMG_20140221_153324.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-Ev05LIBKwmA/Uwpkm1lLKoI/AAAAAAABCNQ/80bUuT8BnI4/s1600/IMG_20140221_153324.jpg" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-NNUR8c7iz9w/Uwpkm-RGGMI/AAAAAAABCNQ/sokS-bCOeDk/s1600/IMG_20140221_152015.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-NNUR8c7iz9w/Uwpkm-RGGMI/AAAAAAABCNQ/sokS-bCOeDk/s1600/IMG_20140221_152015.jpg" height="240" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-LYfD4CNdQjE/Uwpkm4usd0I/AAAAAAABCNQ/0VaA_owRqK4/s1600/IMG_20140221_152754.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-LYfD4CNdQjE/Uwpkm4usd0I/AAAAAAABCNQ/0VaA_owRqK4/s1600/IMG_20140221_152754.jpg" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-nTA0fMmURnU/Uwpkm61xHEI/AAAAAAABCNQ/mmvFrvOxQIU/s1600/IMG_20140221_154617-MOTION.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-nTA0fMmURnU/Uwpkm61xHEI/AAAAAAABCNQ/mmvFrvOxQIU/s1600/IMG_20140221_154617-MOTION.gif" height="239" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
In this particular instance we played 8 rounds per 'duel' and it was very helpful to have <a class="g-profile" href="https://plus.google.com/104243854554833157722" target="_blank">+Jason Young</a> assist me with writing down the scores etc...</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Here's the overall scores which show that the team named: 'Cymru' acquired the least total score (and won a box of chocolate):</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-vcZhpPZGF2s/Uwpl3UkEKmI/AAAAAAABCNg/DmtN2qB5uGs/s1600/IMG_20140221_155457.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-vcZhpPZGF2s/Uwpl3UkEKmI/AAAAAAABCNg/DmtN2qB5uGs/s1600/IMG_20140221_155457.jpg" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
Here's all the 'duels':<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-gMtGPZVK18c/UwpmEHMdxzI/AAAAAAABCNo/1vgflK6KWQs/s1600/IMG_20140221_155451.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-gMtGPZVK18c/UwpmEHMdxzI/AAAAAAABCNo/1vgflK6KWQs/s1600/IMG_20140221_155451.jpg" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<b>The 3rd game was the most interesting (from an educators point of view).</b></div>
<div class="separator" style="clear: both; text-align: left;">
<b><br /></b></div>
<div class="separator" style="clear: both; text-align: left;">
Team 'Roy' at the very beginning of the duel stated:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<i>'We will cooperate until you defect, once you defect we will only defect'</i></div>
<div class="separator" style="clear: both; text-align: center;">
<i><br /></i></div>
<div class="separator" style="clear: both; text-align: left;">
Both teams cooperated fully and in the final round Roy defected (whilst their opponent continued to cooperate). This all happened with no prompting from myself which is great because team Roy in effect discovered how strategies had to be defined in repeated games which must take in to account the entire history of the game.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<strike>What's also quite cool is that they described 'Tit for Tat' the strategy that won <a href="http://en.wikipedia.org/wiki/Tit_for_tat" target="_blank">Axelrod's tournaments</a>.</strike></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<a class="g-profile" href="https://plus.google.com/105928933060914545488" target="_blank">+Michael Trick</a> pointed out that that is completely incorrect and that Roy <b>almost</b> described 'Tit for Tat', they in fact played what's called 'grudger' (which did not win Axelrod's tournaments).</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
What happened in the last two rounds of the game was also pretty interesting as some coalitions formed to try and share the box of chocolates. Some of my students showed some great game theoretical reasoning: 'we will give you all but enough chocolates for each one of us on the team'...</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
In class <a href="http://goo.gl/hVv0kG" target="_blank">we will consider repeated games</a> in a more rigorous setting and before playing infinitely repeated games also play a modified version of this tournament (I'll blog about that when it happens).</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
(Note that the name of the winning team: Cymru is Welsh for Wales and I think was partly motivated by the fact that I was wearing my French rugby shirt before the Wales France game that evening. <a href="http://goo.gl/AbQEyx" target="_blank">Wales played extremely well and thrashed France.</a>)</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-28686422053127709582014-02-21T03:58:00.003-08:002014-02-21T03:58:59.383-08:00Best responses to mixed strategies in class<script src="https://sagecell.sagemath.org/static/jquery.min.js"></script>
<script src="https://sagecell.sagemath.org/static/embedded_sagecell.js"></script>
<script>sagecell.makeSagecell({"inputLocation": ".sage"});</script>
On Monday my Game Theory class and I took a look the connection between extensive form games and normal form games (leading to subgame perfection) which correspond to these two chapters of my course: <a href="http://goo.gl/ZpVg8g" target="_blank">C7</a> and <a href="http://goo.gl/IIzf0I" target="_blank">C8</a> but before starting that we took another look at best responses to mixed strategies (<a href="http://www.vincent-knight.com/teaching/gametheory/mixedstrategyne/" target="_blank">this Chapter of my course</a>).<br />
<br />
We have been using this game quite a bit in class:<br />
<br />
\[\begin{pmatrix}<br />
(2,-2) & (-2,2)\\<br />
(-1,1) & (1,-1)<br />
\end{pmatrix}\]<br />
<br />
We played it before and I blogged about it <a href="http://goo.gl/vc0BYz" target="_blank">here</a>. This is a slight modification of the matching pennies game where the 1st strategy corresponds to playing Heads (\(H\)) and the second to playing Tails (\(T\))<br />
<br />
If player 1 (the row player) is playing a mixed strategy \(\sigma_1=(x, 1-x)\) then the utility to player 2 when playing player 2 plays $H$ (the first column) can be written as:<br />
<br />
\[<br />
u_2(\sigma_1,H)=-2x+1-x=1-3x<br />
\]<br />
<br />
and when player 2 plays $T$:<br />
<br />
\[<br />
u_2(\sigma_1,T)=2x-1+x=3x-1<br />
\]<br />
<br />
We can plot these two utilities here (using <a class="g-profile" href="https://plus.google.com/113421169347512599264" target="_blank">+Sage Mathematical Software System</a>):<br />
<br />
<div class="sage">
<script type="text/x-sage">
u2H(x) = 1 - 3 * x
u2T(x) = -u2H(x)
p = plot(u2H,x,0,1, legend_label='$u_2((x,1-x),H)$')
p += plot(u2T,x,0,1, legend_label='$u_2((x,1-x),T)$', color='red')
p
</script>
</div>
It is immediate to note that when \(x < 1/3\) player 2 should play $T$. In fact we can write down player 2's best response \(s_2^*\) to any \(\sigma_1\):<br />
<br />
\[<br />
s_2^*=\begin{cases}<br />
H,&x < 1/3\\<br />
T,&x > 1/3\\<br />
\text{indifferent},&<br />
\end{cases}<br />
\]<br />
<br />
Using all this I played the following game in class:<br />
<br />
<br />
<ul>
<li>I handed out sheets asking students to play against 3 separate mixed strategies \(\sigma_1\in\{(.2,.8),(.9,.1),(1/3,2/3)\}\). I will refer to these 3 rounds as R1, R2 and R3;</li>
<li>Students (acting as player 2) filled in their strategies;</li>
<li>I then used the following interact to sample mixed strategies according to \(\sigma_1\):</li>
</ul>
<div>
<br /></div>
<div class="sage">
<script type="text/x-sage">
x = 1/3
data = [0,0]
history = []
@interact
def play_mixed(
button=selector(["Sample with $x=%.02f$" % x],label='',buttons=True)):
if random() < x:
data[0] += 1
history.append('H')
else:
data[1] += 1
history.append('T')
print history
sigma = [(k/sum(data)).n(digits=2) for k in data]
print sigma
p = bar_chart(sigma)
p.ymin(0)
p.ymax(1)
p.show()
</script>
</div>
I changed the value of \(x\) as required.<br />
<br />
Here are the three row strategies that were sampled:<br />
<br />
<br />
<ul>
<li>R1: TTTTTH </li>
<li>R2: HHHTHH </li>
<li>R3: TTHTTT </li>
</ul>
<br />
<br />
This is obviously not giving the exact proportions dictated by the mixed strategy \(\sigma_1\) but that's also kind of the point.
By round, here are the results.<br />
<br />
<b>R1</b><br />
<b><br /></b>
Here's a plot of the mixed strategy that was played by the entire class during round 1:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-Xx3rOi2mRIU/Uwcnhl-0qcI/AAAAAAABBZI/1UNxSAsQrPA/s1600/R1strategiesvbestresponse.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-Xx3rOi2mRIU/Uwcnhl-0qcI/AAAAAAABBZI/1UNxSAsQrPA/s1600/R1strategiesvbestresponse.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
This corresponds to \(\sigma_2=(.70,.30)\), so most students seemed willing to 'trust the theory' that one should play $H$ against this mixed strategy.<br />
<br />
4 students scored the highest score (\(7\)) and here's the strategy they all played: \(HHHHHT\), in essence they got lucky and maxed out what they could have had. If they had played the <b>theoretical</b> best response (to only play $H$) they would have scored: 3.<br />
<br />
The expected value of playing the <b>theoretical</b> best response (always pick \(H\) against this mixed strategy is: \(6(1-3\times.2)=2.4\) (recall that \(\sigma_1=(.2,.8)\) for this round).<br />
<br />
The mean score for this round was 1.4 and here's a distribution of the scores:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-3ZDii8q1l-A/Uwc9Vv5iMPI/AAAAAAABBaU/AG3whc15gw8/s1600/R1score.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-3ZDii8q1l-A/Uwc9Vv5iMPI/AAAAAAABBaU/AG3whc15gw8/s1600/R1score.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />
47 students who 'won' ie scored a positive score (this is a zero zum game) played \(\sigma_2=(.83,.17)\). 18 'lost' (scored a negative score) playing \(.37,.63\).<br />
<br />
It's nice to see that there was a large amount of students who did in fact score 3.<br />
<br />
<b>R2</b><br />
<b><br /></b>
Here's a plot of the mixed strategy that was played by the entire class during round 2:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-KDTV7ps2eME/UwcqUd7Np3I/AAAAAAABBZU/oxHPsEJPxno/s1600/R2strategiesvbestresponse.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-KDTV7ps2eME/UwcqUd7Np3I/AAAAAAABBZU/oxHPsEJPxno/s1600/R2strategiesvbestresponse.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
This corresponds to \(\sigma_2=(.12,.88)\), which is again pretty close to the theoretical best response.<br />
<br />
2 students scored the highest score: 11. They once again lucked out and played the perfect response: \(TTTHTT\). If they had played the theoretical best response they would have scored 9.<br />
<br />
The expected value of playing the <b>theoretical</b> best response (always pick \(T\) against this mixed strategy is: \(6(3\times.9-1)=10.2\) (recall that \(\sigma_1=(.9,.1)\) for this round).<br />
<br />
The mean score for this round was 6.9 and here's a distribution of the scores:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-TRbjcsfITKc/Uwc9arrEL9I/AAAAAAABBac/TCqe1hney0w/s1600/R2score.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-TRbjcsfITKc/Uwc9arrEL9I/AAAAAAABBac/TCqe1hney0w/s1600/R2score.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
60 students 'won' ie scored a positive score (this is a zero zum game) playing \(\sigma_2=(.07,.93)\). 5 'lost' (scored a negative score) playing \(.77,.23\).<br />
<div>
<br /></div>
<b>R3</b><br />
<b><br /></b>
The third round had the students playing against a mixed strategy for which they should have been indifferent. Here's how they played:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-ix7ly8qZWdo/UwcqzmyAsvI/AAAAAAABBZc/07um9Sg4ShE/s1600/R3strategiesvbestresponse.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-ix7ly8qZWdo/UwcqzmyAsvI/AAAAAAABBZc/07um9Sg4ShE/s1600/R3strategiesvbestresponse.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
This corresponded to \(\sigma_2=(0.62,.38)\).</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
There were 10 winners for this game and they scored 10 (quite a few strategy profile gave this score so I won't list them but they mainly took advantage of the fact that mostly $T$ was sampled). (The theoretical utility is in fact 0 as you can see with one of the plots above).</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
The mean score for this round was was .4 (which is quite close to the theoretical value of 0). Here's the distribution of the scores:</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-2mTCwcuMPJs/Uwc9fCaZf7I/AAAAAAABBak/DXxX83LV1uE/s1600/R3score.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-2mTCwcuMPJs/Uwc9fCaZf7I/AAAAAAABBak/DXxX83LV1uE/s1600/R3score.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
28 scored positively playing \(\sigma_2=(.64,.36)\) and 37 scored negatively playing \(\sigma_2=(.77,.23)\).<br />
<br />
<b>What's nice to see here is that this 3rd round is a bit more random, with an almost (stretching the definition of the word almost) equal distribution between the number of students who won and lost.</b><br />
<br />
Here's a distribution of the overall scores:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-qGjU4rbsMWU/Uwc9mt4gCjI/AAAAAAABBas/Skcc0MJVGrU/s1600/cumulativescore.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-qGjU4rbsMWU/Uwc9mt4gCjI/AAAAAAABBas/Skcc0MJVGrU/s1600/cumulativescore.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
The overall winner of the game (who scored the most over the 3 rounds) was Becky who played:<br />
<br />
<ul>
<li>R1: \(TTHHHH\)</li>
<li>R2: \(TTTTTT\)</li>
<li>R3: \(HHTHTH\)</li>
</ul>
<br />
For a cumulative score of: 21<br />
<br />
<b>This was good fun to analyse and was hopefully useful to my students to see what is meant by best responses to mixed strategies. It was particularly cool to see an 'indifferent' (again stretching the definition of the word indifferent) response to the third round.</b><br />
<b><br /></b>
(Like with everything for this course you can find the data, analysis scripts and everything else at this <a href="https://github.com/drvinceknight/Year_3_game_theory_course" target="_blank">github repo</a>)<br />
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-88818169469054396612014-02-18T04:46:00.000-08:002014-02-18T04:49:08.594-08:00My students write about their first Python conference<span style="font-family: inherit;"><a href="http://drvinceknight.blogspot.co.uk/2014/02/my-first-pycon.html" target="_blank">Last week</a> I wrote about my impressions from my first Open Source Software conference (OSS): https://djangoweekend.org/</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">It was an awesome conference but the highlight for me was seeing 3 of my students take full advantage of the event. <b>I asked Matt, Alex and James to write a bit of a guest post for this blog about their experiences:</b></span><br />
<span style="font-family: inherit;"><b><br /></b></span>
--------------------------------<br />
<span style="font-family: inherit;"><b><br /></b></span>
<span style="font-family: inherit;"><b>Here's what Matt had to say:</b></span><br />
<span style="font-family: inherit;"><br /></span>
<i>"Having never been to a conference like this before, and with only a few months of coding experience under my belt, I had no idea what to expect from Django Weekend Cardiff. Despite this I had an incredible weekend. Everyone that I met and talked to was friendly and more than willing to answer my questions. </i><br />
<i><br /></i>
<i>While some of the talks went a little over my head, the clinics were very helpful in getting me started with Django. I even felt confident enough to give a lightning talk, that gave me the chance to voice my opinion on computing with regards to education, and how it had helped me over the few months I was leaning it as part of my undergraduate course for maths.</i><br />
<i><br /></i>
<br />
<i>Overall I had a great time, and will definitely be keeping an eye out for Django Weekend Cardiff 2015."</i><br />
<i><br /></i>
Matt's lightning talk was recorded so as soon as it's online I will be post about it. He did an awesome job.<br />
<br />
--------------------------------<br />
<br />
<b>Here's what <a class="g-profile" href="https://plus.google.com/112667035463015419109" target="_blank">+Alex Carney</a> had to say:</b><br />
<b><br /></b>
<i>"I first became aware of the open source scene when I was in Year 7 and my dad installed Ubuntu 7.10 on my </i><i>ancient laptop in a bid to keep it usable. I slowly became more and more fascinated on what software I was able to download </i><i>for free and have a play with, from creating animations with Blender to messing around in GIMP and to hear </i><i>him say that it was made by normal people such as ourselves I was blown away thinking how on Earth could people like my dad </i><i>and myself create such wonders?</i><br />
<i><br /></i>
<i>Well needless to say it reignited my desire to learn programming, I had dabbled with Pascal and BASIC beforehand but </i><i>I couldn't get much further than a series of print statements and lost interest. But then to discover </i><i>Python, a language with syntax that was actually readable to someone just starting secondary school was amazing, </i><i>slowly I was able to teach myself parts of it in short bursts over the years, before dropping it when I was </i><i>in Year 11, to learn C++ mostly forgetting about Python.</i><br />
<i><br /></i>
<i>Fast forward to September 2013, when I started my Maths degree at Cardiff Uni, and I finding out that I would be </i><i>taught Python as part of the course was like being reunited with an old friend. But this time there was a major </i><i>difference I was actually <b>using</b> Python. Back when I was teaching myself I never had any concrete goals </i><i>or deadlines, I would follow one example before swiftly moving on to the next without stopping to </i><i>apply what I had learnt. So naturally it was hard to maintain focus and I never produced anything worthwhile. </i><br />
<i><br /></i>
<i>However being set tasks to complete was great as I was finally applying my knowledge I had gained over the years and </i><i>was able to appreciate how useful being able to program is, once you start thinking like a programmer the only </i><i>limit is your imagination - Oh! and of course how powerful your computer is...</i><br />
<i><br /></i>
<i>I can't thank Vince and the School of Mathematics at Cardiff enough for sponsoring me to go to the conference because </i><i>it made me realise a lot of things. Firstly is that there really is a thriving <b>welcoming</b> community </i><i>on the open source scene. I was always vaguely aware that it existed as I trawled through forums and mailing lists </i><i>looking for solutions to problems I was having, but something always stopped me from joining in. I was thinking that even though </i><i>it was open there was some mystical entry barrier that you had to pass before you would be accepted.</i><br />
<i><br /></i>
<i>However by going to the conference I was shown the complete opposite. Nobody so much batted an eyelid when they saw me, </i><i>some student only just able to scratch the surface of Python's power and knowing absolutely nothing about Django. Moreover </i><i>they <b>wanted</b> to speak to me, they wanted to hear about it from a beginner's perspective, they wanted to know </i><i>what it was like learning Django for the first time, what could they do to make it easier for me to learn? </i><i>While having a chat with one of the core Django developers I pointed out that I didn't find certain steps in a </i><i>tutorial that clear and afterwards he went away and amended the tutorial clearing up the confusion that I had!</i><br />
<i><br /></i>
<i>It was incredibly interesting to hear how other people have used Python in their work and I was blown away </i><i>at the power of not only the programming language itself but the community as well. An example from a particular </i><i>talk was the Astronomy community, how Python was able to help the community create a common standard for sharing data </i><i>and how all the tools developed by individuals went on to benefit the community as a whole. Leaving </i><i>researchers able to concentrate more on the science than the technical difficulties and headaches of having to </i><i>deal with fragmented standards and datasets.</i><br />
<i><br /></i>
<i>I want to finish by saying how truly inspired attending the conference made me and I not only want to thank </i><i>Vince and the School of Mathematics for giving me the opportunity, but to thank Daniele Procida for making the </i><i>conference a reality in the first place. I will definitely want to attend next year's and I'm even thinking of going to </i><i>PyConUK in September. I am yet to contribute to an open source project but I'm hoping that's an issue I can fix sooner </i><i>rather than later."</i><br />
<span style="font-family: inherit;"><br /></span>
Alex was one of the students in the class with the most starting knowledge; in fact he helped me win a bet with <a class="g-profile" href="https://plus.google.com/104243854554833157722" target="_blank">+Jason Young</a> (that I would be able to get a student to use Vim before the end of the year: Alex used Vim from the start...). It's really nice to read that he found the whole conference interesting and more importantly inspiring.<br />
<br />
--------------------------------<br />
<br />
<b>The final post is from <a class="g-profile" href="https://plus.google.com/103944008095354003273" target="_blank">+James Campbell</a></b> but he has his <a href="http://www.jamescampbell.org.uk/?page_id=390" target="_blank">own blog</a> that I'd really recommend you taking a look at (James is also a rugby referee so he blogs about that as well). Here's the post he wrote about the conference: <a href="http://www.jamescampbell.org.uk/?p=417">http://www.jamescampbell.org.uk/?p=417</a><br />
<br />
If it's too much effort to click over to there here's a bit I stole:<br />
<br />
<i>"Today they were working on fixing bugs and reviewing code for the upcoming Django 1.7 release. However, despite how busy they were, whenever I needed a hand someone was happy to help. At one point I had Django core developers discussing the best way to solve one of my problems. These guys are some of the best in the world at what they do, yet they still found time to help a complete newcomer, and I’m really grateful to all those who did so."</i>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-38632181621806822922014-02-11T07:01:00.002-08:002014-02-11T10:50:59.573-08:00A Rock, Paper, Scissors, Lizard, Spock Tournament in classI just taught mixed strategy Nash equilibria to my students (http://goo.gl/evmerJ and http://goo.gl/wMxAoY).<br />
<br />
I thought I could use this as an excuse to play a Rock, Paper, Scissors tournament and then someone suggested I play a Rock, Paper, Scissors, Lizard, Spock tournament:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/iapcKVn7DdY?feature=player_embedded' frameborder='0'></iframe></div>
<br />
<br />
Most students had seen the game but to help us along with the rules I put this up on the board (<a href="http://en.wikipedia.org/wiki/Rock-paper-scissors-lizard-Spock" target="_blank">source: wikipedia</a>):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Rock_Paper_Scissors_Lizard_Spock_en.svg/220px-Rock_Paper_Scissors_Lizard_Spock_en.svg.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Rock_Paper_Scissors_Lizard_Spock_en.svg/220px-Rock_Paper_Scissors_Lizard_Spock_en.svg.png" /></a></div>
<br />
<br />
We then proceeded to play a 16 player knockout tournament that <a class="g-profile" href="https://plus.google.com/104243854554833157722" target="_blank">+Jason Young</a> kindly helped run. Student were matched up and played best of 3 rounds with sudden death.<br />
<br />
Here are the results (<a href="http://2.bp.blogspot.com/-e7sdUOMhuic/Uvo3w46ecnI/AAAAAAAA_vU/XTOa84HEk9M/s1600/bracket.png" target="_blank">open the image in it's own tab to view it in detail</a>):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<img border="0" src="http://2.bp.blogspot.com/-e7sdUOMhuic/Uvo3w46ecnI/AAAAAAAA_vU/XTOa84HEk9M/s1600/bracket.png" height="250" width="400" /><span id="goog_733267955"></span><span id="goog_733267956"></span><a href="https://www.blogger.com/"></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Here's a plot of the strategies played during the 1st, 2nd and 3rd rounds:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-UCjuv6OklyI/Uvo6P4vyZGI/AAAAAAAA_wQ/BPWiVqn0UPY/s1600/round1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-UCjuv6OklyI/Uvo6P4vyZGI/AAAAAAAA_wQ/BPWiVqn0UPY/s1600/round1.png" height="240" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-2XbxstgVRlE/Uvo6P3ELg9I/AAAAAAAA_wU/2T30OAPEvkY/s1600/round2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-2XbxstgVRlE/Uvo6P3ELg9I/AAAAAAAA_wU/2T30OAPEvkY/s1600/round2.png" height="240" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-BMD3Ie4yoXs/Uvo6P8m5u-I/AAAAAAAA_wc/rFpa-xqDCVU/s1600/round3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-BMD3Ie4yoXs/Uvo6P8m5u-I/AAAAAAAA_wc/rFpa-xqDCVU/s1600/round3.png" height="240" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
The overall strategy profile played is here:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-8h_kH-CzRBI/Uvo6VUUQZII/AAAAAAAA_w0/Qro-dyv9GnM/s1600/allstrategies.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-8h_kH-CzRBI/Uvo6VUUQZII/AAAAAAAA_w0/Qro-dyv9GnM/s1600/allstrategies.png" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />
We're not quite playing at Nash equilibrium (which would imply a uniformly distributed choice of strategies) but it's not too far off.<br />
<br />
Here are the strategy profiles of all matches that won a game:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-kUUHRJcMSG0/Uvo6VRP-HFI/AAAAAAAA_ww/Ang9DJYwCbQ/s1600/winningstrategies.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-kUUHRJcMSG0/Uvo6VRP-HFI/AAAAAAAA_ww/Ang9DJYwCbQ/s1600/winningstrategies.png" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Thus it looks like a response to these winning strategies would be to play strategies that beat Spock, Rock and/or Lizard. Paper would seem to be an ok bet. </div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
Here are the losing strategies:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-6RrD1jwDk0Y/Uvo6VXloOHI/AAAAAAAA_w4/s-7KMd484aE/s1600/losingstrategies.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-6RrD1jwDk0Y/Uvo6VXloOHI/AAAAAAAA_w4/s-7KMd484aE/s1600/losingstrategies.png" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
It looks like Scissors was being played a bit too much and losing to Spock and Rock.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
This was good fun and hopefully help the students understand what a mixed strategy is.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<a href="https://gist.github.com/drvinceknight/8936399" target="_blank">If it's of interest here is the dirty Python script I wrote to analyse all this.</a></div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-24291333746238299212014-02-09T13:36:00.005-08:002014-02-09T13:51:10.511-08:00My students and my first PyConA couple of months ago an email somehow found it's way in to my inbox mentioning a new user group that was setting up in Cardiff. This was from some guy called <a href="https://twitter.com/evildmp" target="_blank">Daniele Procida</a>. As a Python coder really enthusiastic to be part of the Open Source Software (OSS) community I thought this would be awesome so I've been along to the monthly meetings where all things Python and Django are discussed.<br />
<br />
However many months later I got to attend my first PyCon (in fact a DjangoCon): <a href="https://djangoweekend.org/">https://djangoweekend.org/</a><br />
<br />
Here's the programme that I carried around in my back pocket:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-w96Fn4ZSObc/UvfbmQ1DT0I/AAAAAAAA_mY/LH-pRLToalM/s1600/IMG_20140209_194603.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-w96Fn4ZSObc/UvfbmQ1DT0I/AAAAAAAA_mY/LH-pRLToalM/s1600/IMG_20140209_194603.jpg" height="320" width="240" /></a></div>
<br />
<br />
Professor Tim Phillips, the head of the School of Mathematics kindly agreed to sponsor 3 tickets for students on my Computing for Mathematics course. I gave 3 tickets to students as a reward for their individual coursework (James wrote about Markov chains and Snakes and Ladders, Alex about Fractals and Matt about prime numbers).<br />
<br />
<a class="g-profile" href="https://plus.google.com/104243854554833157722" target="_blank">+Jason Young</a> who has been my research undergraduate student for a couple of years now (and is a very able coder) attended and <a class="g-profile" href="https://plus.google.com/101590053538744950069" target="_blank">+Izabela Komenda</a> (a post-doc) also presented some of her PhD work.<br />
<br />
Here's a picture of my Cardiff students, Daniele and I:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-3Sj-t-ndbpo/Uvf1gX_2yaI/AAAAAAAA_nw/0tKRPmAfhao/s1600/IMG_20140208_154243.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-3Sj-t-ndbpo/Uvf1gX_2yaI/AAAAAAAA_nw/0tKRPmAfhao/s1600/IMG_20140208_154243.jpg" height="240" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />
It was great that so many sponsors contributed to the conference (<a href="https://djangoweekend.org/sponsors/" target="_blank">full list here</a>) and also that <a class="g-profile" href="https://plus.google.com/105597832656358813737" target="_blank">+Cardiff University</a> supported the event wholeheartedly, <a href="https://twitter.com/profmobisoc" target="_blank">Roger Whitaker</a> (the dean of research for the physical sciences) even opened the scientific talks on Friday.<br />
<br />
Frankly:<br />
<br />
<b>It was the best conference I've ever been to.</b><br />
<b><br /></b>
<br />
The atmosphere cultivated by the OSS community is really amazing. Everyone is really encouraging, understanding and just plain ol' nice.<br />
<br />
From the scientific talks on the Friday where usages for Python in Science were discussed to witnessing what a 'code sprint' was on the Sunday: everyone was just exceptionally <b>nice.</b><br />
<b><br /></b>
<b>I learnt Django over christmas and the help people were willing to give (not once making my mistakes more than they were) was really cool.</b><br />
<b><br /></b>
For example this morning I sat down with <a href="https://twitter.com/bmispelon" target="_blank">Baptiste</a>, one of the core Django developers and he really kindly answered all the (noobish) questions I had (before leaving today he actually gave me his card and told me to get in touch if I had any further problems with a particular thing).<br />
<br />
That is just one example of the awesome atmosphere that was cultivated during the conference. The event brilliantly mixed advanced programming for one of the most popular web frameworks with accessible topics for every attendee. I think that this is something that is kind of inherent to the OSS community, you are encouraged to put yourself out there and potentially make mistakes.<br />
<br />
<b>For this reason alone I'm extremely glad that the 3 undergraduates got to attend the event. </b><br />
<br />
Fear of failure and mistakes is something that sometimes really holds students back. As educators it's very important for us to make sure students learn to embrace mistakes.<br />
<br />
During one of the talks on Saturday a particular particularity of Django was being discussed and I thought to myself:<br />
<br />
<i>I wonder if my students will be put off by "how much they don't understand" and perhaps this will end up being a negative experience for them...</i><br />
<i><br /></i>
I could not have been more wrong, <b>their attitudes were perfect.</b> They realised that they were very much at the beginning of the road (some of them had not coded before October) and just took advantage of everything around them.<br />
<br />
James gave a talk on the Friday which was great and Matt gave a lightning talk (less than 5mins):<br />
<!--5mins--><!--5mins--><!--5mins--><!--5mins--><!--5mins--><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-VLduIXFHlw8/UvfkTo4oAzI/AAAAAAAA_nY/KF3A_BK2R7I/s1600/IMG_20140207_121525.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-VLduIXFHlw8/UvfkTo4oAzI/AAAAAAAA_nY/KF3A_BK2R7I/s1600/IMG_20140207_121525.jpg" height="240" width="320" /></a></div>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-Hiekdai1AV8/UvfkImjAuwI/AAAAAAAA_nM/qwRhXJiSoA8/s1600/IMG_20140208_175201.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-Hiekdai1AV8/UvfkImjAuwI/AAAAAAAA_nM/qwRhXJiSoA8/s1600/IMG_20140208_175201.jpg" height="240" width="320" /></a></div>
<br />
<br />
They all spoke to the experts around them constantly and by Sunday were themselves writing Django apps. It was great to have <a class="g-profile" href="https://plus.google.com/109555173433940635279" target="_blank">+Robert Dragan</a> of <a href="http://www.learnium.net/" target="_blank">learnium</a> help some of them debug their code on the Sunday.<br />
<br />
In fact towards the end of Sunday James even had Daniele (a core Django developer) and Charlie (a super-duper really helpful and nice Django developer/person) helping him work on a site:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-IsK02RKvE0w/Uvfd21HpKAI/AAAAAAAA_mw/DDdQv1E0Rws/s1600/IMG_20140209_170922.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-IsK02RKvE0w/Uvfd21HpKAI/AAAAAAAA_mw/DDdQv1E0Rws/s1600/IMG_20140209_170922.jpg" height="240" width="320" /></a></div>
<br />
I won't write much more about the whole event but I'll just repeat something that Matt said during his lightning talk.<br />
<br />
He started by saying that he was a bit dismayed when at the beginning of his degree he was told that he was going to <b>have</b> to learn how to code (my course is brand new), he then talked about how he thought <a class="g-profile" href="https://plus.google.com/113421169347512599264" target="_blank">+Sage Mathematical Software System</a> helped him gain a better understanding of the prime number theorem but it was what he said last that was really <b>awesome</b> (a lot of other attendees commented on it):<br />
<br />
<div style="text-align: center;">
<i>"Why did I have to wait until coming to University to learn to code?"</i></div>
<div style="text-align: center;">
<i><br /></i>
<div style="text-align: left;">
(All the talks on Saturday were recorded so I really look forward to sharing his talk, it was very well delivered.)</div>
<i><br /></i></div>
<div style="text-align: left;">
This whole event was a really great experience for me but more importantly my students.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<b>The conference will be running again next here which is awesome for my future students.</b> Next time Daniele, (who is one of the most impressive human beings I've ever met) will have (at least) me to help organise the it.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
I've already signed up for my next PyCon (<a href="http://pyconuk.org/">http://pyconuk.org/</a>) and more importantly I've asked myself:</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: center;">
<i>"Why did I have to wait till now to attend an OSS conference?"</i></div>
<!--5mins-->Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-66790862273889240172014-02-03T11:00:00.002-08:002014-02-25T13:34:14.512-08:00An attempt at Golden Balls in classToday I introduced my students to the concepts of Dominance and Best responses in my new game theory class (<a href="http://goo.gl/MMLsGD" target="_blank">Chapters 3</a> and <a href="http://goo.gl/39KjVw" target="_blank">4</a> of my class notes).<br />
<br />
To re-affirm ideas we saw previously (normal form representation of games) and also talk about Dominance I tried to set up a kind of <a href="http://en.wikipedia.org/wiki/Golden_Balls" target="_blank">Golden Balls game</a>.<br />
<br />
Golden Balls is a game show that aired in the UK a while ago and I've never actually seen an episode but the premise is that two players cooperate during the game to come up with a total sum of money that must then be 'shared' using a Prisoner's Dilemma.<br />
<br />
If you haven't seen this video before, it's a great example of the end game of the show:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/p3Uos2fzIJ0?feature=player_embedded' frameborder='0'></iframe></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
I always show this video to students when talking about Game Theory as I reckon it's pretty awesome.</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<b>Here's what I did in class:</b></div>
<div class="separator" style="clear: both; text-align: left;">
<b><br /></b></div>
<div class="separator" style="clear: both; text-align: left;">
I got two students to play the game: A and S. They were to compete against me (as the row player, I was the column player) in the following 5 normal form games (their utility corresponded to the number of chocolates I would owe them):</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
1. Just a plain old matching pennies game (we played this in class last week and I blogged about it <a href="http://drvinceknight.blogspot.co.uk/2014/01/matching-pennies-in-class.html" target="_blank">here</a>):</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
$$\begin{pmatrix}<br />
(1,-1)&(-1,1)\\<br />
(-1,1)&(1,1)<br />
\end{pmatrix}$$<br />
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
2. A modification of this game with a weakly dominated strategy:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
$$\begin{pmatrix}<br />
(1,-1)&(-1,1)\\<br />
(1,-1)&(1,-1)<br />
\end{pmatrix}$$<br />
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
A and S were both quick to realise that they should play the second row strategy.</div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
3. A modification of the matching pennies game:</div>
<div class="separator" style="clear: both;">
<br /></div>
$$\begin{pmatrix}<br />
(2,-2)&(-1,1)\\<br />
(-1,1)&(2,-2)<br />
\end{pmatrix}$$<br />
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
4. A game with a strategy at which they would definitely win something:</div>
<div class="separator" style="clear: both;">
<br /></div>
$$\begin{pmatrix}<br />
(2,-2)&(1,-1)\\<br />
(-1,1)&(2,-2)<br />
\end{pmatrix}$$<br />
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
5. The same game as 4, again (when I play this next year I'll change this game slightly).</div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
<b>This ended up with A and S having about 6 chocolates between them. I then split the team up and told them to play:</b></div>
<div class="separator" style="clear: both;">
<br /></div>
$$\begin{pmatrix}<br />
(2,2)&(0,3)\\<br />
(3,0)&(1,1)<br />
\end{pmatrix}$$<br />
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
If they cooperated (choosing the first strategy) I would double the 6 chocolates and they would have 12 chocolates each. If 1 defected, the defector would have 18 chocolates and the other none. If they both defected they would just have 6 chocolates each.</div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
I asked if they'd like to talk to each other. S, tried but A confidently said: 'no need, I know what you are going to do'. S cooperated and A defected.</div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
There were 1 or 2 'oooos' that were swiftly ended when A proceeded to immediately share his chocolates with A. I in fact ended up just giving the whole box of chocolates I bought:</div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-xRSyKgmiZlw/Uu-tHG0dtkI/AAAAAAAA-tk/gPn9o63dVag/s1600/2014+-+1" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-xRSyKgmiZlw/Uu-tHG0dtkI/AAAAAAAA-tk/gPn9o63dVag/s1600/2014+-+1" height="320" width="240" /></a></div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
<b>After this we moved on to talk about best response strategies.</b> </div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both;">
I asked for a volunteer to player tic-tac-doe with me and we used this as a discussion about best responses:</div>
<div class="separator" style="clear: both;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<i>'Right, now that she has played there, where should I play?'</i></div>
<div class="separator" style="clear: both; text-align: center;">
<i><br /></i></div>
<div class="separator" style="clear: both; text-align: left;">
I put up a picture of <a class="g-profile" href="https://plus.google.com/107491426046453511750" target="_blank">+Randall Munroe</a>'s <a href="http://xkcd.com/832/" target="_blank">tic-tac-toe solution</a>.</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
All in all it was good fun I think and hopefully helped make the class a bit more 'alive'. I have a (what I think is a) cool idea about a game I'll try and play with my students next week when talking about <a href="http://goo.gl/wMxAoY" target="_blank">mixed strategy equilibrium</a>. This could involve a bracket of 16 volunteers...</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
If you liked the video above, take a look at this one which is pretty awesome too:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div style="text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/S0qjK3TWZE8?feature=player_embedded' frameborder='0'></iframe></div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-67490956832220615602014-01-28T03:54:00.003-08:002014-02-03T09:36:25.282-08:00Matching pennies in classYesterday I took the first class of my new module on Game Theory. I've been very excited about this as I think Game Theory is a really fun subject to learn (and teach).<br />
<br />
In class we covered the first two chapters of my notes (<a href="http://goo.gl/vuZgRF" target="_blank">Chapter 1: Introduction to Game Theory</a>, <a href="http://www.vincent-knight.com/teaching/gametheory/normalformgames/" target="_blank">Chapter 2: Normal Form Games</a>). Whilst talking about Normal Form Games I showed the students the game called Matching Pennies.<br />
<br />
<i>Two players each show a coin with either 'Heads' or 'Tails' showing. If both coins match then the 1st player (the row player) wins, otherwise the 2nd player (the column player) wins.</i><br />
<i><br /></i>
This can be represented using a 'bi-matrix':<br />
<br />
$$\begin{pmatrix}<br />
(1,-1)&(-1,1)\\<br />
(-1,1)&(1,1)<br />
\end{pmatrix}$$<br />
<br />
Each tuple of that matrix corresponds to a pair of strategies from the set $\{H, T\}$, so if the row player chose $H$ and the column player chose $T$ then they would read the outcome in the <b>first row</b> and <b>second column:</b> $(-1,1)$. The convention used here is that outcomes show the <b>utilities</b> to the first and then the second player. So in this instance the row/first player would get -1 and the column/second player would get 1 (ie the column player wins because the coins where different).<br />
<br />
I asked the students to get in to pairs and record five rounds of the game on some paper (<a href="http://goo.gl/N0sO7f" target="_blank">forms and all other content for the course available at this github repo</a>).<br />
<br />
After that, I modified the game to give this:<br />
<br />
$$\begin{pmatrix}<br />
(2,-2)&(-2,2)\\<br />
(-1,1)&(1,1)<br />
\end{pmatrix}$$<br />
<br />
The row player still wins when the coins match but there is just more to win/lose when $H$ is picked by the row player.<br />
<br />
I got the students to once again record the results.<br />
<br />
Last night I got home and instead of speaking to my wife I went through and entered all the data.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-WG7scjjcwlY/UueT0Wm0OiI/AAAAAAAA-T8/T0GMbcXNz08/s1600/IMG_20140127_182012.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-WG7scjjcwlY/UueT0Wm0OiI/AAAAAAAA-T8/T0GMbcXNz08/s1600/IMG_20140127_182012.jpg" height="240" width="320" /></a></div>
<br />
<b>Here are some of the results.</b><br />
<b><br /></b>
First of all 'basic matching pennies'. Here are the moving averages of all the games played:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-PPPDkSbhKLk/UueULe2Qu6I/AAAAAAAA-UE/uIeZsRgNyEw/s1600/mixedstrategiesgame1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-PPPDkSbhKLk/UueULe2Qu6I/AAAAAAAA-UE/uIeZsRgNyEw/s1600/mixedstrategiesgame1.png" height="300" width="400" /></a></div>
<br />
I'm graphing the probability with which players played $H$. As you can see 'we' got to equilibrium pretty quickly and 'on average' players were randomly swapping between $H$ and $T$.<br />
<br />
Here is a plot of the equivalent mean score to both players:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-XF4NCRKHobw/UueUdWvxc1I/AAAAAAAA-UM/9gKejqUrdjA/s1600/meanscroresgame1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-XF4NCRKHobw/UueUdWvxc1I/AAAAAAAA-UM/9gKejqUrdjA/s1600/meanscroresgame1.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
First of all we see that the plots are reflections in the $x=0$ line of each other. This is because the game we are considering is called a Z<b>ero Sum Game:</b> all the utility doublets sum to 0. Secondly we see that the mean score is coming around to 0. </div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
<b>All of the above is great and more or less exactly what you would expect.</b></div>
<br />
While playing the second game I overheard a couple of students say something like 'Oh this is a bit more complicated: we need to think'. <b>They were completely right!</b><br />
<b><br /></b>
Here are the results. First of all the strategies:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-znwKP4XEKwc/UueVLu3q7cI/AAAAAAAA-Uc/SPDGraW5qMQ/s1600/mixedstrategiesgame2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-znwKP4XEKwc/UueVLu3q7cI/AAAAAAAA-Uc/SPDGraW5qMQ/s1600/mixedstrategiesgame2.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
It seems like students are once again playing with equal probabilities of picking $H$ or $T$. The outcome for the score is again very similar:</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-ufwzJY0vVl4/UueVm8cH9TI/AAAAAAAA-Uk/kZIltH82jqU/s1600/meanscroresgame2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-ufwzJY0vVl4/UueVm8cH9TI/AAAAAAAA-Uk/kZIltH82jqU/s1600/meanscroresgame2.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<br />
<b>Is this what we expect?</b><br />
<b><br /></b>
Not quite.<br />
<br />
Let us assume row players are playing a 'mixed strategy' $\sigma_1=(x,1-x)$ (ie they choose $H$ with probability $x$) and column players are playing $\sigma_2=(y,1-y)$.<br />
<br />
Let us see what the expected utility to the <b>row </b>player is when $\sigma_2=(.5,.5)$ as a function of $x$ (the probability of playing $H$):<br />
<br />
$$u_1((x,1-x),(.5,.5))=.5(2x-(1-x))+.5(-2x+1-x)=0$$<br />
<br />
So in fact what the row player does is irrelevant (with regards to his/her utility) as long as the column player plays $\sigma_2=(.5,.5)$.<br />
<br />
<b>What about the column player?</b><br />
<b><br /></b>
Writing down the utility to the column player when $\sigma_1=(.5,.5)$ as a function of $y$ (the probability of playing $H$):<br />
<br />
$$u_2((.5,.5),(y,1-y))=1/2(-2y+y+2-2y+y-1)=1/2-y$$<br />
<br />
<b>So NOW if $\sigma_1=(.5,.5)$ it looks like the column player has SOME control over his/her utility.</b><br />
<b><br /></b>
Here is a plot of that $u_2$:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-SGPCEsN2IEY/Uui45IVWlPI/AAAAAAAA-Wk/AYAkKfy9qfg/s1600/sage0.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-SGPCEsN2IEY/Uui45IVWlPI/AAAAAAAA-Wk/AYAkKfy9qfg/s1600/sage0.png" height="297" width="400" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
So our plot is that of a decreasing function. <b>Remember </b>$y$ is something that the column player can control. So as the column player wants to increase $u_2$: the best response they should adapt to the row player playing $\sigma_1=(.5,.5)$ is in fact $y^*=0$ because at $y=0$ the utility is at it's highest!</div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
What this implies (for the second game) is that <b>whilst</b> the students were all winning and losing in equal measure (the mean score was around 0). <b>The column player could in fact improve their strategy and take advantage of the fact that the row player was playing $\sigma_1=(.5,.5)$.</b></div>
<div class="separator" style="clear: both; text-align: left;">
<b><br /></b></div>
<div class="separator" style="clear: both; text-align: left;">
The row player can't actually do this (we did the math above and we saw that he/she couldn't really have any effect on his/her utility). What my students and I will see in <a href="http://goo.gl/wMxAoY" target="_blank">Chapter 6</a> of my class is that in fact there is a way to make both players 'unable to improve their outcomes'. When we get there it will also shed light on the dashed lines in some of the plots of this blog post.</div>
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-674584740645102252014-01-24T09:38:00.001-08:002014-01-24T13:09:23.948-08:00What happens when I ask students if they have seen 'A Beautiful Mind'For the past 4~5 years now I've been lucky enough to tag along with <a class="g-profile" href="https://plus.google.com/103137876942082024919" target="_blank">+Paul Harper</a> when he does outreach in high schools. I've developed my own little 'roadshow' that introduces students to Game Theory.<br />
<br />
On Wednesday there was a cool event at the School of Mathematics where we had 120 odd 17 year olds in to get a taste for the Mathematics at University (some pics: <a href="https://plus.google.com/+PaulHarper/posts/eQfPv6LEftj" target="_blank">here</a> and <a href="https://plus.google.com/+VincentKnight/posts/cwM9HDh1MU9" target="_blank">here</a>).<br />
<br />
I've <a href="http://drvinceknight.blogspot.co.uk/2013/04/two-thirds-of-average-game.html" target="_blank">blogged many times</a> (and <a class="g-profile" href="https://plus.google.com/107135522210834007871" target="_blank">+Dana Ernst</a> has as well: <a href="http://danaernst.com/tag/game-theory/" target="_blank">here</a>) about the activity that I run which involves a Prisoners dilemma tournament and 2 rounds of a 2/3rds of the average game, here is my updated set of results over all the times I've played it (the second guess is after we all discuss rational behaviour):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-FE2H1nqkrSI/UuKhdtFjCnI/AAAAAAAA-Es/56fEW2E73v8/s1600/alldata.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-FE2H1nqkrSI/UuKhdtFjCnI/AAAAAAAA-Es/56fEW2E73v8/s1600/alldata.png" height="300" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="font-size: xx-small;">(if any of my student are reading this the above could help them win a box of chocolates on Monday)</span></div>
<div class="separator" style="clear: both; text-align: center;">
<span style="font-size: xx-small;"><br /></span></div>
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
This is not the purpose of this post.</div>
<br />
<b>Something terrible happened on Wednesday.</b><br />
<b><br /></b>
During my activity I always show this clip from A Beautiful Mind (<a href="http://www.imdb.com/title/tt0268978/" target="_blank">awesome movie about John Nash</a>):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/CemLiSI5ox8?feature=player_embedded' frameborder='0'></iframe></div>
<br />
Before showing the clip I always ask: "How many of you have seen the movie 'A Beautiful Mind'?".<br />
<br />
Now, I've been doing this for 4~5 years and the response I get to this question has made me realise that I'm not cool anymore. I guess there's a point in everyone's life where that realisation hits them. I've been in denial until Wednesday when for the first time ever: <b>not one student had seen the movie :'(.</b> This makes me sad because I think this is probably one of my favourite movies and one I've always thought was pretty cool.<br />
<b><br /></b>
Here's a little plot showing what <b>I've been telling myself </b>over the past few years (the fact that xkcd style graphs is <a href="http://matplotlib.org/xkcd/examples/showcase/xkcd.html" target="_blank">now native to matplotlib is cool</a>, my previous attempt at one of these: '<a href="http://drvinceknight.blogspot.co.uk/2013/05/probability-of-saying-yes-to-academic.html" target="_blank">probability of saying yes to academic responsabilities</a>'):<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-oZm6QL4kHMQ/UuKl_eXLEaI/AAAAAAAA-Fg/ikgyGWGdDp8/s1600/howIfeelaboutstudentsnothavnigseenbm.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-oZm6QL4kHMQ/UuKl_eXLEaI/AAAAAAAA-Fg/ikgyGWGdDp8/s1600/howIfeelaboutstudentsnothavnigseenbm.png" height="480" width="640" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
When I first asked and had about a quarter of the room know what I was talking about I thought that it was kind of cool and a sign of no longer being a kid...<br />
<br />
When in twenty years time I embarrass my daughter by opening the door to her boyfriend/girlfriend wearing pyjamas; inviting him/her inside for a talk and reading him/her passages of my PhD thesis or whatever else I can think of, I'll be able to say that it's revenge for not being cool any more and that I made this decision on the 22nd of January 2014.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-2723198164899432682014-01-23T09:58:00.001-08:002014-01-23T09:59:12.579-08:00My Game Theory YouTube Playlist and other resourcesI just added Graham Poll's awesome <a class="g-profile" href="https://plus.google.com/115229808208707341778" target="_blank">+YouTube</a> playlist (<a href="http://goo.gl/UZ1Ws">http://goo.gl/UZ1Ws</a>) to my <a href="http://goo.gl/iKrTy3" target="_blank">"reading" list</a> for my Game Theory course that I'm teaching on Monday and thought that I should also include the humble videos related to Game Theory that I have on my <a href="http://www.youtube.com/channel/UCJoZNbN4ziZBIfzC1zjuHYA" target="_blank">channel</a>:<br />
<br />
<iframe allowfullscreen="" frameborder="0" height="360" src="//www.youtube.com/embed/AarPMxxvuCs?list=PLnC5h3PY-znw4BliiUmxChxLJWYYAe2Aw" width="640"></iframe>
<br />
<br />
I also thought I could get away with making a blog post about this. The playlist above has them in 'last in first out' order but here they are in the order that I made them:<br />
<br />
1. <a href="http://youtu.be/poYucyX7-gE" target="_blank">"An introduction to mixed strategies using Sage math's interact page."</a><br />
<br />
A video that looks at the 'battle of the sexes' game and also shows of a <a class="g-profile" href="https://plus.google.com/113421169347512599264" target="_blank">+Sage Mathematical Software System</a> interact.<br />
<br />
2. "<a href="http://youtu.be/0uLd_KQ-QoQ" target="_blank">Selfish Behaviour in Queueing Systems</a>"<br />
<br />
A video close to my research interests which look at the intersection of Game Theory and Queueing Theory. This video is actually voiced by <a class="g-profile" href="https://plus.google.com/104243854554833157722" target="_blank">+Jason Young</a> who was doing his first research internship at the time with me and will be starting his PhD at the beginning of the 2014/2015 academic year.<br />
<br />
3. "<a href="http://youtu.be/DWiAAWZfooE" target="_blank">Pigou's Example</a>"<br />
<br />
A video describing a type of Game called a 'routing game'. Pigou's example is a particular game that shows the damaging effect of selfish (rational) behaviour in a congestion affected system. This video also comes with a bit of <a class="g-profile" href="https://plus.google.com/113421169347512599264" target="_blank">+Sage Mathematical Software System</a> code.<br />
<br />
4. "<a href="http://youtu.be/aThG4YAFErw" target="_blank">Calculating a Tax Fare using the Shapley Value</a>"<br />
<br />
This is one of my most popular videos despite the error that <a class="g-profile" href="https://plus.google.com/116319893425910717496" target="_blank">+Brandon Hurr</a> pointed out at 3:51. It describes a basic aspect of Cooperative Game Theory and uses the familiar example of needing to share a taxi fare as an illustration.<br />
<br />
5. "<a href="http://youtu.be/Tz-lZy0AKRI" target="_blank">Using agent based modelling to identify emergent behaviour in game theory</a>"<br />
<br />
This video shows off <a href="http://goo.gl/qC5iH1" target="_blank">some Python code that I've put online</a> that allows the creation of a population of players/agents that play any given normal form game. There are some neat animations showing the players choosing different strategies as they go.<br />
<br />
6. "<a href="http://youtu.be/ZU_HTiwrxM4" target="_blank">OR in Schools - Game Theory activity</a>"<br />
<br />
This isn't actually a video of mine. It is on <a class="g-profile" href="https://plus.google.com/104226696062995307517" target="_blank">+LearnAboutOR</a> 's channel but it's a 1hr video of one of the outreach events I do which gets kids/students using Game Theory.<br />
<br />
7. "<a href="http://youtu.be/AarPMxxvuCs" target="_blank">Selfish behaviour in a single server queue</a>"<br />
<br />
I built a simulation of a queue (<a href="https://github.com/drvinceknight/Simulating_Queues" target="_blank">Python code here</a>) with a graphical representation (so you see dots going across the screen). This video simply shows what it can do but also shows how selfish behaviour can have a damaging effect in queues.<br />
<br />
I'm going to be putting together (fingers crossed: time is short) a bunch more over the coming term.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-4212553888783541751.post-48909062082556743292014-01-19T01:38:00.000-08:002014-01-19T01:38:16.669-08:00Is being a pro athlete like being an academic?<div style="text-align: justify;">
This academic year is a very busy one for me and I spent most of Christmas working (this isn't unusual at all amongst academics) . This didn't feel strange or 'hard': it was simply what I did.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
When one of my brothers in law pointed out that writing code on Christmas morning was a bit 'strange' it reminded me of the fact that <a href="http://www.jonnywilkinson.com/" target="_blank">Jonny Wilkinson</a> (one the best rugby players of all time) supposedly/famously practices on Christmas day (fact #3 <a href="http://www.standard.co.uk/sport/20-fascinating-facts-about-jonny-6957936.html" target="_blank">here</a>). </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>This post is going to be some thoughts about the similarity between professional athletes and academics...</b></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I watched this great <a class="g-profile" href="https://plus.google.com/102652096288109758515" target="_blank">+TEDx</a> talk the other day about a kid who describing his 'hackschooling' and in particular discusses 'what he wants to be when he grows up' (the answer is 'happy'):</div>
<div style="text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/h11u3vtcpaY?feature=player_embedded' frameborder='0'></iframe></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
As a young kid all I ever wanted to be was a professional rugby player (reality set in at about 13-14) . I more or less always had a ball with me, here's a picture of me (I'm the one with my head down) when I was 12ish (I think):</div>
<div style="text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-XFI13MEQBZE/TnnuYDYSdsI/AAAAAAAAasE/AvaeeaYgp9g/w384-h242-no/%255BUNSET%255D" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-XFI13MEQBZE/TnnuYDYSdsI/AAAAAAAAasE/AvaeeaYgp9g/w384-h242-no/%255BUNSET%255D" height="201" width="320" /></a></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I went to a rugby boarding school when I was 16 and had the best time of my life there. I was never athletically good enough to ever 'be what I wanted to be' (a pro rugby player). A nasty roller blading accident when I was 18 more or less finished off my rugby 'career' anyway. </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
From the age of about 15 though I think I realised that I needed a more realistic plan and when people would ask me what I wanted to be I'd always say: 'I want a PhD in mathematics and to be a mathematics researcher'. I don't think I really knew what that was, but that's what I would say.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
15 years later that's what I am and I consider myself <b>very</b> lucky to be what I wanted to be when I was a kid.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>1. Passion</b></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I think that's probably the first similarity between athletes and academics, it's such a competitive environment. Kids who play pro anything most probably invested (as did their families) a lot of time and effort in to getting there.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Similarly for academics. You have to work extremely hard, to get in to a good University, to do well, to get a PhD and then to finally get a 'pro contract' in the form of post-doc or similar.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>2. Luck</b></div>
<div style="text-align: justify;">
<b><br /></b></div>
<div style="text-align: justify;">
For every good pro athlete (I don't mean great), there are probably a bunch that were never 'discovered' (or who themselves never discovered that they were/could be great).</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I think this is similar to academics, with less and less funding available for research positions and the extremely competitive job market, there are probably quite a few talented people who never even think of pursuing a career in academia.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
A lot of it is probably about being in the right place at the right time. Playing a game when a scout happens to be watching is quite similar to how I got my first post-doc: there happened to be some funding available when I was coming to the end of my PhD and my current employers where open minded enough to appreciate my ability to change fields.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>3. Hard Work</b></div>
<div style="text-align: justify;">
<b><br /></b></div>
<div style="text-align: justify;">
Academia is hard. Ridiculously hard. You have to juggle various things: teaching, research, outreach, admin (I really hate admin...) and you have to be good at all of them.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Being a pro athlete is (probably) hard. You have to juggle various things: athletic ability, injuries, athletic IQ, press/media and you have to be good at all of them.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The thing is you do all these things, whether or not that's why you got in to the field in the first place. That's probably because of the passion or the pay (I'll get back to the pay later...).</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
As a rugby player I was not a good tackler, I was terrible. It was something I had to work on a lot harder than on my vision and fitness for example. I used to spend more time than most working on tackling. </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
In academia it took me quite a while to get 'ok' at writing (my PhD supervisor and <a class="g-profile" href="https://plus.google.com/103137876942082024919" target="_blank">+Paul Harper</a> who proof read a lot of my early drafts will no doubt agree with that). This was something that I had to work quite hard at (and still do!).</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Ultimately athletes and academics are faced with the same 'problem'/'opportunity'. We can work as hard as we want to. There's always further to go (more weights to lift, another training session to have, more tape to watch, more recovery techniques to try...). Here's a good <a class="g-profile" href="https://plus.google.com/110552130912289198936" target="_blank">+PHD Comics</a> that was published today illustrating what I mean:</div>
<div style="text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-mB-TUJn8rw8/UtuB6DpRRNI/AAAAAAAABMY/3zBGEa8r05s/w1000-h433-no/phd011714fb.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-mB-TUJn8rw8/UtuB6DpRRNI/AAAAAAAABMY/3zBGEa8r05s/w1000-h433-no/phd011714fb.jpg" height="172" width="400" /></a></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>4. Competitiveness</b></div>
<div style="text-align: justify;">
<b><br /></b></div>
<div style="text-align: justify;">
I love competition. I don't really mind losing, but I love competing (I have a rant that I repeat fairly often about the difference between being a bad loser and being competitive but I'll leave that for another time).</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
When I was in the running for my permanent post I loved knowing that I was working as hard as I possibly could to get it. If someone was going to get appointed ahead of me it was not going to be because I did not push myself hard enough.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The analogous holds immediately with pro athletes and it's a part of my job that I love.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>5. The pay</b></div>
<div style="text-align: justify;">
<b><br /></b></div>
<div style="text-align: justify;">
Ok this is where my analogy perhaps breaks down as the pay is pretty much incomparable but I think there are some parallels to be drawn.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
In the press a lot of athletes apparently 'fall out of love with the game' (recently an England cricketer for example was told to go home and <a href="http://www.cricket.co.uk/news/fraser_urges_finn_to_rediscover_bowling__love__rss4566997.shtml" target="_blank">remember why he liked cricket</a>), I guess that they sometimes (understandably given how much money comes their way) play for money and it becomes about contracts etc...</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
For a lot of Academics it's probably the same thing. After a while (snowed under by a pile of admin) it just becomes a job. There's nothing wrong with that of course (a lot of people perhaps end up in Academic 'by mistake' also).</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>Personally, </b>I think I have the coolest (second to being a pro rugby player) job in the world and am just ridiculously grateful to be able to do it.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The bad sides of this are that I am a workaholic and don't see my wife very often (she sometimes +1s my G+ posts so we do interact), but ultimately I get to do what I wanted to do when I was a kid (if I had been bigger, stronger and faster I'd be writing a flipped version of this on <a href="http://www.stadetoulousain.fr/Effectif-16-EN.html" target="_blank">Toulouse's website</a> right now...). In particular I have found teaching to perhaps be one of the most rewarding experiences one can have.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>I'm sure there is a lot wrong with my analogy and a huge amount of differences between 'us' and pro athletes... Perhaps this comparison is just a young boys way of coping with his workload and believing that it's actually what he wants to do and that he made it as a 'pro athlete'... ;)</b></div>
Unknownnoreply@blogger.com0