Sunday, July 05, 2015

Peyton fest

I write to thank the organisers of Peyton Young’s 70th birthday symposium, held in Oxford last week. The great thing about birthday symposia is that they are not rational in the economic sense (they do not make money) so they feel like taking a stand against the bean-counting mentality. Through celebrating the work of one of the research community’s well-known figures, we celebrate the community itself, and the intrinsic interest of the topic. Here’s a couple of thoughts on rationality. Vince Crawford’s talk made a point that explains one reason why game theory usually focuses on rational agents rather than boundedly-rational ones: I am tempted to call it the Anna Karenina principle: that rational agents are all alike, but every irrational agent is irrational in its own way. Hence, the study of irrational agents becomes diffuse, with a difficulty to reach agreement on what kind of irrationality to allow. (e.g.: I care about what values of ε one could compute ε-Nash equilibria in polynomial time, and one could argue endlessly about what constant value of ε might be considered acceptable. This is why a PTAS would be so nice.) Prior to hearing that point being made, when asked to explain why economists focus on rational agents, I’d note the basic requirement of economic mechanisms that they should function well in the presence of rational agents, and in general it’s too much to ask that they should perform well in the presence of irrational ones. The other item: in Peyton’s speech at the end, he considered possible future directions for game theory, and proposed that adaptability to changing conditions may become the new rationality: an agent should be judged on how well it handles change rather than whether it best-responds to a fixed environment.

and the group photo

Friday, June 12, 2015

unimportant email

I’ve been getting quite a lot of journal spam recently. I wonder what sort of people would take the following seriously; it has an entertaining aspect (subject line: “Possible chance of publishing”).
Dear Dr. Paul Goldberg,

Greetings from International Journal of Innovative Research in Computer and Communication Engineering!

Hope this mail finds you in a jovial mood.

Assuming that you may have received our previous correspondence we are sending this as a polite reminder request to you. To know more about the journal, please visit here:

We would like to invite you to contribute a manuscript to be considered in the forthcoming issue of International Journal of Innovative Research in Computer and Communication Engineering (IJIRCCE).

(remainder not quoted)

“polite reminder”? I’m feeling more jovial by the second…

It reminds me of a fairly reliable rule about email, which is that there is an inverse relationship between the importance of a message, and the quantity of formatting (colours, fonts, links etc.) that it contains.

(added 16.5.15:) Another similar item of journal spam (subject “Publish your research”; includes request to be notified when you read the message):
Dear Dr. Paul Goldberg

Greetings from International Journal of Biomedical Data Mining!

Hope this mail finds you in a pink health!

We are enthralled to know about your scientific contribution in the area of Artificial Intelligence, Data mining and would like to invite you as a potential author.

(remainder not quoted)

(added 7.7.15:) The following comes from an address ending in katsura.letstogether.org, with a reply-to address of sas@seipub.org. Subject is *Solids and *Structures(SAS):

Dear *NAME*,

Your paper, Revenue maximization in a Bayesian double auction market, draws our attention.

Introduction

Solids and Structures(SAS) is an internationally refereed journal dedicated to publishing the latest advancements in solids and structures research.

Indexing
Googleckan
World CatgetCITED
Academia.edupub zone
BibleScribd.
LinkerDeepdyve
Aol.ULRICHSWEB
Rice StARCHIVE
WIPOCloud D
AcademicKeys
Submission deadline

July. 26, 2015

Tips: accepted paper which is submitted before the deadline can enjoy a discount on registration fee.

That last example uses the new-ish technique of making reference to one of the recipient’s papers, presumably to gain his attention. Shame about the salutation, Dear *NAME*.

Wednesday, April 29, 2015

tempted by a cut to 6k tuition fees?

I have as many ill-informed opinions as the next voter, but luckily the only ones I consider writing up here are the ones directly relevant to academia.

A well-publicised Labour manifesto policy is to cut tuition fees from 9k/year to 6k/year, and this is meant to be a positive selling-point of their package.  Much as I disliked the change to the current regime, I can’t get excited about this proposal. Thinking about why not:
  • A reduction of 3k is not a very big discount on 9k plus living expenses.
  • The 6k proposal lacks detail about the repayment terms and interest rates (I did read the relevant part of the manifesto). Thus, we’re being offered a pig in a poke.
  • There is no proposal to refund the students who have been required to take on 9k of debt per year. This shows a regrettable tolerance of unfairness to people who have ended up in greater debt due to sheer bad luck. The 6k tuition fee proposal is not so much about righting a wrong, as about a headline-grabbing policy proposal.
  • This article seems to be showing that the current fees have at least brought in more money to UK universities, which is being spent on students. This takes place at a time of considerable international competition between universities, and we cannot afford not to spend more money on facilities at universities.
  • While the current fees regime in unsustainable, we should welcome a transient period of stability (“meta-stability” for readers who know about Markov chain mixing…); I think we’re suffering from change-fatigue.
None of the above is supposed to be taken as supportive of the current 9k fees. I could actually feel supportive of this proposed cut to 6k, if it was presented as a step in the right direction; some kind of down-payment on the way to the abolition of fees. But that’s not how it’s being presented.

Wednesday, April 01, 2015

Rating my co-authors

I feel like I’m something of a late-comer to the Rate My Co-author community (I include a link below, for completeness) and now feel like I should have joined earlier. It looks like one of these things whose user base reaches a critical mass, and then everyone has to join in. To be honest, I’m rather annoyed at how many of my co-authors seem to have claimed more than their fair share of the credit for various papers I worked with them on; now it seems I have to choose between making a counter-claim (and rely on Procaccia and Goldman’s fair division algorithms to moderate), or else enter into a costly dispute that may leave me worse off than if I just cave in and accept the lower share of credit. Their plan to integrate with Google scholar to produce the “world’s most accurate measure of an individual’s research contribution” is worrying. On the other hand, the fun aspect is seeing quite how many well-known papers seem to have dragged their authors into protracted disputes, to the extent that the authors end up with fewer “good co-author” points, than if only they had originally accepted a smaller share of the credit!

Anyway, the thing I like is the way you get to rate co-authors on about a dozen useful, but distinct skills. For example: Finding a fruitful line of research, Problem-solving, Being an optimist, Choosing a good venue, etc. There is clearly a big win to be had when it comes to team-building: we can now look up the skills of a potential research team, and check we’ve got everything covered. Previously I thought that Linkedin endorsements were the only available resource for this, but I admit to having been reluctant to endorsing my colleagues for (say) Latex skills, in case they take it the wrong way and demand endorsements for Algorithms, or Game theory.

Thursday, March 26, 2015

Tutorial talks, and a reminder that total search problems are not NP-complete

Here is a link to recordings of invited and tutorial talks at the recent STACS 2015 conference. (Slides are available here.) These recordings include my tutorial talk on algorithmic game theory, all 3 hours of it, which may possibly be of use to writers of articles with titles like The Top Ten Mistakes you make When Giving a Technical Talk.

Possibly the commonest mistake (other than dressing badly) is to assume too much knowledge on the part of the audience. This mistake wastes the opportunity for a “big win” in which you present some fact or result that most people in the room don’t already know, but which should by rights be ingrained in their DNA. I got to do that via presenting Megiddo’s 1988 result that NP total search problems cannot be NP-complete unless NP=co-NP. To be clear, an NP total search problem is one where every instance has an easy-to-check solution, for example FACTORING, where the output is a prime factorization of an input number, or NASH, where the output is a Nash equilibrium of a given bimatrix game. This is the reason why we don’t bother to look for an NP-hardness result for NASH, and have to use an obscure-looking complexity class like PPAD.

It's possible to write a convincing proof sketch as follows. Consider what would it would mean if an NP total search problem (like FACTORING) was NP-complete. There should then be a poly-time reduction from (say) SAT to FACTORING. That is, an algorithm A that can solve SAT efficiently, provided that it has access to an efficient solver for FACTORING. Now consider what happens when pass a non-satisfiable formula Φ to A. What you end up concluding is that any run of A must constitute a (short) certificate that Φ is not satisfiable, implying NP=co-NP. A will process Φ, from time to time constructing instances of FACTORING that it can solve “for free”. Since every such instance of FACTORING must have a solution, A cannot fail for reasons of presenting the FACTORING oracle with an unsolvable instance, so must run its course. If it ends without finding a satisfying assignment, there isn’t one.

Friday, February 27, 2015

Game theory and cool-kidology

It would appear that there’s a substantial academic literature on social groupings amongst adolescents at schools. I learned about this while attending a seminar by Robert Akerlof on Social norm formation: the role of esteem. The paper considers a simplified model of social interaction between adoloscents1 in which (in a 2-player version) each player makes 3 choices: effort at 2 activities (academic achievement versus rock music), which one to value, and whether to interact with the other player. There are exogenous costs of effort and of interaction; the latter may be positive or negative. If both players choose to interact with effort at the same activity, then the weaker player grants esteem to the other player; self-esteem may also be derived from valuing the activity you really prefer. Esteem is what everyone wants. The model is somewhat reminiscent of social network models of opinion adoption, but without an underlying graph and neighbourhood structure.

The paper aims to be “the first model to capture the conflict between conformity and differentiation, which is at the heart of social interaction in many economic settings”. One key feature of the real world that the model aims to capture is the way we give up on activities where there are poor prospects of being competitive; competition for academic achievement is high amongst pupils of similar ability, but a big disparity may cause the weaker ones to switch to something else entirely. Apparently this can be used to explain why Catholic schools have lower drop-out rates; the lower cost of interaction helps (according to the equilibrium of the simultaneous-move game) pupils who are weak academically, and would be most likely to drop out. The model also predicts a “smart set”, and a “cool set” who have high self-esteem, and the middle, who have low self-esteem. That was probably you, if you read this far.

1No jokes now. I’m willing to accept that it’s possible to simplify interaction amongst adolescents.

Thursday, February 19, 2015

Not just a little local difficulty

Last week I attended a debate on a proposal for work to be carried out to improve the appearance of the Castle Mill student residences at Oxford. This article reports the outcome of the debate, and the basics of the background to it. The proposal to remove the top floor of the residences was rejected with 210 votes in favour and 536 votes against. But (as reported here) supporters of the proposal are now requiring a postal vote of all approximately 4500 academics/senior admins who are eligible to vote. I’m glad I went along to the debate, even though my opinion was unchanged; I just became slightly more convinced that it would be daft to remove the top floor of the buildings. I would encourage anyone to read the transcripts of the speeches, that appear in this supplement to the latest issue of the university’s Gazette. I couldn’t give the debate a write-up that would do it justice; it touched on interesting and fundamental issues such as the extent which someone is obliged to remedy an accidentally bad outcome, what’s to be done about the shortage of housing, and the fundamental nature and purpose of Oxford (the city, as much as the university).

The following are a few points I took away. It was pointed out that the cost of implementing the proposal is a very small fraction of the university’s turnover. The counter-argument is that nearly all of the university's turnover (including philanthropic donations) is devoted to specific projects, and is not discretionary income; the cost of work on the residences would have to be met from discretionary funds. That’s a reminder, in turn, that such discretionary funds are very valuable, and should be carefully looked after. It was also pointed out that the 38 student rooms that would be lost by the proposal represents a very small fraction of the university’s estate (and an even smaller fraction of the total amount of student housing in Oxford). The counter-argument is that it is (or ought to be) pretty hard to demolish student rooms (at a substantial cost) at a time when Oxford is the most unaffordable place in the UK. It also occurs to me that due to the inelastic nature of housing demand, it could easily be the case that a small change in student housing availability could have a disproportionate effect on the price of student housing, one that would impact on the cost of living for all Oxford students. (Although Oxford’s absentee-landlords may cite a positive externality.)

I chose the title of this article since it notes the “bigger picture”, which I felt got slightly less attention in the debate than it deserved. It is taken from a speech by one of the supporters of the proposal, who argued that if it did not go ahead, that outcome would make the university appear uncaring about its surroundings, and it would be less favourably regarded by outsiders, including potential benefactors. Against that, the same problem arises with spending a lot of money in getting rid of high-quality student rooms. Another “bigger picture” point was made that the university has to change and evolve in order to maintain its leading position in the wider academic world. The city of Oxford’s raison-d’être has got more to do with an internationally-leading university than a nationally-competitive meadow. Personally I would have liked one or two speakers to emphasise the point that at a time of worsening housing shortage at the national level, decisions to build have to be made in a more hasty manner than may be desirable in an ideal world, and we sometimes have to make certain sacrifices in order to ensure that people have roofs over their head.

As a final note, surely the view of St. Barnabas Church is no great loss. I’m quite a fan of Victorian architecture, but the main reason to preserve St. Barnabas Church is as a reminder that occasionally the Victorians got things badly wrong. That picture on the Wikipedia page speaks more eloquently to that point than I possibly could.