Notes on Roughgarden AGT Lecture - 1

Does the participants' goal align with the designer goal?

When you are designing a system, like a tournament, or like an auction, or like a computer network, and you have participants that are strategic, the rules of the game matter. You cannot expect participants to behave in a way other than in their own interest. That is an unreasonable assumption as a designer. You must account for strategic behavior, and if you don't do it carefully, you will get unexpected, and often undesirable, consequences.

Some examples

A summary of the badminton example

The committee's initial pairing mechanism makes sense: to pair the winner of a group with the second place of another group.

Intuitively, this rule incentivizes teams to win, as one would thought that the second place of any group is always weaker than the first place. Nevertheless, this intuition is proven wrong when in one of the groups, a much stronger team lost to a weaker team, resulted in the second place and the first place for the two teams in that group, respectively.

Braess’s Paradox

Braess’s Paradox. Source: Roughgarden Lecture Note 1

Consider pure Nash, and the objective value of a profile being the averaged commute time over all players. Note that in the augmented network, the profile where everyone takes the route $(s, v, w, t)$ is an (and the only) equilibrium; the objective value is $2$ .

On the other hand, in the augmented network, an optimal profile yields an objective value of $3/2$ , giving a PoA of $4/3$ . Interestingly, such a profile with object $3/2$ is a Nash (and the only Nash) in the original network, thereby a paradox.