这是一份2022夏季的伯克利大学STAT 155 001 game theory Assignment 3作业代写的成功案例
数学作业代写|game theory Assignment 3
Exercise 4.2 Continuing the previous exercise, restrict now to feasible sets $X$ that contain only 0-1 vectors – that is, each bidder either wins or loses. We can identify each feasible outcome with a “feasible set” of bidders (the winners). Assume that for every bidder $i$, there is an outcome in which $i$ does not win. Myerson’s payment formula (3.5) dictates that a winning bidder pays her “critical bid”-the infimum of the bids at which she would continue to win.
Prove that, when $S^$ is the set of winning bidders under the allocation rule (4.2) and $i \in S^, i$ ‘s critical bid equals the difference between (1) the maximum social welfare of a feasible set that excludes $i$; and (2) the social welfare $\sum_{j \in S^* \backslash{i}} v_j$ of the bidders other than $i$ in the chosen outcome $S^*$.
IIn this sense, each winning bidder pays her “externality” – the welfare loss she imposes on others.|
Exercise 4.5 Prove that the three-step greedy knapsack auction allocation rule in Section 4.2.2 is monotone. Does it remain monotone with the two optimizations discussed in the footnotes?
Problem 4.1 Consider a variant of a knapsack auction in which both the valuation $v_i$ and the size $w_i$ of each bidder $i$ are private. A mechanism now receives both bids $\mathbf{b}$ and reported sizes a from the bidders. An allocation rule $\mathrm{x}(\mathrm{b}, \mathrm{a})$ now specifies the amount of capacity allocated to each bidder, as a function of the bids and reported sizes. Feasibility dictates that $\sum_{i=1}^n x_i(\mathrm{~b}, \mathrm{a}) \leq W$ for every b and a, where $W$ is the total capacity of the shared resource. We define the utility of a bidder $i$ as $v_i-p_i(\mathbf{b}, \mathbf{a})$ if she gets her required capacity (i.e., $\left.x_i(\mathbf{b}, \mathbf{a}) \geq w_i\right)$ and as $-p_i(\mathbf{b}, \mathbf{a})$ otherwise. This is not a single-parameter environment.
Consider the following mechanism. Given bids $\mathbf{b}$ and reported sizes a, the mechanism runs the greedy knapsack auction of Section 4.2.2, taking the reported sizes a at face value, to obtain a subset of winning bidders and prices $\mathbf{p}$. The mechanism concludes by awarding each winning bidder capacity equal to her reported size $a_i$, at a price of $p_i$; losing bidders receive and pay nothing. Is this mechanism DSIC? Prove it or give an explicit counterexample.
Exercise 5.2 Compute the virtual valuation function of the following distributions.
(a) The uniform distribution on $[0, a]$ with $a>0$.
(b) The exponential distribution with rate $\lambda>0$ (on $[0, \infty)$ ).
(c) The distribution given by $F(v)=1-\frac{1}{(v+1)^c}$ on $[0, \infty)$, where $c>0$ is some constant.
Just C. Is this a regular distribution?
Exercise 5.5 Prove that for every single-parameter environment and regular valuation distributions $F_1, \ldots, F_n$, the virtual-welfaremaximizing allocation rule is monotone in the sense of Definition 3.6. Assume that ties are broken lexicographically with respect to some fixed total ordering over the feasible outcomes.
Exercise 5.8 Repeat the previous exercise for sponsored search auctions (Example 3.3).
Exercise 5.7 Consider a $k$-unit auction (Example 3.2) in which bidders’ valuations are drawn i.i.d. from a regular distribution $F$. Describe an optimal auction. Which of the following does the reserve price depend on: $k, n$, or $F$ ?
Problem 5.1 This problem derives an interesting interpretation of a virtual valuation $\varphi(v)=v-\frac{1-F(v)}{f(v)}$ and the regularity condition. Consider a strictly increasing distribution function $F$ with a strictly positive density function $f$ on the interval $\left[0, v_{\max }\right]$, with $v_{\max }<+\infty$.
For a single bidder with valuation drawn from $F$, for $q \in[0,1]$, define $V(q)=F^{-1}(1-q)$ as the (unique) posted price that yields a probability $q$ of a sale. Define $R(q)=q \cdot V(q)$ as the expected revenue obtained from a single bidder when the probability of a sale is $q$. The function $R(q)$, for $q \in[0,1]$, is the revenue curve of $F$. Note that $R(0)=R(1)=0$.
(a) What is the revenue curve for the uniform distribution on $[0,1]$ ?
(b) Prove that the slope of the revenue curve at $q$ (i.e., $\left.R^{\prime}(q)\right)$ is precisely $\varphi(V(q))$, where $\varphi$ is the virtual valuation function for $F$.
(c) Prove that a distribution is regular if and only if its revenue curve is concave.
数学代写|game theory Assignment 3 请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。
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.
Final: Thursday December 14, 3:00-6:00, Hearst Mining 390.GRADING. Your final grade will consist of
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).
