Today’s talk’s topic is an idea so important in game theory, and with so many applications in different fields including computer science, that it earned its discoverer, together with Reinhard Selten and John Harsanyi, the 1994 Nobel Memorial Prize in Economic Sciences.
To introduce this idea, together with other basic game-theoretic notions, we resort to some examples. Here goes the first one:
Alice and Bob are planning an evening at the cinema. Alice would like to watch the romantic movie, while Bob would like to watch the action movie. Neither of them likes much the other’s favored movie: however, should they split, the sadness for being alone would be so big, that neither of them would enjoy his or her movie!
This is the kind of situation modeled by a game in normal form, where we have:
- A set of players.
- A set of strategies for each player.
- A collection of utility functions which associate to each strategic profile a real number, such that is the utility player gets from the strategic profile .
In the case of Alice and Bob, this may be summarized with a table such as the following:Romantic Action Romantic Action
Such tables represent games in normal form between two players, where the rows of the table are labeled with the strategies suitable for the first player, and the columns of the table are labeled with the strategies suitable for the second player: the entries of the table indicate the values of the utility functions when the first player plays the corresponding row and the second player plays the corresponding column. When we want to emphasize the role of player in contrast to the others, we write as , and talk about the strategy of player given the strategic profile of the other players.
Suppose that Alice is the first player, and Bob is the second player: then the table tells us that, if they both choose the romantic movie, Alice will enjoy it a lot (utility value ) and Bob not very much (utility value ). However, if Bob defects from this strategic profile and goes watch the action movie, he will ultimately not enjoy it, because he will be sad for not being together with Alice—which was the entire point about organizing the evening at the movies!
Let us consider another game (a rather serious one indeed) where the players are a lion and a gazelle. The lion wants to catch the gazelle; the gazelle wants to avoid being caught by the lion. To do this, they may choose between being on the move, or staying more or less in the same place. It turns out, from observation in the field, that the table for the lion-and-gazelle situation is similar to the one below:Move Stay Move Stay
We observe that, for the lion, the most profitable strategy is to move. Indeed, if the gazelle moves, then the utility for the lion is if he moves, which is more than the he gets if he stays; on the other hand, if the gazelle stays, then the utility for the lion is if he moves, which is more than the he gets if he stays. A strategy such as this, which always gives the best possible result independently of the other players’ strategies, is called a dominant strategy. Such strategies are indeed quite rare: indeed, neither Alice nor Bob from the previous game had a dominant strategy, nor has the gazelle here, as they can maximize their own profit only by choosing the same strategy as the other player.
So, what if we relax the requirement, and just demand that every player chooses the most favorable strategy, given the strategies of the other players? This is the basic intuition under the concept of Nash equilibrium, formalized and studied by John Nash in his 1950 doctoral thesis.
Definition 1. A Nash equilibrium for a game in normal form is a strategic profile such that, for every player and every strategy feasible for player , it is the case that .
The situation when both the lion and the gazelle are on the move, is a Nash equilibrium: and is the only Nash equilibrium in the corresponding game. (By definition, every dominant strategy enters every Nash equilibrium.) The situation when both Alice and Bob go watch the romantic movie, is a Nash equilibrium: and so is the one when they go watch the action movie.
So, does every game have a Nash equilibrium?
Indeed, suppose that the predator and the prey, instead of being large mammals such as the lion and the gazelle, are small insects such as a dragonfly and a mosquito. It then turns out, after careful observation, that the table for the predator-prey game gets more similar to the following:Move Stay Move Stay
In this situation, the dragonfly maximizes its utility if it does the same as the mosquito. In turn, however, the mosquito maximizes its own utility if it does the opposite than the dragonfly! In such a situation there can be no such thing as a Nash equilibrium as defined above.
Where determinism fails, however, randomization may help.
Definition 2. A mixed strategy for the player in a game in normal form is a probability distribution on the space of the strategies for player . A mixed strategy profile is a collection of mixed strategies for each player.
For example, the dragonfly might decide to move with probability , and stay still with probability ; similarly, the mosquito might decide to move with probability , and stay still with probability .
With mixed strategies, the important value for player to take into account is the expected utility given the strategic profile
which we may write when we want to emphasize the role of player .
Now, suppose that the dragonfly decides to set its own paramenter so that its expected utility does not change if the mosquito decides to move or to stay: this corresponds to the dragonfly maximizing its expected utility, given the mixed strategy of the mosquito. Our table tells us that this corresponds to
which has solution . In turn, if the mosquito sets its own parameter so that its own expected utility does not change if the dragonfly decides to move or stay, then
which has solution . The situation where the dragonfly moves with probability and the mosquito moves with probability is a situation none of the two insects has any advantage to change on its own part, given the choice of the other.
Definition 3. A mixed strategy Nash equilibrium for a game in normal form is a mixed strategy profile such that, for every player and every mixed strategy feasible for player , it is the case that .
And here comes Nash’s great result:
Nash’s theorem. Every game in normal form that allows at most finitely many pure strategic profiles admits at least one, possibly mixed strategy, Nash equilibrium.
It is actually sufficient to prove Nash’s theorem (as he did in his doctoral thesis) when there are only many players, and each of them only has finitely many pure strategies: such limitation is only apparent, because the condition that pure strategy profiles are finitely many means that all players have finitely many pure strategies, and at most finitely many of them have more than one.
The idea of the proof, which we might go through in a future Theory Lunch talk, goes as follows:
- Identify the space of mixed strategic profiles with a compact and convex set for suitable .
- For define a family of continuous transformations .
- By the Brouwer fixed-point theorem, for every there exists a mixed strategic profile such that .
- As is compact, the sequence has a limit point .
- By supposing that is not a mixed strategy Nash equilibrium we reach a contradiction.
We remark that Nash equilibria are not optimal solutions: they are, at most, lesser evils for everyone given the circumstances. To better explain this we illustrate a classic problem in decision theory, called the prisoner’s dilemma. The police has arrested two people, who are suspects in a bank robbery: however, the only evidence is about carrying firearms without license, which is a minor crime leading to a sentence of one year, compared to the ten years for bank robbery. So, while interrogating each suspect, they propose a bargain: if the person will testify against the other person for bank robbery, the police will drop the charges for carrying firearms without license. The table for the prisoner’s dilemma thus has the following form:Quiet Speak Quiet Speak
Then the situation where both suspects testify against each other is the only pure strategy Nash equilibrium: however, it is very far from being optimal…
Are you experienced at delivering high-quality apps? Are you interested in data analysis, pattern detection, optimization, machine learning? Do you like working on numerous, diverse projects with quick timelines? Do you write well-structured code that other people would like to pick up, learn from, and reuse? And -- of course -- do you love functional programming?
FP Complete is hiring a Haskell data analysis application developer to work on numerous compact applications and libraries that will be used, learned from, and reused by our customers to understand critical data in a timely way. The focus is on financial markets (such as equities trading), so experience with that subject is strongly desired and will work in your favor. We also do significant scientific work. Typical tasks will range from a few days to a few months in duration.
You can work from home, anywhere in the world, as long as you are available 30+ hours a week, on a schedule compatible with Eastern USA colleagues. You have to be organized and good at working with limited supervision, from understanding requirements to design, implementation, test, delivery, and versioning with iterative improvements. You must be an experienced functional programmer in Haskell or another FP language, with sample code to show.
Extra good if you understand HPC, linear algebra, statistics, and/or team software engineering methods, or have contributed significantly to libraries or other open-source projects. Also great if you have experience dealing with end users and/or creating training materials. And if you can start soon!
I’m the founder and head of FP Complete, the Haskell tools & services company. Join our team and stay with us as we grow. Email your resume/C.V., compensation requirements, descriptions of some of your impressive accomplishments, and some links to good FP source code written personally by you, to me at firstname.lastname@example.org . Applicants for previous openings are welcome to apply again. For this position we will accept applications from highly experienced candidates, as well as highly motivated less senior candidates who can show they have the skills and are ready to work. This is a long-term contractor position.
Questions, feel free to email or PM me. Thanks. It is a pleasure to be a part of such a great community.submitted by FPguy
[link] [4 comments]
I started a couple months back an alternative home page for Haskell. It is a work in progress, but as I work on it every so often I push changes to it.What’s wrong with haskell.org?
haskell.org isn’t doing a satisfactory job for me as a place to impress people with Haskell and to guide them into using it.
- Its design is broken or just strangely put together and it’s not responsive.1
- There are too many links on one page which indicates indecision about priorities and a lack of user story or particular target audience. Who’s this site targeting? Where are they supposed to go next? Is it answering the right questions?
- Also, the uncoordinated effort of the wiki misleads people and pages begin to bitrot. There are too many to vet.
The current home page is historically resistant to change, technologically and socially. My relationship to haskell.org over the years has been one of stonewalling when requesting access, of slow replies, and of bike-shedding and nitpicking when proposing designs. A camel is a horse designed by committee and haskell.org is such a horse.So your plan is?
The plan goes like this:
- The first part of the plan was to survey existing programming language web sites.
- Decide on an audience.
- Decide on a theme.
- Decide on user stories.
- Yay, shiny web site.
I looked at the following web sites:
There are good points and bad points for each one, but I came up with a set of things that are common among all, and a couple additional points I came up with:
- A theme
- Visual things
- Opening paragraph
- Code sample
- Thumbnails of videos
- Pictures of community stuff; human beings
- Selling points
- Supporters / sponsoring companies
- Other links
- Application areas / success stories
- Language options (locale; Japanese, German, etc.)
If you’re interested in my review of each home page, here’s what I wrote:
- F#’s is boring, it has no character, features no code samples. But it does have a bunch of company backing logos.
- Ruby’s is among the best. It has character. It has two navigations, which is bad,2 but otherwise it’s perfect. Otherwise, my only criticism is that it overemphasizes news which most new people don’t care about and which Rubyists get via other sources.
- Python’s, like Ruby’s, is good. It has character. It has code samples. But it’s worse than Ruby in that it has four areas of navigation. The top bar, the second bar, the third call to action section, and finally the footer. Each of which has a different subset of total places of interest. Again, it uses space presenting news items. However, I particularly like the section which shows Web Programming, GUI Development, etc. and then next to each the library one would use to accomplish that task. That’s very practical and speaks positively about the language and community.
- OCaml’s is not bad either. It has a deserty theme giving it its own character. It suffers from link overload, which implies it might’ve been copying Haskell’s or Python’s home pages.
- Go’s home page is notable for its embedded try feature, something which I’ve wanted Haskell’s home page to have for a long time. It’s also got a very simple and straight-forward navigation. The logo/mascot is in there, giving the whole page a bit of fun character, too. While not much to look at, unresponsive to device, clearly written by a pragmatist systems person, it has a lot going for it and is in my mind among the best I’ve looked at.
- For Perl’s homepage, I’ll echo similar complaints as before. Link overload. It’s a rather lazy way to make a home page. Let’s throw in as many links as we can and hope people read it all and by chance find what they’re looking for. Oh and to fill out the page, let’s add recent uploads (who cares?) and news items (again, who cares?). Finally, it has no character whatsoever. It has the awful O’Reilly pen drawing of a random animal that’s supposed to embody the character of the language, but is meaningless. I probably dislike this one the most, a close tie with F#’s.
- Scala’s is very trendy and pretty. It’s got a lot of events and training info which, along with the header mountains, gives it a very communal and active fresh feel. Again, echoing the praise of Go’s page, it has very simple navigation. One navigation at the top, and then two big buttons for the most common tasks. After that, like Python’s home page, there’s a good review of features of the language that make this language more interesting than the next language. I give credit to this page for visual inspiration.
- Clojure suffers a little bit from linkitis, too. It has three menus and then a page full of links. It has zero code samples on the first page you land on. But it is clean and has a certain character to it.
Generally, I’m not sure why sites bother with search boxes. Unless they’re implementing code-aware searches, Google will be faster and more accurate every time. As Joel Spolsky says of his StackOverflow, Google is the user interface to SO.
Regarding linkitis, I will quote Don’t Make Me Think that a user will happily click three links to narrow down what they want, than to have to think and search around a page to find what they want, if they have the patience for it.The audience
The audience is newbies. People who use Haskell don’t go to haskell.org. They go to Hackage, or they google search and find wiki entries, or the GHC manual. A home page shouldn’t cater to Haskellers, it should cater to would-be Haskellers.
Naysayers for an attractive home page say things like “we don’t want superficial people joining the community” (as if they could just learn Haskell on a whim!), but forget that people live insular lives. There are millions of people out there who’ve never heard of Haskell. If a random web user stumbles upon it and is taken by the look of it, what are they going to do with it? Share it. How did you first hear of Haskell? I was told about it by a friend.
To decide on the kinds of things I want to see on a landing page when I first look at a language I’m unfamiliar with I ask a bunch of common questions. I’ve condensed them all in the user stories section.The theme
I’ve always liked the purple and green of the old Haskell logo. I don’t know why gray/sky blue ended up being used for the new logo. So I decided I’d keep that purple theme and made some mockups. Purple is a cool color.User stories
The user stories I’ve identified have been encoded in the main navigation:
- A user just wants to try Haskell. They scroll to ‘Try it’ and, well, try it. There can be links to further sites like Try Haskell, School of Haskell, Code Pad, Lambdabot, services like that.
- A user wants to download Haskell. They click ‘Downloads’. What particular file they want to download doesn’t matter. It could be GHC, it could be the Haskell Platform, it could be some packages. If they want to download something, they go to Downloads.
- A user wants to interact with/find community. They click ‘Community’. On that page is a list of various community places of interest, which may itself be expanded with videos and things like that.
- A user wants to get information. They click ‘Documentation’. That means books, reports, papers, tutorials.
- A user wants to catch up with what’s new in general, with Haskell. They click ‘News’ and there can be an RSS feed available on that page. Haskell News is mostly suitable to this task.
I synthesized all this together into a comp in Inkscape.
I think it answers the following questions:
- Any particular brand/logo? [header]
- In a few words, what is this thing? [header]
- What does it look like? I want to see code immediately. [header]
- Can I try it right now? [try haskell section]
- I’m still interested. Is anyone using this thing? [community & videos, events section]
- What are the selling points, over, say, ML or C#? [features section]
- Where do I download stuff/find community/docs/news? [the main menu at the top]
I made a mockup for the subsite, but that’s uninteresting.Implementation
I’ve implemented a starting prototype here at haskell-lang.org. At the time of writing it doesn’t yet fully flesh out all the things planned in the mockup.
There are a few half-done pages in the navigation, fleshed out just enough to satisfy my plan and to motivate for further work.
Here’s a quick comparison of the two sites now:
To illustrate, here’re the sites on various devices:
I’ve also made a little page to render wiki pages from haskell.org. There is a simple request sent to haskell.org for /wiki/* pages, it parses the Wiki syntax with pandoc and renders it to HTML, at least for the pages that MediaWiki is kind enough to serve. Example: Handling errors in Haskell
Here is the above wiki page with a cleaned up presentation.
Note that MediaWiki is a bit stunted in the data it exposes for use. Some pages just aren’t available, others produce invalid XML, etc. This is why the wiki is not exposed in the navigation.
I’m not sure about exposing the wiki directly, but rather some selected vetted pages, perhaps.Going forward
I still have to:
- Fill in the Try support
- The features copy
- Examples for each of said features
- A list of video thumbnails to appear under the community banner (as in the comp)
- Upcoming/past events
- At least 5 examples for the header code
- Add books & manuals to the Documentation tab
I’m happy with the look and feel and organization. Now is the matter of filling it with useful things. That’ll take about a month, by weekend/spare-time development. Once that’s done, it will be ready to link to newbies. I’ll have a link to be proud of when people bring up Haskell.
I could solicit the community for contributions via pull requests. It depends on people approving of the project and my approach. So if you’re reading this and you accept my design and organization3 and would like to contribute content (content pages are written in markdown), then pull requests to the github repo would be most handy. I will merge your changes and redeploy with relative speed.
In particular, content in wanting which is not straight-forward for me to produce:
- About 5 examples of concise, short Haskell code which can sit in the header. Ideally, each example can be clicked and it will take you to a markdown page under an Examples hierarchy that explains how the code works.
- The features section needs to be filled out with content. I’m not entirely sure that the headers are decent, but I’m pretty sure they’re a good start.4 Pages for each of those which contain example code of real problems that are solved are needed.
I won’t be able to actively work on this for a few days, but I can do bits and bobs here and there on the weekend and I always have time to merge straight-forward changes.
When I open haskell.org on my phone, I see the tablet-sized layout with tiny text. The layout goes wonky on the tablet version.↩
That means that you won’t nitpick design decisions, bike shed about the theme, organization, choice of picture in the landing page, etc.↩
Maybe type-classes and monads might be of interest because both where pioneered by Haskell and, at least in their native support, are both peculiar to Haskell.↩
The Debian Haskell Group has no proper policy about when to update a certain package to a new version from Hackage. So far, we upgrade when one of us personally needs something, when someone nudges us, if its required as a dependency or just when we feel like it. I was thinking about ways to improve that.
One thing that we should definitely do is to upgrade to new versions that differ only in the forth version number, e.g. from 184.108.40.206 to 220.127.116.11 – these are most likely bug fix uploads and have little risk of breaking things. (Unless they are only changes to the .cabal file, then they might not be an improvement for our users or us.) I plan to code that soon.
But what else can we do? Ideally we’d package versions that will be the newest version for a long time, and not versions that are going to be replaced the next day. Unfortunately, deciding that requires visionary powers. But maybe there is a correlation between the upload history and the lifetime of a new package? Maybe there are patterns, e.g. the first upload after a long time tends to be replaced fast, but the third package in a short succession has a high chance to live long? Can we predict the livetime of a freshly uploaded package? So after a bit of hacking I got this graphic:
It needs a bit explanation: Both axis are time differences, the picture is one year by one year. For every release of which we know the lifetime (i.e. there has been an upload later), we draw its history on a vertical line. The horizontal position of the line corresponds to the lifetime of the release: A package that was superseded immediately later (which I sometimes do after spotting annoying typos) would appear on the far left, a package that is stable for one year on the far right.
The history itself is a series of dots, representing the previous uploads of that package, with their distance from the lower edge indicating the time that has passed since then. So if a package had two updates half a year ago, and then no update for another half year, it would contribute two dots right above each other in the middle of the picture.
Unfortunately, the picture does not yield any insight, besides that short-lived packages are more frequent than long-lived packages.
So I tried another view:
I grouped uploads by the livetime of their two preceding uploads. For each such groups, the circle indicates the average livetime. The darkness indicates the absolute number in the sample. So we see a correlation between the packages livetime and the livetime of its predecessor, which is also not very surprising. We can state some hypothesis, like: “A package replacing a very old package is likely to be long-lived if its pre-predecessor lived very long or very shortly, but less so if that lived for a few months.“ But I’m not sure of the significance of these.
I could have also taken into account which uploads are major and which are minor, by looking at the version number, but I didn’t.
What’s the conclusion? Nothing much. I got some funny looking graphs. And there needs to be a way to render pictures like the first within the axes of a Chart diagram. I put the (somewhat hackish) code online – feel free to play with it.
Today, it's possible to build rich, sophisticated applications in the browser. Everybody's familiar with GMail and Google Maps, of course, but have you seen stuff like Mozilla's PopcornMaker?
This just blows me away. And applications like this are appearing all over, and they're well within the reach of any tech startup.
Of course, the major problem with building sophisticated applications is that now you need to maintain them. And just hacking everything together with jQuery is probably going to make a mess.
I've built a few rich applications during the last twelve months, both for clients and for myself. Based on that experience, here's a list of tools that have worked well, and tools that look promising for the coming year. This list is shamelessly subjective, and probably already obsolete. Please feel free to contact me with better suggestions; I'll add a bunch of them to the article.Personal choices: Table of contents
- Model View Controller: Ember.js (or Angular.js)
- Asynchronous callback handling: Promises/A+
- Module system: ECMAScript 6 modules and a transpiler
- Package management: Bower.js
- Unit testing: QUnit if I must, Jasmine or Mocha if I can
- DOM manipulation and compatibility: jQuery
- Syntax: CoffeeScript (OK, OK) or a couple of other alternatives
- The bad news: These recommendations will be obsolete quickly
The standard disclaimer applies: In 95% of all cases, it's better to stick with what you're already using, unless something else will offer you an order of magnitude better productivity.
Keep reading for code snippets, rationales and some promising alternatives.
The current version of unification-fd (0.8.1) does not build on GHC >= 7.8 due to changes in the coverage condition for fundeps. I've made a new version which builds, but before posting it to Hackage I want to make sure it doesn't break too much code.
If you are a current user of unification-fd, please try compiling your code against the current HEAD version (darcs, sdist) and let me know if you run into any issues with your BindingMonad or RankedBindingMonad instances or with ambiguous types during inference.submitted by winterkoninkje