# 数学作业代写|game theory Assignment 2

Problem 1.

Suppose a subset $S$ of the bidders in a second-price single-item auction decide to collude, meaning that they submit their bids in a coordinated way to maximize the sum of their utilities. Assume that bidders outside of $S$ bid truthfully. Prove necessary and sufficient conditions on the set $S$ such that the bidders of $S$ can increase their combined utility via non-truthful bidding.

Problem 2.

Use the “payment difference sandwich” in (3.4) to prove that if an allocation rule is not monotone, then it is not implementable.

Problem 3.

Consider the following extension of the sponsored search setting described in Section 2.6. Each bidder $i$ now has a publicly known quality $\beta_i$, in addition to a private valuation $v_i$ per click. As usual, each slot $j$ has a CTR $\alpha_j$, and $\alpha_1 \geq \alpha_2 \cdots \geq \alpha_k$. We assume that if bidder $i$ is placed in slot $j$, then the probability of a click is $\beta_i \alpha_j$. Thus bidder $i$ derives value $v_i \beta_i \alpha_j$ from the $j$ th slot.
Describe the welfare-maximizing allocation rule in this generalized sponsored search setting. Prove that this rule is monotone. Give an explicit formula for the per-click payment of each bidder that extends this allocation rule to a DSIC mechanism.

Problem 4.

Problem 3.1 Recall our model of sponsored search auctions (Section 2.6): there are $k$ slots, the $j$ th slot has a click-through rate
(CTR) of $\alpha_j$ (nonincreasing in $j$ ), and the utility of bidder $i$ in slot $j$ is $\alpha_j\left(v_i-p_j\right)$, where $v_i$ is the (private) value-per-click of the bidder and $p_j$ is the price charged per-click in slot $j$. The Generalized Second-Price (GSP) auction is defined as follows:
The Generalized Second Price (GSP) Auction

1. Rank advertisers from highest to lowest bid; assume without loss of generality that $b_1 \geq b_2 \geq \cdots \geq b_n$.
2. For $i=1,2, \ldots, k$, assign the $i$ th bidder to the $i$ slot.
3. For $i=1,2, \ldots, k$, charge the $i$ th bidder a price of $b_{i+1}$ per click.
The following subproblems show that the GSP auction always has a canonical equilibrium that is equivalent to the truthful outcome in the corresponding DSIC sponsored search auction.
(a) Prove that for every $k \geq 2$ and sequence $\alpha_1 \geq \cdots \geq \alpha_k>0$ of CTRs, the GSP auction is not DSIC.
(b) (H) Fix CTRs for slots and values-per-click for bidders. We can assume that $k=n$ by adding dummy slots with zero CTR (if $k$ $n)$. A bid profile $\mathbf{b}$ is an equilibrium of GSP if no bidder can increase her utility by unilaterally changing her bid. Verify that this condition translates to the following inequalities, under our standing assumption that $b_1 \geq b_2 \geq \cdots \geq b_n$ : for every $i$ and higher slot $j<i$

$$\alpha_i\left(v_i-b_{i+1}\right) \geq \alpha_j\left(v_i-b_j\right)$$
and for every lower slot $j>i$,
$$\alpha_i\left(v_i-b_{i+1}\right) \geq \alpha_j\left(v_i-b_{j+1}\right) .$$
(c) A bid profile b with $b_1 \geq \cdots \geq b_n$ is envy-free if for every bidder $i$ and slot $j \neq i$,
$$\alpha_i\left(v_i-b_{i+1}\right) \geq \alpha_j\left(v_i-b_{j+1}\right) .$$
Verify that every envy-free bid profile is an equilibrium. ${ }^4$
(d) (H) A bid profile is locally envy-free if the inequality (3.9) holds for every pair of adjacent slots – for every $i$ and $j \in{i-1, i+1}$. By definition, an envy-free bid profile is also locally envy-free. Prove that, for every set of strictly decreasing CTRs, every locally envy-free bid profile is also envy-free.
(e) (H) Prove that, for every set of values-per-click and strictly decreasing CTRs, there is an equilibrium of the GSP auction in which the assignments of bidders to slots and all payments-perclick equal those in the truthful outcome of the corresponding DSIC sponsored search auction.
(f) Prove that the equilibrium in (e) is the lowest-revenue envy-free bid profile.

Comments on Problem 3.1: This is an important example of a non DSIC mechanism. Your time is well spent understanding this problem!
(part b) The condition for a bid profile being in equilibrium is that you don’t improve your utility if you unilaterally (i.e. only you) change your bid.
(part c) The condition for a bid profile being envy-free is that you don’t improve your utility if you exchange bids with another person. You show that a bid profile being envy-free is a stronger condition than a bid profile being in equilibrium.
(part d) As the hint in the back of the book suggests, you will need the fact that, in a GSP Auction, if a bid profile is locally envy-free bid with strictly decreasing CTRs, then $v_1 \geq v_2 \geq \cdots \geq v_n$. To show this start with the following two locally envy-free equations:
$$\begin{gathered} \alpha_i\left(v_i-b_{i+1}\right) \geq \alpha_{i+1}\left(v_i-b_{i+2}\right) \ \alpha_{i+1}\left(v_{i+1}-b_{i+2}\right) \geq \alpha_i\left(v_{i+1}-b_{i+1}\right) . \end{gathered}$$
Adding these inequalities there is a nice cancellation and you end up with
$$\left(\alpha_i-\alpha_{i+1}\right) v_i \geq\left(\alpha_i-\alpha_{i+1}\right) v_{i+1}$$
which implies that $v_i \geq v_{i+1}$.
Hint: To prove part (d) notice that
$$\alpha_i\left(v_i-b_{i+1}\right) \geq \alpha_{i+1}\left(v_i-b_{i+2}\right) \Longrightarrow \alpha_i\left(v_{i-1}-b_{i+1}\right) \geq \alpha_{i+1}\left(v_{i-1}-b_{i+2}\right) .$$
(part e) To simplify the notation lets assume that there is one more bidder than slots, (i.e. $n=k+1$ ). It is not hard to generalize but don’t worry about this. You need to do two things: (1) find a bid profile for a GSP auction such that the payments $\left(b_2, b_3, \ldots, b_{k+1}, 0\right)$ match that of the corresponding Sponsored Search (SS) auction and (2) show that this bid profile is locally envy-free.

Regarding (1) notice that $b_1$ isn’t relevant for GSP and SS pricing to be the same (you do need however that $\left.b_1 \geq b_2\right)$. Having matching payments means that $\left(b_2, b_3, \ldots, b_k, b_{k+1}, 0\right)$ equals $\left(P_1 / \alpha_1, P_2 / \alpha_2, \ldots, P_k / \alpha_k\right)$
where $P_i / \alpha_i$ is the payment per click for the $i t h$ slot in a SS auction.
Regarding (2) Show that for $1<i \leq n$, we have the recursive formula
$$b_i=\frac{\alpha_i}{\alpha_{i-1}} b_{i+1}+v_i\left(1-\frac{\alpha_i}{\alpha_{i-1}}\right)$$
where $b_{k+1}=v_k$. Recognize that this formula is equivalent to the locally envy-free equality
$$\alpha_i\left(v_i-b_{i+1}\right)=\alpha_{i-1}\left(v_i-b_i\right) .$$
(part f) Given the envy-free bid profile in part (d), show that the price is as low as possible among all locally envy-free profiles. Note that a locally envy-free profile satisfies the recursive formula
$$b_i \geq \frac{\alpha_i}{\alpha_{i-1}} b_{i+1}+v_i\left(1-\frac{\alpha_i}{\alpha_{i-1}}\right) .$$

Problem 5.

Exercise 4.1 Consider an arbitrary single-parameter environment, with feasible set $X$. Prove that the welfare-maximizing allocation rule
$$\mathbf{x}(\mathbf{b})=\operatorname{argmax}{\left(x_1, \ldots, x_n\right) \in X} \sum{i=1}^n b_i x_i$$
is monotone in the sense of Definition 3.6.
|Assume that ties are broken in a deterministic and consistent way, such as lexicographically.]

## Statistics 155. Game Theory.

TTh 12:30p-2:00p in Stanley 106.GENERAL INFORMATION. (## = berkeley dot edu)
Please include “STAT155” and your SID in the subject line of all emails.
Instructor: Nike Sun (nikesun at ##).
Office hours Thu 2:15p-4:15p in Evans 443.
GSI: Soumendu Mukherjee (soumendu at ##).
Office hours Mon 3:00p-4:30p and Fri 2:30p-4:00p in Evans 444.
Discussion sections Wed 11:00a-12:00n and 12:00n-1:00p in Evans 340.Some materials, including homework assignments, will be posted to bcourses. If you cannot access the site, email the instructor with your @berkeley.edu address.PREREQUISITES. To take this course you should have some background in single-variable calculus, matrix algebra, and probability theory (ideally Statistics 134).REFERENCES.
(KP) Game Theory, Alive by A. Karlin and Y. Peres, available online.
(F) Game Theory by T. S. Ferguson, available online.HOMEWORK. Please be considerate of the grader: write solutions neatly, and staple.
At the top of the first page, write clearly the following information: your name, student ID number, Berkeley email address, the course name (STAT155), and the names of any other students with whom you discussed the assignment. Please also indicate if you are currently waitlisted.
Collaboration policy. You should first attempt to solve homework problems on your own. If you are having trouble, you may discuss with others. You are expected to write down your solutions alone.TESTS. All tests will be closed book and closed notes. No calculators or other devices.
Midterm 1: Thursday September 28, in lecture time slot.
Midterm 2: Thursday November 9, in lecture time slot.
20% homework + 20% midterm 1 + 20% midterm 2 + 40% final.
No late homework will be accepted. Lowest two homework scores will be dropped.
No rescheduling (early/late/repeat) for any exams. Missing the final will automatically result in an F grade. All students will be graded under the same scheme, regardless of late enrollment.SCHEDULE. KP = Karlin & Peres, F = Ferguson (see above for links).

• Lecture 1 (08/24) impartial combinatorial games: subtraction. KP 1.1.
• Lecture 2 (08/29) impartial combinatorial games: Chomp and Nim. KP 1.1.
Homework 1 posted, due 09/06.
• Lecture 3 (08/31) impartial/partisan combinatorial games: Nim/Rims; recursive majority. KP 1.2.
• Lecture 4 (09/05) introduction to zero-sum games; statement of minimax theorem. KP 2.1-2.3.
• Lecture 5 (09/07) zero-sum games; (pure/mixed) Nash equilibria; equalizing payoffs; separating hyperplane theorem. KP 2.4.1, 2.6.
• Lecture 6 (09/12) proof of von Neumann’s minimax theorem via separating hyperplanes. KP 2.6. Homework 2 posted, due 09/20.
• Lecture 7 (09/14) principle of indifference (also called principle of equalizing payoffs or complementary slackness). KP 2.4.2, Proposition 2.5.3.
• Lecture 8 (09/19) domination and indifference; plus one game. KP 2.4.3.
• Lecture 9 (09/21) review of zero-sum games. KP Exercise 2.3.
• Lecture 10 (09/26) review of combinatorial games; Sprague–Grundy theorem. F I.3, I.4.
• Midterm 1 (09/28) covering KP Chapters and 2.
• Lecture 11 (10/03) two-player general-sum games. KP 4.1-4.2.
Homework 3 posted, due 10/11.
• Lecture 12 (10/05) multi-player general-sum games. KP 4.3.
• Lecture 13 (10/10) congestion games, potential games. KP 4.4.
Homework 4 posted, due 10/19.
• Lecture 14 (10/12) consensus game (asynchronous updates versus parallel updates), graph coloring game. KP 4.4.
• Lecture 15 (10/17) competitive pricing game; evolutionarily stable equilibria (ESS). KP 4.5, 7.1.
• Lecture 16 (10/19) ESS and ESMS (evolutionary stability against mixed strategies) in k-player games. KP 7.1.
• Lecture 17 (10/24) ESS in k-player games (polluting factories example); introduction to correlated strategies. KP 7.1-7.2.
• Lecture 18 (10/26) correlated strategies and correlated equilibrium (CE). KP 7.2.
Homework 5 posted, due 11/02.
• Lecture 19 (10/31) traffic congestion games (with infinitesimal drivers), Braess paradox, price of anarchy (POA). KP 8.1.
• Lecture 20 (11/02) traffic games with linear latencies (POA equals 1), traffic games with affine latencies (POA is at most 4/3); Braess paradox and POA. KP 8.1.
• Lecture 21 (11/07) (lecture given by Soumendu) POA under more general latencies. KP 8.1.
Homework 6 posted, due 11/16.
• Lecture 22 (11/14) cooperative games: transferable utility (TU) vs nontransferable utility (NTU); solution of 2-player TU cooperative games via threat strategies. F III.4.1-III.4.2.
• Lecture 23 (11/16) n-player TU cooperative games, as specified by characteristic functions: Gilles core; Shapley value and Shapley random arrival formula. KP 12.1-12.3.
• Lecture 24 (11/21) introduction to auctions: allocation, payment, utility, Bayes–Nash equilibrium (BNE). Examples: first-price and second-price auctions. KP 14.1-14.3.
Homework 7 posted, due 11/29.
• Lecture 25 (11/28) auctions: general approach to finding symmetric BNE; revenue equivalence theorem. KP 14.4.
• Lecture 26 (11/30) review 1.
Homework 8 (last homework) posted, due 12/06.
• Lecture 27 (12/05) review 2 (last lecture).
• The final exam is on Thursday December 14, 3:00-6:00, Hearst Mining Building Room 390 (registrar).