Congestion games, optimal transport and basic algorithmic game theory

These are some notes from my time teaching myself some algorithmic game theory, since it came up in my research and is something I knew very little about at the time. In particular, I'm interested in the state of the art in modelling traffic flow in graph-theoretic terms. Here, I write down my internal intuition for basic ideas in mechanism design, selfish routing, congestion games, as well as survey one or two important papers in the field. For the first three sections here, we work through some parts of Tim Roughgarden's Twenty Lectures on Algorithmic Game Theory, and accordingly, my solutions to the problem sets are given alongside some of these ramblings.

Core ideas and introduction to mechanism design

Solutions to (selected) exercises.

1. Give at least two suggestions for how to modify the Olympic badminton tournament format to reduce or eliminate the incentive for teams to intentionally lose a match.

Solution. Either randomize the knockout match pairings to eliminate the incentive to lose -- so that the outcome of the final match between first and second seed in a group no longer determines anything -- or, better yet, incentivize teams to win by allowing the first seed in the group to choose who they play in the next round of the knockout phase.

2. Clarify how the movie "A Beautiful Mind" misrepresents what a Nash Equilibrium is.

Solution. Ironically, the movie has it exactly wrong. It describes a scenario where 5 girls walk into a bar where John Nash and 3 of his friends are. There are four brunettes, and a blonde. The men are all attracted to the blonde more than the brunettes, but care above all else with having someone at the end of the day, even if it's one of the brunettes. Nash -- in the movie -- posits that if they all go for the blonde, she rejects them all, and then so do her friends (the brunettes) since they don't want to be second choice. Instead, he proposes they go for the brunettes -- one each -- from the outset, to maximize "social surplus," in economics-lingo, and have someone at the end of it all.

In reality, Nash Equilibria (NE) describe scenarios where no agent has incentive to deviate. In this setup, if all your competitors are going for a brunette, you do have incentive to deviate/change your behavior (pursue the blonde), since then you're likely to get her since there is no competition. This is an example of a situation that is categorically not a Nash Equilibrium -- as many movie critics (nerds) are quick to point out.

3. Prove that there is a unique (mixed-strategy) Nash equilibrium in the Rock-Paper-Scissors game described in class.

Solution. We offer a constructive proof: consider a uniform randomization over the possible actions, with probability \( \frac{1}{3} \) each. Call this strategy \(U\). To see this is a Nash Equilibrium just observe that the expected value of perturbing any of the probabilities is zero, by a symmetry argument. It remains to show that this Nash equilibrium is unique. Therefore, fix your opponents' strategies, and assume there exists some strategy \( U' \neq U\) that would yield a higher probability of winning on your behalf. We will derive a contradiction, implying that no such \( U'\) can exist. To see this, observe that since \(U\) is the unique strategy that places equal probability on all three actions "rock-paper-scissors." Therefore, strategy \(U'\) must have an action \(a \in \{ R, P, S\}\) for which the probability of being played if greater than \( \frac{1}{3}\).

Then see that there exists an opposing action \( \lnot a \) (eg. rock for scissors) that the opponent can play with probability one once they identify you are playing \( a\) with high probabilitiy. In this scenario, they win in expectation, and so have incentive to shift their strategy towards doing that, and therefore than can be no equilibrium. Then see that in the case you play symmetrically randomly using strategy \(U\), there can be no such opposing action \( \lnot a \), and thus no incentive for the opposition to deviate, establishing the Nash equilibrium we found at the beginning, as required.

5. Consider a single-item auction with at least three bidders. Prove that awarding the item to the highest bidder, at a price equal to the third-highest bid, yields an auction that is not dominant-strategy incentive compatible (DSIC).

Solution. It suffices to construct a scenario in which a bidder has incentive (or is indifferent) to lie -- or at least not be truthful about their true preference. Let the two highest bids for a good so far be \( B_1 = 200, B_2 = 10\), and let the private valuation of an agent considering bidding be \( v = 100 \). Assume quasilinear utility, as is standard. The agent knows bidding \( b > 200\) will get him the item for \( $10\), resulting in \( 100 - 10 = 90\) utils, and he therefore does so. Since \( b > v \) strictly, he gains positive utility from lying, and therefore a third-item auction does not always incentive agents to set their bids equal to their valuations, as required.

6. Suppose there are \( k \) identical copies of a good and \( n>k \) bidders. Suppose also that each bidder can receive at most one good. What is the analog of the second-price auction? Prove that your auction is DSIC.

Solution.

7. Suppose you want to hire a contractor to perform some task, like remodeling a house. Each contractor has a private cost for performing the task. Give an analog of the Vickrey auction in which contractors report their costs and the auction chooses a contractor and a payment. Truthful reporting should be a dominant strategy in your auction and, assuming truthful bids, your auction should select the contractor with the smallest private cost.

Solution.

8. Recall the sponsored search setting, in which bidder i has a valuation vi per click. There are k slots with click-through-rates (CTRs) α1 ≥ α2 ≥ · · · ≥ αk. Recall that the social surplus of an assignment of bidders to slots is Pn i=1 vixi, where xi equals the CTR of the slot to which i is assigned (or 0 if bidder i is not assigned to any slot). Prove that the social surplus is maximized by assigning the bidder with the jth highest valuation to the jth slot for j = 1, 2, . . . , k

Solution.

Selfish routing, PoA, network over-provisioning

Equilibrium heirarchies and smooth games

An introduction to congestion games

The Cell Transmission Model

Search Frictions and Efficiency in Decentralized Transport Markets

Next steps