Surge pricing, anyone?

One social contribution that I tentatively attribute to Uber is popularisation of the concept of surge pricing. That is, we try to call an Uber and all-too-frequently get told that we have to pay a premium at this particular point in time, due to high demand. On the other hand, recent shortages of toilet paper, paracetamol, and certain foods were not accompanied by any kind of surge pricing, and the limits imposed on how much stuff you can buy, were not so effective in keeping these goods available. At this point, things have improved, although I have not been able to buy flour recently: the shortage of flour in the supermarkets I visit seems to be chronic.

Now I appreciate the objection to charging to charging a premium to allcomers, rich and poor alike, in the context of vital food and medicine. (Although, limits on purchases can also be criticised as being unfair to a single purchaser buying for a large family, or a key worker who is short of time and doesn't want to search excessively for a desired item.) In trying to advocate surge pricing, let me turn instead to possible examples less controversial, such as hairdressers and garden centres. When these establishments are allowed to reopen, it seems reasonable that they should charge a premium (temporarily). Not only do they need the money, but it would help to control a flood of customers all causing long queues and infecting each other at close quarters. To be honest, I’m not optimistic that this will happen, since they will still worry about accusations of price-gouging, plus there’s the question of how big a premium is appropriate.

An article in the Economist highlights a related problem, which is the difficulty of measuring the rate of inflation, at a time when various goods and services (whose prices get used to measure inflation) are unavailable. Coming back to flour, it may be felt that some of it (not all!) should be sold at market price, meaning one that some people will pay, but where it stays on the shelves for a few days, at least. There is a moral case against selling goods too cheaply, which is that it becomes an attempt to hide a problem — a successful attempt, if inflation cannot be measured.

Finally, the problem discussed here touches on a defect at the heart of traditional economic theory, which is the celebrated existence of “correct” prices, unaccompanied by a means of arriving at those prices. The Algorithmic Game Theory community has quite rightly worried about price discovery and its computational obstacles. But the obstacles are also social, and status quo bias plays a big part.

Short-term prospects for UK universities

A round-up of gloomy reading material I have been taking in.

UK universities fear huge budget holes as Chinese students stay home has worrying figures about the dependence of UK universities on students from China in particular. Note the discussion about Aberdeen University towards the end of the article. had hoped to earn £50m from overseas students this year, 20% of its overall income, but that “is now likely to fall substantially, because of the restrictions and uncertainty created by coronavirus”

How can universities climb out of the coming financial abyss? considers prospects of universities closing or merging, or obtaining bridging loans from banks or government, possibly with strings attached (such as closure of certain courses seen as not very valuable). It is suggested that some prospective UK students may decide to defer going to university, although for the ones that do, “those students may have an edge in the graduate jobs in three or four years’ time, though it’s not clear how many students, if any, will be making that wholly rational calculation.”

Universities UK: state bailout required to save institutions. Some comments added by readers made the point that senior administrative salaries ought to be cut, in the context of requesting a government bailout.

Coronavirus: universities face a harsh lesson discusses universities in the UK, USA, and Australia, with emphasis on the likely loss of income from overseas students, especially from China. The ‘overexposure to the Chinese market’ story seems to be widespread.

What will higher education look like after coronavirus?
The Office for Students will need to design and put in place a multi-billion pound stabilisation fund to prevent the collapse of scores of vulnerable English universities. Access to this fund should be subject to strict non-negotiable conditions, including the phased closure of poor-quality and low-value courses under teach-out arrangements to ensure that students can complete their studies. (This seems easy to say; harder to say what’s meant by a poor-quality and low-value course. I don’t think some smirking reference to Gender Studies does the job.) More optimistic about the long-term; argues that demand for higher education will increase in developing countries. The article has an unfortunate digression into an argument that universities that attract plenty of students, should continue to expand at the expense of ones that don’t.

On leaving the EU

For someone based in the UK who works in any kind of international market, it looks reasonable to consider how his business strategy should be affected by leaving the EU. In the case of CS theory research, this perhaps runs counter to an idealised view in which all research is global, and should not be affected by squalid political considerations. The interest inherent in any specific problem or result ought to be independent of where it was studied. On a related note, it may be felt that it’s the research topic that chooses the researcher, not the researcher who chooses the topic. On the other hand, even in CS theory, ones political environment and associated social networks may have a stronger effect than we would like to acknowledge.

When I was a graduate student, Algorithms and Computational Complexity was relatively under-represented in the UK, compared with today. The UK theory community was dominated by so-called “Euro-theory”, which at the time did not seem to exhibit obvious points of contact with algorithms research. People like me had to look west for assurance that our research was of wider interest than what was apparent in our own backyard. To further justify that west-looking approach, it was clear that the USA was, in terms of research, the undisputed world leader. Then as now, it collected the lion’s share of Nobel prizes. It had industrial research labs producing leading CS theory research, such as IBM, AT&T, and NEC, while Europe had nothing similar. For me, this sowed the seeds of a defiantly Atlanticist attitude to CS theory research — appropriate for Brexit Britain, perhaps? — that the best way to pursue high-quality research was via links with colleagues in the USA.

Fast-forward to about five years ago, and my attitude had softened. The UK’s algorithms-and-complexity community steadily grew, and is much larger than it was in the early 90’s. Travel within Europe is relatively quick and cheap, with no visa issues. The European research community became a bit of a comfort-zone, while the USA’s research ethic seemed comparatively intense and high-pressure. The perennial question of “Where’s my next STOC/FOCS paper going to come from?” has always seemed less urgent in Europe.

The EU has attempted to unify Europe’s academic research activity, which is supported by diverse governments, and gives rise to diverse complaints among European colleagues. I am reminded of the “unhappy families” quote from Anna Karenina. In an attempt to give it a bit of unity, there’s some EU funding for research, concerning which we have this criticism from Andre Geim’s Nobel prize speech: “I can offer no nice words for the EU Framework programmes which, except for the European Research Council, can be praised only by Europhobes for discrediting the whole idea of an effectively working Europe.” For my part, I recently tried to get a grant from the European Research Council but they turned me down. If I were a rational agent, I should at this point be one of Geim’s Europhobes; of course in reality things are not quite so simple. But at this point I reckon the US research funding system looks like the least worst. A recent article at Athene Donald’s blog discusses the post-EU era and the idea of a DARPA-like research agency for the UK.

So, leaving the EU looks like an opportune point to dust off the above-mentioned “Atlanticist attitude”. These days China is also becoming more important. But I hope that Europe will not give up on us, but will compete strenuously with them for our attention.

A competitive foraging/gathering game

Here’s an interesting-looking game that occurred to me recently; let me know if you have seen an analysis of it or something similar. Suppose that two or more competing agents can move around in an environment in which there are a number of valuable items, and agents want to gather more items than their opponents. (One thinks of the arena in the vicinity of the Cornucopia in The Hunger Games, although a better story may be a collection of robots who can each obtain credit for performing tasks that have arisen in various locations.) How hard is it to figure out what each agent should do, and how many items she can collect? The analysis looks challenging. What follows is a few observations. A and B denote players.

It looks like a player faces an NP-hard problem, since one can present player A with a Travelling Salesman Problem of collecting n items in his vicinity before player B (initially located some distance away) has time to reach the area and collect some of these items.

One question that is not about computational difficulty is: can such a game ever have a standoff in which players stop moving, and one or more items remains uncollected? The answer seems to be yes, subject to certain modelling assumptions.

Suppose that the items are located at the vertices of a graph, and players may traverse the edges. If the graph is allowed to be directed, a standoff is easy to construct, see diagram below. All edges take 1 time unit to traverse. Suppose both players A and B start at the central vertex, and there are items of equal value 1 on each of the other vertices. If player A moves towards the top vertex, player B will move towards the bottom left vertex just downstream (according to the edge direction), and will be able to collect 2 out of the 3 items, exploiting the directedness of the edges. Hence it looks like both players will be reluctant to leave the central vertex. (Especially if we assume that the aim is to get more items than the opponent, as opposed to maximising the number of items collected.)

Can we do something similar for undirected graphs? The following example is inspired by a secure protocol for bilateral trade of physical goods, which I used once or twice as a young child. The parties to the transaction place the items on the ground a few metres apart, and walk towards each other, passing at the halfway point. Assuming they want the exchange to go ahead, they continue towards their preferred item, noting that neither trader can grab both items, subject to the reasonable assumption that neither can run 3 times as fast as the other.

The figure below shows an undirected graph where player A is very close to an item worth  1.5 (we can assume he grabs it immediately) while player B is distance 1 from the remaining two items of value 1. Player A is distance 1.5 from each of these 2 remaining items.

Assuming that the aim of the game is to get the lion’s share of the items, A needs one more item, and B needs both remaining items. If A moves towards the top item, then B can move towards that same item, get there first and then go back for the bottom item. If players can move freely (and reverse directions) on edges, B can stop A from getting both, by staying slightly closer to whichever item A is closest to. However, if B goes ahead and collects (say) the top item, then A can go for the bottom one, as soon as B is close to the top one. Result: an impasse, especially if you assume that such an impasse means the game is tied and the overall prize is split.

Notice that you do not get this deadlock if players can move freely in the plane: in that version, A can move directly towards B, and if B approaches (say) the top item then A should approach the bottom one. So A wins with no impasse. It would be interesting to know whether an impasse can result in this setting of free movement in the plane.

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!

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.

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

ACM-SIAM Algorithmic Principles of Computer Systems (APoCS20)

https://www.siam.org/Conferences/CM/Main/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

Submissions:

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:

Databases

Compilers

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