Compute the optimal social welfare

Assignment Help MATLAB Programming

Reference no: EM133196688

CE322 Algorithmic Game Theory - University of Essex

Question 1:

Consider the following game G:

	A	B
X	4, -4	7,-7
Y	8,-8	6,-6

a. Is there a pure Nash equilibrium in G? Justify your answer.
b. Compute a mixed equilibrium using the indifference conditions of the players. Present both the equilibrium and the analysis clearly. No coding is required.

Question 2:
Consider the following normal form game G. Your task is to find the correlated equilibrium that max- imizes the sum of players' utilities, using Linear Programming in MATLAB. In your report, you need to present the equilibrium that you have computed, the linear program that you are solving (which should include the equilibrium conditions that are satisfied), and a screenshot of your MATLAB in- put AND output. Use the following ordering of variables when constructing your MATLAB input: pXA, pXB, pXC, pY A, pY B, pY C, pZA, pZB, pZC.

	A	B	C
X	6,6	0,8	0,0
Y	8,0	2,2	0,0
Z	0,0	0,0	1,1

Question 3
Five commuters A, B, C, D, E, must choose between their own car with a fixed travel cost, or the public
of using his own car for commuter i A, B, C, D, E and let cA = 1, cB = 3, cC = 5, cD = 7, cE = 9. bus, where the charge to each user decreases with the number of users. Let ci denote the cost/travel time Regarding the bus, if 1 person uses it his cost will be 10, if 2 people use it then each of them will have cost 8, if 3 people use it then each of them will have cost 6, if 4 people use it then each of them will have cost 4, while if all 5 people use it then each of them will have cost 2. Naturally, each player wants to minimize his own cost.

a. Is there any dominated strategy (ies) in this game? If yes, perform an iterated elimination of all dominated strategies. Explicitly mention the sequence in which the corresponding strategies are eliminated and present the resulting game.
b. Find (and clearly present) all pure Nash equilibria (NE) of the game.
c. What is the Price of Stability of this game (assuming that the objective function is the total travel time)?

Question 4
Consider the following sponsored search auction instance I:

• 2 slots. The top slot has a known click-through rate (CTR) ctr1 = 1 and the bottom slot has a known click-through rate ctr3 = 0.5.
• 2 advertisers. Advertiser 1 has a private value-per-click v1 = 1 and advertiser 2 has a private value-per-click v2 = 0.5.
• The payoff of advertiser i, (i is either 1 or 2), who is assigned to the top slot is (vi pi), where pi
is the price charged per-click to i. The payoff of advertiser j (j is either 1 or 2 but different than
i) who is assigned at the bottom slot is 0.5 (vj pj) where pj is the price charged per-click to j. pi and pj are defined by the auction rule, as follows.
Consider the following auction rule (first-price auction):
- Advertisers are asked to declare their value per click (this doesn't mean that their declarations are truthful!). Advertisers are then ranked according to their declarations and the advertiser with the highest declaration is assigned to the slot with the highest CTR (top slot), the advertiser with the second highest declaration is assigned to the slot with the lowest CTR (bottom slot). In case of
a tie, advertiser 1 is allocated to the top slot. The per-click payment of any advertiser is equal to
their own bid.
a. Compute the optimal/highest social welfare (sum of individual values) in I.

b. Assume the following strategy sets (the allowed strategies/reports each player can make) S1 = 0, 0.5, 1 and S2 = 0, 0.5 . Write MATLAB code that computes all Nash equilibria in I (under the first-price auction described above), and outputs the social welfare achieved in each of them.

You can (or not) follow a brute-force approach, i.e. consider all possible combinations of declarations and for each of them check if it is an equilibrium. Copy and paste your MATLAB code in your report, and explicitly mention where in your MATLAB code you guarantee that the equilibrium conditions are satisfied (even if your code doesn't run or doesn't compute an equilibrium). If your code successfully computes one or more equilibria, present them in the report alongside their social welfare. Marks will be awarded for partially-correct approaches.

Reference no: EM133196688

Questions Cloud

Describe the rules of the sport of volleyball : Describe the rules of the sport of volleyball as it is currently played. Describe rules for indoor volleyball game, give court dimension, number of players, etc

Explain in detail at least five separate science arguments : List and explain in detail at least five separate science based arguments you would use in a conversation you would have with a person

Provide a brief rational as to why you chose that scholar : Provide a brief rational as to why you chose that scholar. Lastly, students will also prepare an annotated bibliography of the three readings.

Reply to digital forensics discussion : Reply to Digital Forensics Discussion - The syslog contains informational, warning events and errors related to the OS of a computer

Compute the optimal social welfare : CE322 Algorithmic Game Theory - University of Essex - Compute a mixed equilibrium using the indifference conditions of the players. Present both the equilibrium

How the developments changed societys understanding : Describe how the developments changed society's understanding. How is the development applicable outside of the social sciences?

Why was this patient placed on immunosuppressive therapy : Inflammatory Bowel Disease Case Study - Why was this patient placed on immunosuppressive therapy

What was the framers intent with the constitution : What was the framer's intent with the Constitution? How did they divide the powers between the branches of government?

Describe three factors that can act as triggers : Question - Mass Wasting Events Research Paper - Describe three factors that can act as triggers for mass wasting events

User Account

All Pages