From a 2002 paper by Eric Friedman and David Parkes entitled, “Pricing WiFi at Starbucks – Issues in Online Mechanism Design”:
We consider the problem of designing mechanisms for online problems in which agents arrive over time and the mechanism is unaware of the agent until the agent announces her arrival. Problems of this sort are becoming extremely common particularly in a wide variety of problems involving wireless networking.
We show how the standard results of mechanism design can be modified to apply to this setting, provide conditions under which efficient and incentive compatible mechanisms exist and analyze several important online models including wireless networks and web serving.
The authors basically boil the problem of socially optimal wifi pricing down to four variables: users’ valuations of wifi, the capacity of the wifi network, and the number of potential users at a given time (which is a ratio of the arrival and departure rates). If game theory does not interest you, you can stop reading now.
It’s an interesting paper and very readable for someone who was introduced to mechanism design only recently. However, there are three weak points in the paper. The first is their (lack of a) proof for Theorem 1. The theorem states that,
For both dominant-strategy and Bayesian equilibrium, if a social choice function can be implemented online, then it can be truthfully implemented by a direct-revelation online mechanism. (p. 7)
As proof, they cite the standard proof of the Revelation Principle in the Mas-Colell et. al. (1995) textbook. Given that this result is so important to their paper, it seems that they should have spent more time explaining it. The way it is, they rely on an offline result for an online mechanism, and are thus assuming–rather than demonstrating–that there is no qualitative difference. Note that I am not arguing a difference exists, but that it should be shown to exist or not.
The second weak point is closely parallel to the first, and can be found in Theorem 2:
An online VCG mechanism is strategyproof if the online choice rule is offline optimal, in the sense that it maximizes the utilitarian value. (p. 8)
Again, they declare that the proof “is analogous to standard proofs for the strategyproofness of VCG mechanisms” and move on.
Third and finally, from a more general economic standpoint it is troubling that they ignore the fact that coffee and wifi may be complementary goods. More specifically, they state that “all customers depart at rate μ, not only the ones in service [of the wifi].” (p. 12) This is problematic because it seems that the purpose of café wifi in the first place is at least partially to get customers to stay longer and purchase more coffee.
Overall, despite these weak points the paper does a good job of showing that optimal pricing is a computationally hard problem. They suggest that a simple mechanism would be a series of (m+1)st price auctions, where m is the wifi capacity, but that this is not implementable when users are uninterruptible (even in the non-strict sense where interrupting their wifi means they might throw hot coffee on you). This explains why the optimal mechanism is not observed in the real world, which is one of the major problems for mechanism design as a field. A good paper for beginners like myself; comments welcome.
Thanks to Josh Cutler and Shahryar Minhas for their comments on a draft of this post.