Computing Boston and TTC in Python

Question

This is somewhat of a follow up question to Available code for computing solutions to matching algorithms?.

In the above question, I got great answers, but all of them were for R.

I am now programming a lab experiment in otree, which means I am working with Python.

It is fairly easy to find code in python solving matching problems using the Deferred Acceptance mechanism, but I wondered if anyone knew of python code for some of the other common mechanisms in the literature. Specifically, I am looking for python code for

The Boston mechanism (aka. Immediate acceptance)
The Top-trading cycle algorithm

In the best of the worlds, these codes would

Be compatible with the school choice model (i.e. many-to-one matching problem in which agents in one side of the "market" can be matched to many agents on the other side)
Allow for constrains on the lenght of the preference list agents can report (see http://www.sciencedirect.com/science/article/pii/S002205310900057X)

However, I would already be very happy with python code for Boston and TTC, even if the two last features are not implemented.

Just in case, Python can run R. See eg rpy2. – Anton Tarasenko Sep 09 '15 at 21:01 — Anton Tarasenko, Sep 09 '15 at 21:01

Martin Van der Linden · Answer 1 · 2016-01-07T05:31:12.433

1

I found one implementation of TTC in python at http://www.dreamincode.net/forums/topic/377004-algorithmic-game-theory-top-trading-cycle-procedure/?ref=dzone.

However, it does not seem to include the two additional features I was mentionning.

With of without these two features : I would still love to hear about more implementation of TTC, and about implementations of Boston.

edited Jan 07 '16 at 05:31

answered Sep 09 '15 at 16:29

Martin Van der Linden

5,237
23
43

2

I'm the author of that article. I cross-post both on Dream.in.Code and my personal blog. The math is cleaner on my blog, which supports LaTeX rendering. For reference: https://michaellevet.wordpress.com/2015/06/01/algorithmic-game-theory-house-allocation-problem/ – ml0105 Sep 09 '15 at 20:53

score 0 · Accepted Answer · answered Oct 22 '15 at 19:22

I ended up putting together some code to compute the assignment under Boston and deferred acceptance. It can be found at https://github.com/vanderlindenma/school_choice_python.

The code there uses and modifies former code from Jeremy Kun, stable-marriage, (2014), GitHub repository, https://github.com/j2kun/stable-marriages, described in one of Jeremy's blog posts at http://jeremykun.com/2014/04/02/stable-marriages-and-designing-markets/.

I hope to expend on the code that’s currently available and add more functionalities soon. Any participation is welcome.

Computing Boston and TTC in Python

2 Answers2