Tuesday, June 04, 2019

plans for WINE conferences

Update on the annual Conference on Web and Internet Economics (I am on the steering committee).

WINE 2019 (the 15th) will be at Columbia University, December 10-12. We could not avoid the clash with NeurIPS, due to Columbia’s exam schedule. Submission deadline is July 15th.

The plan is for WINE 2020 to take place at Peking University, following the tradition to rotate between Europe, USA, and Asia.

WINE 2021 is under discussion; one idea it to hold it in Addis Ababa, Ethiopia, which is not as novel as it may seem at first sight, it would be following ICLR 2020 (see this link (noting the visa issues) and others). The rationale is that Africa has a burgeoning AI community including people who are interested in algorithmic game theory, and for them, Ethiopia is an easy destination (administratively, in particular). WINE 2018 (at Oxford, UK) had (I think) 5 African participants, and about 10 more would have liked to come but were denied visas. These participants brought home to me the point that there is this developing AI community in Africa. At WINE 2018, Eric Sodomka (from Facebook) gave a well-received presentation on the idea of holding a future WINE in Africa. Are there other places in Africa we should be thinking of? I welcome feedback and comments!

Thursday, May 30, 2019

Augar review

This note considers the Augar review from the perspective of a prospective student, as opposed to a typical university (Wonkhe does not fill me with enthusiasm on that aspect).

Moneysavingexpert gives a fairly helpful list of the main points; see the bold-face subtitles. It goes wrong in one place with “Student loans should be renamed a ‘student contribution system’ … Student loans are a misnomer. So it’s with relief that the Augar report notes our call to change the name…” However, when an expense incurs interest and an obligation on an individual to repay it, there’s no getting away from the fact that it’s a loan (and incurs a debt), and in a minor victory for plain English, the article goes on to use the word loan, and not ‘student contribution system’.

An earlier BBC article Rich students save by paying fees up front notes that under the current regime, 10% of students pay tuition fees upfront (or at least, their parents do). I agree with the criticism of the current regime, as quoted as in the article. When I first read that Augar proposes the fees to be reduced, but you’re on the hook for debt repayment for an additional 10 years (as noted in the moneysavingexpert article: “The loan will wipe after 40, not 30, years – substantially increasing the total repayment for many”) it looked to me like that added up to an even stronger incentive to pay upfront. But wait... there’s also a proposed cap of loan plus 20% (adjusted for inflation) that you have to repay, that makes the set-up more benign. It means that with a partial repayment, you’re chipping away at something that cannot grow without limit. That mitigates a deeply disagreeable feature of the present system, namely the uncertainty and lack of control on how much someone will repay.

My guess: affluent parents will continue to pay the fees upfront, even if the cost to the family for not doing so is at most an additional 20%. It’s basically an attractive mechanism for bequeathing money. There’s also the issue of how such a bequest changes the behaviour the student after they graduate (an aspect of up-front payment that has not received much attention) — arguably if a graduate doesn’t face a tax bill when his income exceeds some amount, he’s more likely to pursue a well-paid job.

Friday, April 12, 2019

New conference: ACM-SIAM Algorithmic Principles of Computer Systems (APoCS20)

ACM-SIAM Algorithmic Principles of Computer Systems (APoCS20)

January 8, 2020
Hilton Salt Lake City Center, Salt Lake City, Utah, USA
Colocated with SODA, SOSA, and Alenex

The First ACM-SIAM APoCS is sponsored by SIAM SIAG/ACDA and ACM SIGACT.

Important Dates:

August 9: Abstract Submission and Paper Registration Deadline
August 16: Full Paper Deadline
October 4: Decision Announcement

Program Chair:

Bruce Maggs, Duke University and Akamai Technologies


Contributed papers are sought in all areas of algorithms and architectures that offer insight into the performance and design of computer systems.  Topics of interest include, but are not limited to algorithms and data structures for:

Emerging Architectures
Energy Efficient Computing
High-performance Computing
Management of Massive Data
Networks, including Mobile, Ad-Hoc and Sensor Networks
Operating Systems
Parallel and Distributed Systems
Storage Systems

A submission must report original research that has not previously or is not concurrently being published. Manuscripts must not exceed twelve (12) single-spaced double-column pages, in addition the bibliography and any pages containing only figures.  Submission must be self-contained, and any extra details may be submitted in a clearly marked appendix. 

Steering Committee:

Michael Bender
Guy Blelloch
Jennifer Chayes
Martin Farach-Colton (Chair)
Charles Leiserson
Don Porter
Jennifer Rexford
Margo Seltzer

Wednesday, March 27, 2019

Meaningful votes

In the unlikely event that we get a second referendum on Brexit, here’s how it ought to be done: Arrange all the alternatives in a line in order of “hardness” of Brexit. In may be felt that Remain should not be an option, in which case we have Norway plus (a.k.a. Common Market 2.0) at one end, and no-deal at the other. Every voter chooses their favourite option from the list. The winning option is chosen to be the one for which at least half the voters prefer a harder Brexit, and at least half favour a softer Brexit. The claim that this system is truthful, is based on the presumed single-peaked-ness of preferences: every voter has a favourite option, and their support for the others goes down, the further away you get from the favoured option.

Of course, the only thing less likely than a second referendum is the adoption of an eminently sensible approach such as the one above, and the interesting question is, why it would not be used. One objection I can think of, goes as follows: suppose there are 3 alternatives offered, say Norway plus, Theresa May’s deal, and no-deal. Suppose that 20 million voters support Norway plus, another 20 million support no-deal, and one voter supports May’s deal. In that case, May’s deal wins, and someone would complain it’s (a lot) less popular than one of the others (probably the one the complainant supported). In reality, this result should have everyone — on both sides — celebrating the fact that whatever outcome they liked least has just been narrowly averted. A better objection is that some people would prefer a principled in-or-out result, and either extreme is preferable to some sort of fudge. (I admit, I recently heard that view sincerely expressed.) So, for them the vote is not truthful, but there are not many people like that, and they are free to vote (strategically) for whatever extreme they prefer. A third objection, implicit in most objections to electoral reform, states that voters are too stupid to understand anything other than plurality, or “first past the post”.

If the above system were used in Parliament, May’s deal would probably win, unless MPs were allowed to vote anonymously, in which case Norway Plus would probably win.

I checked the paper Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical since the point about voting is analogous to the observation that no-one uses VCG. The 13 reasons are mostly not applicable, or only weakly applicable, to the above election. It is true that there are other weak equilibria besides truth-telling, but it seems unlikely that someone would vote against his preference simply because he’s unlikely to swing the outcome.

The effort we put into studying voting systems is justified by the following Milton Friedman quote:
Only a crisis - actual or perceived - produces real change. When that crisis occurs, the actions that are taken depend on the ideas that are lying around. That, I believe, is our basic function: to develop alternatives to existing policies, to keep them alive and available until the politically impossible becomes the politically inevitable.

Monday, March 18, 2019

The will of the people

At one point in Iain Banks’ novel The Wasp Factory, the main character (a troubled teenager called Frank) makes the following observation:
Often I’ve thought of myself as a state; a country or, at the very least, a city.
He then compares his moods and thought processes to political moods that countries go through:
…For example, there has always been a part of me which has felt guilty about killing Blyth, Paul and Esmerelda. … But I liken it to an opposition party in a parliament, or a critical press; acting as a conscience and a brake, but not in power and unlikely to assume it.
Frank is modelling a single self-contained agent (himself) as the embodiment of many separate agents. It is common in literature for someone to have a struggle between, say, the admirable and the less admirable parts of his nature, but the above is the best example I can recall of this kind of modelling.

Usually we do the opposite, trying to represent many agents as a single one. In the context of Brexit, that approach has been stretched to breaking-point. The phrase “the will of the people” attempts to conflate the electorate (a multitude of agents) into a self-contained purposive entity. Is Brexit the will of the people? Yes, in the same sense that getting a hung parliament is the will of the people. The people seem to want to make life difficult for themselves. UK politicians and commentators have discussed negotiating Brexit with the European Union as if the EU is a self-contained purposive agent. This has led to the unfortunate idea that the EU may want to punish the UK for leaving, in order to discourage other states from leaving. It views the EU as a single entity motivated by the desire to survive and grow, and assumes that it will take actions that run counter to the goodwill of EU leaders. Likewise, we have recently heard a great deal about how Parliament has said what it doesn’t want, but not what it wants. If Parliament is modelled as a single agent, then it ought to want something, but as soon as we acknowledge that it’s not a single agent, there is no particular reason to suppose that there is something that it wants. Given, say, three alternatives, there could perfectly well be a Condorcet cycle.

Returning to Frank, it may be useful to model an individual as a multitude of internal agents. In economics, it could be a new an interesting way to model individual irrationality, which is a perennial challenge that has been taken up in a rather patchy way, and deserves more attention. Finally it may even constitute a way to model emotions: in Frank’s case it is guilt that is represented this way.

Tuesday, November 06, 2018

What do you know that deserves more publicity?

I was talking with a journalist yesterday - not an interview, just an informal conversation - and he asked me the question: What stories in Computer Science are not getting enough attention? And my immediate reaction was: great question! although I suppose for journalists, asking great questions is what they’re supposed to do. And, unaccustomed to being pestered by members of the fourth estate, I did not have a slick and ready answer, but feel like I should have done. It’s reasonable enough to expect a university professor may have insider information on some topic that s/he reckons should be more publicised. Maybe CS theory is not such a rich source of such professors as most other fields.

In coming up with an answer, I would impose the following rules. One’s own research should be off-limits, due to personal bias. Also, you should not argue that some area of CS (presumably AI/big data) is getting too much attention, and other unspecified stories are getting overlooked in consequence. The challenge is to make a positive claim in favour of some specific research sub-field. I thought briefly of exposing the manifold failings of the research funding system, but decided that the story should be CS-specific, not one that many researchers could have come up with.

With hindsight, I would point to the topic of fairness in AI, which has received some mass-media coverage (example) but most people outside of CS/AI still don’t know that it is increasingly viewed as important. It has attracted a fair (?) amount of interest from the TCS community, i.e. among computer scientists who have good taste. Crucially, it is easy to motivate to someone who is a complete outsider. (I have been taking an interest but it’s not currently my own research field, just a related one.) To conclude, I mentioned above that CS theory is maybe not such a rich source of topics that deserve more publicity, but let me know if there are any I should have thought of.

Tuesday, April 17, 2018

STOC child care

I received a request to call attention to the following, but will refrain from sharing it with the Theory of Computing blog aggregator since others have already done so (for example here).

In a challenge to my long-standing view of academic life as a hybrid of Herman Hesse’s The Glass Bead Game and Paul ErdÅ‘s’ itinerant-scholar lifestyle, STOC 2018 will be the first STOC to provide subsidised, pooled childcare. (OK, this is not completely new. Dagstuhl has had this facility for some years, and the earliest example I can recall is the year 2000 British Colloquium on Theoretical Computer Science, although I don’t recall it being subsidised.)

On a related note, I was separately circulated an email advertising a TCS women event at STOC. Features include a panel of senior female researchers, a women’s lunch, and a research rump session. They have also secured funding to sponsor travel scholarships for women to attend STOC (see the web site); the organizers would like to see increase in women participation from outside of USA.