Monday, August 30, 2010

Peer to peer lending

I've been reading about Funding Circle in
this article in the Guardian (Funding Circle's home page also contains links to other news articles that have featured it). It's a new internet-based market that allows individuals to lend money to small businesses. So, it is similar to Zopa, which supports lending of money amongst individuals.

I've not tried it myself but am tempted... you just need a few hundred pounds to make available for loans, and your money gets divided amongst 20 different businesses, so as to spread the risk, and then the claim is that you make on average about 6% on your savings, as opposed to about 2-3% as you currently make in a savings account. Interesting features include: lenders can bid their interest rate, resulting in a trade-off in that if you set a higher rate, it may take longer for your funds to be accepted. You can also set up or join a "circle" (see the help centre) to specialise which businesses you lend to. If you want your money back, you have to sell your outstanding loans to another lender (I assume that effectively results in a penalty for early withdrawal). The system supports "autobid" which manages the division of your funds amongst distinct businesses, and recycles repayments into new loans so that your funds continue to earn interest. Finally, on the downside, my impression from reading the help page is that the tax treatment of income is not very lenient.

Monday, August 16, 2010

Two shocks to the (British university) system

Two recent news articles caught my attention: this one in yesterday's Observer, and this one in today's Guardian. In different ways, they raise profound questions about how British universities will evolve over the next ten years.

The first of the above articles draws attention to a “recruitment drive” by EU universites, aimed at would-be university students in this country. It may come as news to many such students (or their parents) that they have the option to study for degrees in various other EU countries, where the fees are lower than in the UK, and get tuition in English. The article focuses on Maastricht University, by way of example. It's an attractive option: nice town, English language tuition in some subjects, strong research. The recruitment drive is claimed to be driven by our own supply-and-demand problem: too many UK students chasing too few places. The interesting question is whether foreign universities can attract students who actually could get places over here. That potentially reverses higher education's role as a net exporter for the UK. Can this be used as an argument for better state support for universities?

The second article (similar one here), entitled London is most cost-effective UK city for students, publishes a league table, the “2010 NatWest Student Living Index” which evaluates the cost of living for students for 25 cities in the UK, and favours London, surprisingly — the catch is, that cost-effectiveness is a function of a student's earning potential in the city, rather than just cost of living. Seemingly, students are now “meant” to be working part-time while studying (at least, in order for the ranking to be meaningful). Of course, many students get support from their parents and so some of them have the option to study full-time, but (as mentioned in both articles) 46% do not. Universities themselves, meanwhile, remain pretty much oblivious to these inequities — if a student fails an exam, you can cut him some slack on the grounds that his grandmother died recently, but you can't make allowances for him having been pulling pints in the local bar every evening. I think the best fix that is likely to be achievable, would be for universities to be more flexible about the duration of study. The current rigid three-year schedule is dictated by the (declining) Government funding scheme for students, as devised when full-time study was the standard. We could move towards a more German approach of getting your degree in however long it takes you (and we should accept a higher drop-out rate).

added 17.8.10: A new Guardian article:
A landmark review into university finance is expected to recommend that student loans, now only available to those on full-time courses, are extended to part-time students to cover the fees they must currently pay upfront, the Guardian has learned. Such a move would pave the way for a major change in the way university education is viewed, with a three-year stint in a new city no longer a given.
Part-time study is a way forward, but I wonder whether you need a binary divide between full-time and part-time study, or whether we should be able to allow for study schedules that fall between the two.

Tuesday, August 10, 2010

Fictitious play

Fictitious play is a very simple iterative procedure for finding a Nash equilibrium of a game. Before stating an open problem of interest, let me give a quick summary of how it works (or, you can read the Wikipedia page for a more careful description). It's an iterative process that if it converges, must converge to a Nash equilibrium, but unfortunately it doesn't always converge. However it always works for 2-player zero-sum games, more on that below.

Assume you have a 2-player game. To begin with, each player chooses a single pure strategy. Then, both players construct sequences of strategies according to the following rule: At each step, a player considers the sequence chosen by the other player, he supposes that the other player will randomize uniformly over that sequence, and he chooses a best response to that mixed strategy. (So, a player's sequence is treated as a multiset of strategies, one of which is selected uniformly at random.) Technically, we should explain how to choose a best response in the event of a tie (2 equally good responses) - there are various options, but I won't discuss them. Anyway, the chosen best-response is added to a player's sequence, and that's how the sequences get extended.

I have recently been pestering various people with the following question: What is the complexity of the following problem:

input: a bimatrix game. For each player, an initial pure strategy.

question: does FP converge when those initial strategies are chosen at the start?

Additional question: If it converges, give the NE that it converges to.

(and just to be clear, this is not the same thing as asking about the complexity of FP itself.)

I recently read one of the early papers on the topic, namely: Robinson, J. (1951) "An Iterative Method of Solving a Game", Annals of Mathematics 54, 296-301. It is a beautiful paper, just 6 pages; I would recommend anyone to read it. It proves the result mentioned above, that for any zero-sum game, the payoffs obtained by the players do indeed converge to the value of the game. (The convergence rate that is implicitly obtained is very slow - maybe it can be improved?) Note, that is not the same thing as showing that the players play the correct strategies after any given number of iterations - a new paper in SAGT (Felix Brandt, Felix Fischer and Paul Harrenstein "On the Rate of Convergence of Fictitious Play") indicates it may take arbitrarily long to find the right strategies, depending on the payoff values.

Another nice question follows up on a paper by Vince Conitzer "Approximation guarantees for fictitious play" (Allerton 09). This paper studies the quality of approximate equilibria obtained by FP, in a scenario where the number of iterations is less than the number of pure strategies per player. But, if it's applied to a n×n game, and allowed to run for more than n iterations, for all we know it may actually do better than the best currently-known polynomial-time approximation algorithms (that obtain round about 1/3-approximation, if all payoffs are in [0,1].) Although, I will pessimistically guess that some troublesome games that haven't yet been identified, have it obtaining just a 1/2-approximation.