A refinement of approximate correlated equilibrium

One reason to prefer correlated equilibrium (CE) over Nash equilibrium (NE) is that correlated equilibrium is easier to compute. We have various PPAD/PLS-hardness results for exact Nash equilibria (NE), and it is possible that approximate Nash equilibria may also be similarly ‘hard’ to compute. In contrast, approximate correlated equilibria (CE) are not just easy to compute, but are obtainable by simple ‘learning dynamics’ type algorithms. The price you pay is that it’s a much weaker solution concept: every Nash equilibrium is a correlated equilibrium, and there may be CEs that are far from any NEs. For example some congestion games have CEs with social cost much higher than the worst NE. Some games have unrealistic Nash equilibria that motivate the study of various refinements of NE, restrictions that hopefully weed out some or all of the unnatural ones.

Given that CE is a relaxation of NE, it looks like there is even more motivation to impose restrictions on them so as to get rid of unnatural equilibria. For CE, I reckon that any such restriction should try to chip away at the set of approximate correlated equilibria, via some mathematical restriction that gets rid of undesirable ones while preserving the property that the remaining solutions are still easy to find, preferably via simple algorithms. The following definition is derived from the notion of approximate well-supported Nash equilibrium, but the version for correlated equilibrium doesn’t seem to have been considered previously. Here I just give the definition and a motivating example, and leave it as a guess that the restriction makes it not too much harder to compute.

In a well-supported ε-NE, it is disallowed for a player to allocate positive probability to a pure strategy whose payoff is worse than the best response by more than ε. (In contrast, an ε-NE that is not well-supported allows a player to play a really bad response, provided that he does so with such low probability that his average payoff does not fall short of the best response by more than ε. For bimatrix games with payoffs in [0,1], it is currently known how to — in poly time — compute ε-NE for ε just over ⅓, but for well-supported ε-NE, it is only know how to do this for ε slightly less than ⅔.

Applying that “well-supported” principle to ε-correlated equilibria, it corresponds to a requirement that when a player observes his action (a sample of his marginal distribution derived from the approximate CE), he does not gain more than ε by switching to some other pure strategy. Here’s an example of how it makes a difference. We start with a trivial example and then make it more interesting. The trivial example has one player with actions {0,1}, who gets paid 0 to play 0, and 1 to play 1. In a standard ε-approximate CE, he can play 0 with probability up to ε, but if the approximate CE should be well-supported, he must play 1 with probability 1. To make the example more interesting, suppose you have a sequence of players 1,2,...,n, all with 2 pure-strategies 0 and 1, where player 1 is like the original player in the trivial 1-player game, and player i > 1 gets paid 1 to copy player i−1 and 0 to play the opposite strategy of player i−1. In a well-supported ε-CE, all players must play 1 with probability 1. By contrast, in a standard ε-CE, the probability that player i+1 plays 1, may differ by up to ε from the corresponding probability for player i. Consequently, the probability that player i plays 1, may fluctuate arbitrarily between 0 and 1 as i increases, subject to the constraint that it changes by at most ε each time i increases by 1. Thus the “well-supported” constraint seems to rule out a large number of outcomes. Whether you think this “well-supported” constraint is a good one, depends on whether you think these outcomes really ought to be ruled out...

end of lectures?

There’s an interesting discussion in an article in the Guardian about the possible demise of traditional lectures at universities; it’s inspired by a speech by Jimmy Wales reported in more detail here (Jimmy Wales: Boring university lectures ‘are doomed’). Any academic must be tempted to have an opinion on this topic. One thing that I haven’t seen come up in this discussion is the freedom the lecturer gets in an unrecorded lecture to take liberties with the subject-matter; for example to be a bit imprecise when discussing a mathematical topic, in a way that helps the audience’s intuition, but involves saying something that is not strictly correct. With a textbook, or recorded lecture, there is pressure to play it safe and avoid the possibly helpful imprecision.

Lectures are often criticised for not being very interactive (although, these days, any reasonable lecturer attempts to be interactive). When a lecture fails to be interactive, it is noted that you might as well watch a video of the lecture (or better yet, some version of it delivered by a great lecturer). What the video loses, however, is the unrealised possibility of interaction: the possibility that an awkward question may be asked makes it different from a setting where there is no possibility that an awkward question may be asked. At least that may be why I’ve found recorded lectures to be less interesting than the live version, other things being equal.

Finally, the prophets of lecture-doom need to explain why theatres have not been completely wiped out by movies, and indeed why lectures themselves have not already been replaced by recorded ones (after all, the technology has been around for a while).

A real-world path auction (sort of)

Path auctions have received quite a lot of attention in the Algorithmic Game Theory community. The general scenario envisages a single buyer who wants to procure a path through a network, and has to buy a set of links that contains an acceptable path. The links are available for sale from multiple agents; a common special case of interest has each link belonging to a single agent. It’s a line of work that has led to some interesting results and techniques; for example I like the “cheap labor can be expensive” paradox of this paper by Chen and Karlin, which says that sometimes, if additional (and cheap) links/sellers are added to the network, it may actually drive up the cost for the buyer.

Now the standard “practical” motivation for path auctions that is given in the AGT literature, usually refers to a requirement to route network traffic (either data over a computer network, or alternatively, road traffic). However I have not seen any concrete examples of such path auctions actually taking place. But here’s an auction that actually takes place, in a context that is very similar conceptually to a path auction. Adapting Auctions for the Provision of Ecosystem Services at the Landscape Scale considers payments for Ecosystems Services (ES) in which landowners in Australia are paid to promote conservation goals on their land. Quoting the paper:

Most ES auctions adopt a sealed bid, discriminatory price mechanism, in which successful landholders are paid their bid price (e.g. Stoneham et al., 2003; Windle et al., 2009). A rational landholder will request at least the opportunity cost of providing the ES; they can ask for more, but the higher their price the less likely they are to have their bid accepted.

Now, the environmental gain for ES is greater if parcels of land are adjacent, since the protected land then provides wildlife corridors, and the like. The greater value of certain combinations of land parcels has influenced the mechanism used to set the prices. The mechanism in use seems to use a number of iterations, in which bids are received, a set of winners is announced, and based on that (provisional) outcome, sellers get the opportunity to change their bids. Another quote:

A critical problem in corridor formation is individuals not participating, or holding out for excessively high prices. In this form of iterated auction there will be greater opportunity for participants to identify and work around such hold-outs. Where there are different ways of forming a corridor across a landscape, corridors can evolve over multiple rounds according to the bidding behaviour of individual landholders.

The paper reports on lab-based experiments aimed at optimizing parameters of the kind of mechanism in use, in particular the number of rounds of an iterated auction. Another paper I found that may be of interest is An Experimental Study of Iterative Auctions for Ecosystem Services Delivery, which experiments with an iterative descending-price mechanism.

Elsevier Editorial System

Last time I did a review for an Elsevier journal, I was prompted to set up an account on the Elsevier Editorial System, which aggregated all (or most) of earlier reviews I previously did for various Elsevier journals. From now on, it would seem that future reviews for Elsevier journals will get added to a bulging portfolio. While my general understanding is that the main reward for reviewing papers will occur in the afterlife,  there’s something rather satisfying about seeing this collection in one place. (And I never know there were so many Elsevier journals, he adds, naively...).

If there is indeed any value to having a centralised record of (anonymous) reviews, it might provide a new justification for journals to belong to large commercial publishers. On the other hand, review requests lack the personal touch that they used to have until about 10 years ago. And there’s presumably a risk of their database getting hacked, and reviews getting de-anonymised.

On another topic, here is a list of top 30 Computer Science blogs. I am not sure I deserve to be listed there, but anyway, some of the others look interesting, check them out. Here is a similar list that I was notified of at about the same time.

decem quid pro quo?

I received from a colleague, an email bearing the above subject line. It reads (slightly edited):

The Bank of England is considering putting Alan Turing (no need to explain who he is) on the next £10 note. An online petition has been created to collect signatures from people who would like to see this.

So far they have received ~26,000 signatures and it needs over 100,000 signatures before it will be considered by the design committee.

The petition is here:
https://submissions.epetitions.direct.gov.uk/petitions/31659

Personally, I would love to see this come into fruition and I am sure many of you would too.

If you do (and you’re British) I would appreciate if you could take the time to sign the petition.

Let’s hope that this highly influential computer scientist finally gets the wide-reaching recognition he deserves.

I am happy to advertise this!

Ziggie and Zack

A couple of weeks ago I went to a kickoff meeting of COST action IC1215 on computational social choice, and picked up a copy of the most colourful publication on display, “Ziggie and Zack: Your Lightning Heroes” (PDF), a final publication of an earlier COST action on the Physics of Lightning Flash and its Effects. I am now hopeful that the new COST action will produce a similar output featuring the hazards of voting paradoxes and computationally intractable solution concepts.

WINE update

WINE 2012 (held here in Liverpool, UK) came to a successful conclusion yesterday; I should again thank the local organisers. On Tuesday we had a short business meeting to discuss renaming WINE from “workshop” to “conference”, which is a topic I was asked to raise by colleagues a few weeks ago. Since WINE is a conference in all but name, there was a clear consensus to do this, but retaining the acronym. The favoured name that retains the acronym is “Web Interaction and Network Economics”.

Here is a link to the Google Research blog article on WINE 2012.

We also discussed closer links with ACM, with David Parkes (chair of ACM SIGecom) suggesting some options. Currently WINE just has “in association” status with SIGecom. Being an ACM conference would represent some kind of badge of approval, and would provide some organisational support, such as links to ACM digital library and accounting/insurance/negotiation with venues. Being an ACM conference would cost money, but they would take the loss if an occurrence of WINE lost money, so it is a kind of insurance. ACM could alternatively share this status with another non-profit partner, e.g. maybe EATCS.

WINE 2013 will be at Harvard, and for WINE 2014 we had a very nice presentation by Tie-Yan Liu (at MSR Asia), for hosting WINE 2014 at either Beijing or Hong Kong (which one may depend on whether funding is forthcoming for a co-located winter school in Hong Kong). Finally, Martin Hoefer gave a presentation advertising SAGT 2013 to be held in Aachen, Germany (in the SuperC Building) (in October 2013).