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

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.

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.