### 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**