The Deferred Acceptance Algorithm (DAA) goes back to Gale and Shapley (1962). They introduce a rather simple algorithm that finds a stable matching for example for college admissions or in a marriage market. In a marriage market where M men have preferences over W women, and men take the role of the proposing party, the DAA produces what is called the M-stable matching: each man strictly prefers the M-stable matching to any other potential matching. "Stable" means that no couple of a man and a woman could break the matching by choosing another mate. This is quite a strong result.
Variations of this algoritm are used in Hospital assignments in the USA, whereby recently graduated doctors submit preferences over hospitals, and hospitals submit preferences over graduates. Another application is the kidney exchange, where the algorithm is used to find the best match between a set of donors and a set of receivers. If you're interested in this, check out Al Roth's website.

Here I'm going to use R to make a little simulation of this. It's not a spectacular movie, but it shows you how the algorithm works. So here goes: We have M men and W women in a marriage market, and each participant has a complete set of preferences (a ranking) over all participants of the other sex. In the demonstration I assumed strict preferences (no indifference between any 2 members) and that nobody wants to be single, but the algorithm can handle this.
  1. in round one all men are single. They propose to their highest preference-woman.
  2. Each woman who receives at least one proposal picks her highest preference from the set of proposers. Otherwise she stays single. Men who were rejected, go back to the set of singles.
  3. in Round two, all remaining singles propose to their second preference. All women who receive proposals accept the best mate. If there was a mate "deferentially accepted", i.e. some man from round one, he is released back into the set of singles.
  4. the algorithm stops once we cycled over all W preferences, or if there are no more male singles left. At that point the current match is the one that gets implemented.
For this demonstration I used the animation package, which is a very nice way to just record multiple plots and wrap them into some output file of your choice. The code is below.

Demonstration:


Code on gist: https://gist.github.com/1628636


flo.
Posted by
Labels: economics R
0

Add a comment

UPDATE: Following up on a comment below, I used another data source, ONS JOBS02 for the labor market statistics. I report the findings below.

I read a series of articles related to the goings of the UK housing market, the likely effects of the new Help To Buy scheme, the 10% increase in mean London house price over the last year, and employment statistics. I failed to reproduce some numbers cited in the economist (below). This post talks about this.

It all starts with this blog post on the economist:

http://www.economist.com/blogs/buttonwood/2013/09/house-prices

It talks about many things, amongst which employment and housing completions, and how the UK seems likely to be embarking on another round of debt-fueled growth.
10

For loss of a better place, I'll store my recipe for homemade pizza dough here. This will make dough for 14 people.

2kg strong white flour (no self-raising or other extras) 4 sachets of yeast, 7g each (not the super fast bicarbonate stuff) Salt Sugar Olive Oil Water The main problem is to get the right consistency, i.e. how much water to add. You'll have to do some experiments here.

I've got some questions regarding this issue, maybe someone out there has a clue.

The Austrian contingent was 300 out of 1000 soldiers

source: http://www.guardian.co.uk/world/2013/jun/06/israel-angry-austria-golan-heights.

Inspired by the Institute of Fiscal Studies' "Where do you fit in" application, where people can find out their position in the UK's income distribution, I wanted to find out how the picture in London looks like. Quite different. If you are in a very high percentile nationwide, high incomes of mainly financial sector employees in London make sure that you find yourself a couple of ranks further down.
3

I just pushed the most recent version of the PSID panel data builder introduced a little while ago. Got some user feedback and made some improvements. The package is hosted on github.

News:

I added a reproducible example using artificial data which you can run by calling 'example(build.panel)'. This means you can try out the package before bothering to download anything and it provides a simple test of the main function.
3

I got intrigued by the numbers presented in this news article talking about the re-trial in the Amanda Knox case. The defendants, accused and initially convicted of murder, were acquitted in the appeal's instance when the judge ruled that the forensic evidence was insufficiently conclusive. The appeals judge ignored the forensic scientist's advice to retest a DNA sample, because

"The sum of the two results, both unreliable… cannot give a reliable result," he wrote.

I just finished reading the extraordinary book tomorrow's table by P. Ronald and Raoul Adamchak. (I linked to Ronald's blog). In this post I wanted to quickly redo a calculation Adamchak does on page 16, where he explains to his students how much energy is required to produce the fertilizer used to grow one acre of corn using conventional agriculture (as opposed to organic methods).

Economists frequently use public datasets. One frequently used dataset is the Panel Study of Income Dynamics, short PSID, maintained by the Institute of Social Research at the University of Michigan.

I'm introducing psidR, which is a small helper package for R here which makes constructing panels from the PSID a bit easier.

One potential difficulty with the PSID is to construct a longitudinal dataset, i.e. one where individuals are followed over several survey waves.
7

I was recently asked by a friend whether it's worth to buy a house in the UK. That is, assuming they could put down the money, whether it was worth buying as opposed to renting. Apart from obvious things like the expected length of stay in one place, the interest on mortgages and how prices might develop and so forth, they were interested in particular in the amount of transaction costs they were likely to face: fees, taxes and so forth.

So Paul Krugman laments in his post that policy makers across Europe have blindly signed up to the "Austerity only" ticket. He cites some evidence which I find fairly convincing. I just want to raise the point that what he says cannot be used as a critique against the Monti government.

Basically what he's saying is that Monti was installed as a puppet of European creditor nations to make sure that austerity would be imposed and the country's government debt would be continued to be serviced.
2
links
links
About Me
About Me
My Photo
Blog Archive
Blog Archive
Loading
Dynamic Views theme. Powered by Blogger. Report Abuse.