Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Problem Set 4

COMP3352 Algorithmic Game Theory (2022 Spring)

1.  (30 points)  Consider an atomic selfish routing game with linear congestion functions.  In other words, each edge is associated with a congestion function ce(xe) = aexe + be  for some ae, be  ≥ 0.  However, this time we consider a version where there are two types of drivers. The first type is the same as the drivers in the original version, who experiences a congestion of ce(xe) from every edge e that it drives along, where xe is the total number of (both types of) drivers using that edge.   The second type of drivers, however, experiences only the constant part, namely be of congestion from each edge.  (E.g., they are motorcycle drivers and therefore less sensitive to congestions.) Consider a simple graph with two parallel edges from s to t.  The first edge has congestion function c1 (x1 ) = 2x1 + 1 and c2 (x2 ) = x2 + 6. Let there be 4 drivers of each type.

(a)  (15 points) What is the driving schedule that minimizes the total congestion? (b)  (15 points) Find a pure Nash equilibrium and explain what is the PoA.

2.  (30 points)  Consider the atomic selfish routing problem when the family of congestion func- tions is:

c(x) = ax + b               a ∈ {1, 2, 3, 4}, b ∈ {0, 1, 2, 3} .

These are all linear functions so the  price of anarchy upper bound applies. Is it possible to show a better PoA bound for this more restricted family of congestion functions? Why or why not? You may submit computer-aided arguments if necessary.

3.  (40 points)  Consider an all-pay auction of a single item.  That is, let there be n agents bidding for an item.  Let bi  denote the bid of agent i.  The highest bidder wins as usual. However, each agent must pay his bid regardless of whether he wins the item or not.

(a)  (5 points)  This is clearly an untruthful auction. Prove this point by giving an example in which an agent can get a better utility by lying compared with truth-telling.

(b)  (10 points)  Prove that the social welfare is equal to     iui() +    ibi  for any bids  of the agents. Here ui() is the utility of agent i.

(c)  (15 points)  Suppose i*  is the bidder with highest value.   Prove that there exists a deviation bi(/)*   of the bidder such that ui* (bi(/)* , b-i* ) ≥ vi*  − maxji*  bj .

(d)  (10 points)  Show that the PoA of an all-pay auction is at most 2, utilizing the conclu- sions of parts (b) and (c).

(e)  (optional, 0 points) Extend the PoA analysis to simultaneous all-pay auction of m items when agents’ values are unit-demand (i.e., an auction whose allocation problem can be viewed as a matching).