微信客服：xiaoxionga100
微信客服：ITCS521
程序代写案例-QBUS 3310
时间：2022-07-04
QBUS 3310 practice questions – with solutions
Question 1
Two companies, Fast Rail and Snail Rail, are to tender for the construction of one of two
light rail connections from the city: Chatswood or Parramatta. They can submit a tender for
at most one of the connections (thus, they can either choose to submit a tender for the
Chatswood line, submit a tender for the Parramatta line, or not submit a tender at all).
The Chatswood connection is worth $20 M while the Parramatta connection is worth $50M.
If they submit tenders for different light rail connections, each will be awarded the contract
to build the connection for which they tendered. If they submit a tender for the same
connection, Fast rail is given the contract to build the light rail connection for both
Chatswood and Parramatta.
(a) Represent this situation as a game in matrix form (have Fast Rail be the row
player).
Let Fast Rail be the row player and Snail Rail be the column player. Also, let the first
strategy be tendering for Parramatta, the second strategy be tendering for
Chatswood and the third strategy not tendering at all. The game matrix is:
70,0 50,20 50,0
20,50 70,0 20,0
0,50 0,20 0,0
(b) What type of game is this (zero-sum, constant-sum, non-constant sum)?
Eliminate any dominated strategies and answer the question again.
In its current form, the game seems like a non-constant sum game.
Let’s eliminate the dominated strategies. Clearly, the strategy of not tendering is
dominated for both players. After eliminating the third row and third column we
obtain the following matrix.
70,0 50,20
20,50 70,0
Note that this is now a constant sum game. We can rewrite the matrix to express the
row players reward (the column player receives the difference between 70 and this
reward).
70 50
20 70
(c) What is the optimal strategy for each player (company) and how much is each
expected to earn?
The row player will play strategies 1 and 2 with probabilities p and (1-p). In order to
maximise his earnings, he must ensure that he receives the same return for any
strategy the column player chooses. Thus,
( ) ( )70 20 1 50 70 1 70 50 5 / 7p p p p p p+ − = + − ⇒ = ⇒ = .
The total reward for the row player is ( ) 570 5 / 7 20 1 5 / 7 55
7
× + − =
The column player will play strategies 1 and 2 with probabilities q and (1-q). In order
to maximise his earnings, he must ensure that he receives the same return for any
strategy the row player chooses. Thus,
( ) ( )70 50 1 20 70 1 70 20 2 / 7q q q q q q+ − = + − ⇒ = ⇒ = .
The total reward for the row player is: ( )( ) 5 270 70 2 / 7 50 1 2 / 7 70 55 14
7 7
− × + − = − =
.
Question 2
There are five lifeguard towers lined along a beach, where the left-most tower is number 1
and the right most tower is number 5. Two vendors each have an ice cream stand that can
be located next to one of five towers. There are 10 people located next to each tower, and
each person will purchase an ice cream from the stand that is closest to him or her. That is,
if Vendor 1 locates his stand at tower 2 and Vendor 2 at tower 3, then 20 people (at towers
1 and 2) will purchase from Vendor 1, while 30 (from towers 3,4 and 5) will purchase from
Vendor 2. If the vendors are located at tower 2 and 4, respectively, then people at tower 3
are equally likely to buy an ice cream from the two vendors (so 5 will buy one from Vendor 1
and 5 will buy one from Vendor 2). Each purchase yields a profit of $1.
(a) Specify the strategy set of each vendor and provide the matrix for the game.
(b) Are there any strictly dominated strategies?
(c) What is the solution of the game?
The matrix describing the game is:
Player 2
Player
1
Tower 1 2 3 4 5
1 (25,25) (10,40) (15,35) (20,30) (25,25)
2 (40,10) (25,25) (20,30) (25,25) (30,20)
3 (35,15) (30,20) (25,25) (30,20) (35,15)
4 (30,20) (25,25) (20,30) (25,25) (40,10)
5 (25,25) (20,30) (15,35) (10,40) (25,25)
One can easily see that Rows 1,2,4, and 5 are dominated by Row 3. Similarly,
Columns 1,2,4 and 5 are dominated by Column 3. As a result, both vendors will set
up their stall in Tower 3 and generate a profit of $25.
Question 3
Consider the following game: two players compete against each other; each player shows
either one or two fingers and announces a number between 2 and 4. If a player's number is
equal to the sum of the number of fingers shown, then his opponent must pay him that
many dollars. The payoff is the net transfer (so that both players earn zero if both or neither
guess the correct number of fingers shown).
(a) Identify strategies that don’t make sense and will always be avoided.
Answer: In this game each player has 6 strategies: he may show one finger and guess
2; he may show one finger and guess 3; he may show one finger and guess 4; or he
may show two fingers and guess one of the three numbers. Of these 6 strategies,
two are silly and should be discarded. It never pays to put out one finger and guess
that the total number of fingers will be 4 (because the other player can put out
more than two fingers). It never pays to put out two fingers and guess that the sum
will be 2 (because the other player must put down at least one finger).
(b) Construct the matrix for the Zero-sum game described (using only meaningful
strategies; ones that weren’t identified in part (a)). Provide the reward for the Row
player. Don’t solve the game.
After having eliminated the redundant strategies, the four by four matrix describes
the payoff is:
Player B
Player
A
(X,Y) 1,2 1,3 2,3 2,4
1,2 0 2 -3 0
1,3 -2 0 0 3
2,3 3 0 0 -4
2,4 0 -3 4 0
Question 4
John is a business development officer for a large software company. He meets potential
clients in only two cities, Sydney and Melbourne. If he is currently in Sydney, there is a 0.6
probability that his next client meeting is in Sydney. Hence, there is a 0.4 probability that he
will need to fly to Melbourne for his next client meeting. When in Melbourne for a meeting,
there is a 0.7 probability that his next client meeting is in Melbourne (and a 0.3 probability
that he will need to fly to Sydney for his next meeting).
(a) What is the long run proportion of meetings John holds in Sydney and what is the
long run proportion of meetings he holds in Melbourne?
Assuming that the first state in the following matrix is Sydney and the second is
Melbourne, the probability transition matrix is: �0.6 0.40.3 0.7�.
We must calculate the steady state probabilities. We can use the following
equations:
+ = 1; 0.6 + 0.3 = . Thus,
= 3/7 = 4/7.
In the long run 3/7 meetings will be held in Sydney (42.86%) and 4/7 meetings
will be held in Melbourne (57.14%).
(b) John’s hotel room in Sydney costs $400 per night. His hotel room in Melbourne
costs $300 per night. Flights from Sydney to Melbourne and from Melbourne to
Sydney cost John $200 (one way). Assume that John meets exactly 1 client every
day. What is the long run cost of hotels & flights that John incurs?
The proportion of nights in Sydney: 3/7
The proportion of nights in Melbourne 4/7
The proportion of flights: 3/7 × 0.4 + 4/7 × 0.3 = 12/35
Average costs: 3/7 × 400 + 4/7 × 300 + 12/35 × 200 = $411.43
Question 5
A boy and a girl move to the same two-bar-town on the same day. Each night, the boy visits
one bar, starting the first night in bar 1 and continues by selecting a bar for the next night
according to a Markov chain with transition matrix B below. Similarly, the girl visits one bar a
night, starting with bar 2 and selecting the next bar according to G below.
=
=
9.01.0
1.09.0
8.02.0
2.08.0
GB Where B is the boy’s transition matrix and G is the girl’s
transition matrix.
Once the boy and the girl go to the same bar one night, they keep going to the same bar
(either bar 1 for bar 2) for the obvious reason.
Model the progress of the boy and the girl finding each other as a single Markov chain
where only one state is absorbing.
This is a hard question. The three states are I – boy goes to bar 1 and girl to bar 2; II –
boy goes to bar 2 and girl to bar 1; III – they go to the same bar.
The transition probabilities for the first state:
11
12
13
0.8 0.9 0.72 1 2
0.2 0.1 0.02
0.8 0.1 0.2 0.9 0.26
p boy stays in and girl stays in
p both switchbars
p boy stays and girl swicths OR girl stays and boy switches
= × =
= × =
= × + × =
The transition probabilities for the second state:
21
22
23
0.2 0.1 0.02
0.8 0.9 0.72 2 1
0.8 0.1 0.2 0.9 0.26
p both switchbars
p boy stays in and girl stays in
p boy stays and girl swicths OR girl stays and boy switches
= × =
= × =
= × + × =
The transition probabilities for the third state:
31 32 330; 1; .p p p They always stay together= = =
The transition probability matrix:
0.72 0.02 0.26
0.02 0.72 0.26
0 0 1
Question 6
Consider the following knapsack problem: you are given a set of items {1,2,3, … ,} with
weights and utility . You have a knapsack that can hold at most a total weight of
,ℎ ∑ > .=1 Hence, you are not able to take with you all of the items. The
formulation of the problem we provided in lecture was:
Let be the total utility in steps , + 1, … , ℎ ℎ. The
recursive relationship of costs is = { + +1( − ),+1()}. ℎ 1(), and the boundary condition is+1() = 0.
Assume that you now have two knapsacks with available weights 1 2, .
The weight constraint is now ∑ > 1 + 2.=1 How would your formulation change in
order to accommodate the fact that you have two knapsacks?
Let be the total utility in steps , + 1, … , 1 2 ℎ ℎ 1 2, . The recursive relationship of costs is
= { + +1(1 − ,2), + +1(1,2 − ), 0 + +1(1,2)}. ℎ 1(1,2), and the boundary condition is+1(1,2) = 0.
Question 1
Two companies, Fast Rail and Snail Rail, are to tender for the construction of one of two
light rail connections from the city: Chatswood or Parramatta. They can submit a tender for
at most one of the connections (thus, they can either choose to submit a tender for the
Chatswood line, submit a tender for the Parramatta line, or not submit a tender at all).
The Chatswood connection is worth $20 M while the Parramatta connection is worth $50M.
If they submit tenders for different light rail connections, each will be awarded the contract
to build the connection for which they tendered. If they submit a tender for the same
connection, Fast rail is given the contract to build the light rail connection for both
Chatswood and Parramatta.
(a) Represent this situation as a game in matrix form (have Fast Rail be the row
player).
Let Fast Rail be the row player and Snail Rail be the column player. Also, let the first
strategy be tendering for Parramatta, the second strategy be tendering for
Chatswood and the third strategy not tendering at all. The game matrix is:
70,0 50,20 50,0
20,50 70,0 20,0
0,50 0,20 0,0
(b) What type of game is this (zero-sum, constant-sum, non-constant sum)?
Eliminate any dominated strategies and answer the question again.
In its current form, the game seems like a non-constant sum game.
Let’s eliminate the dominated strategies. Clearly, the strategy of not tendering is
dominated for both players. After eliminating the third row and third column we
obtain the following matrix.
70,0 50,20
20,50 70,0
Note that this is now a constant sum game. We can rewrite the matrix to express the
row players reward (the column player receives the difference between 70 and this
reward).
70 50
20 70
(c) What is the optimal strategy for each player (company) and how much is each
expected to earn?
The row player will play strategies 1 and 2 with probabilities p and (1-p). In order to
maximise his earnings, he must ensure that he receives the same return for any
strategy the column player chooses. Thus,
( ) ( )70 20 1 50 70 1 70 50 5 / 7p p p p p p+ − = + − ⇒ = ⇒ = .
The total reward for the row player is ( ) 570 5 / 7 20 1 5 / 7 55
7
× + − =
The column player will play strategies 1 and 2 with probabilities q and (1-q). In order
to maximise his earnings, he must ensure that he receives the same return for any
strategy the row player chooses. Thus,
( ) ( )70 50 1 20 70 1 70 20 2 / 7q q q q q q+ − = + − ⇒ = ⇒ = .
The total reward for the row player is: ( )( ) 5 270 70 2 / 7 50 1 2 / 7 70 55 14
7 7
− × + − = − =
.
Question 2
There are five lifeguard towers lined along a beach, where the left-most tower is number 1
and the right most tower is number 5. Two vendors each have an ice cream stand that can
be located next to one of five towers. There are 10 people located next to each tower, and
each person will purchase an ice cream from the stand that is closest to him or her. That is,
if Vendor 1 locates his stand at tower 2 and Vendor 2 at tower 3, then 20 people (at towers
1 and 2) will purchase from Vendor 1, while 30 (from towers 3,4 and 5) will purchase from
Vendor 2. If the vendors are located at tower 2 and 4, respectively, then people at tower 3
are equally likely to buy an ice cream from the two vendors (so 5 will buy one from Vendor 1
and 5 will buy one from Vendor 2). Each purchase yields a profit of $1.
(a) Specify the strategy set of each vendor and provide the matrix for the game.
(b) Are there any strictly dominated strategies?
(c) What is the solution of the game?
The matrix describing the game is:
Player 2
Player
1
Tower 1 2 3 4 5
1 (25,25) (10,40) (15,35) (20,30) (25,25)
2 (40,10) (25,25) (20,30) (25,25) (30,20)
3 (35,15) (30,20) (25,25) (30,20) (35,15)
4 (30,20) (25,25) (20,30) (25,25) (40,10)
5 (25,25) (20,30) (15,35) (10,40) (25,25)
One can easily see that Rows 1,2,4, and 5 are dominated by Row 3. Similarly,
Columns 1,2,4 and 5 are dominated by Column 3. As a result, both vendors will set
up their stall in Tower 3 and generate a profit of $25.
Question 3
Consider the following game: two players compete against each other; each player shows
either one or two fingers and announces a number between 2 and 4. If a player's number is
equal to the sum of the number of fingers shown, then his opponent must pay him that
many dollars. The payoff is the net transfer (so that both players earn zero if both or neither
guess the correct number of fingers shown).
(a) Identify strategies that don’t make sense and will always be avoided.
Answer: In this game each player has 6 strategies: he may show one finger and guess
2; he may show one finger and guess 3; he may show one finger and guess 4; or he
may show two fingers and guess one of the three numbers. Of these 6 strategies,
two are silly and should be discarded. It never pays to put out one finger and guess
that the total number of fingers will be 4 (because the other player can put out
more than two fingers). It never pays to put out two fingers and guess that the sum
will be 2 (because the other player must put down at least one finger).
(b) Construct the matrix for the Zero-sum game described (using only meaningful
strategies; ones that weren’t identified in part (a)). Provide the reward for the Row
player. Don’t solve the game.
After having eliminated the redundant strategies, the four by four matrix describes
the payoff is:
Player B
Player
A
(X,Y) 1,2 1,3 2,3 2,4
1,2 0 2 -3 0
1,3 -2 0 0 3
2,3 3 0 0 -4
2,4 0 -3 4 0
Question 4
John is a business development officer for a large software company. He meets potential
clients in only two cities, Sydney and Melbourne. If he is currently in Sydney, there is a 0.6
probability that his next client meeting is in Sydney. Hence, there is a 0.4 probability that he
will need to fly to Melbourne for his next client meeting. When in Melbourne for a meeting,
there is a 0.7 probability that his next client meeting is in Melbourne (and a 0.3 probability
that he will need to fly to Sydney for his next meeting).
(a) What is the long run proportion of meetings John holds in Sydney and what is the
long run proportion of meetings he holds in Melbourne?
Assuming that the first state in the following matrix is Sydney and the second is
Melbourne, the probability transition matrix is: �0.6 0.40.3 0.7�.
We must calculate the steady state probabilities. We can use the following
equations:
+ = 1; 0.6 + 0.3 = . Thus,
= 3/7 = 4/7.
In the long run 3/7 meetings will be held in Sydney (42.86%) and 4/7 meetings
will be held in Melbourne (57.14%).
(b) John’s hotel room in Sydney costs $400 per night. His hotel room in Melbourne
costs $300 per night. Flights from Sydney to Melbourne and from Melbourne to
Sydney cost John $200 (one way). Assume that John meets exactly 1 client every
day. What is the long run cost of hotels & flights that John incurs?
The proportion of nights in Sydney: 3/7
The proportion of nights in Melbourne 4/7
The proportion of flights: 3/7 × 0.4 + 4/7 × 0.3 = 12/35
Average costs: 3/7 × 400 + 4/7 × 300 + 12/35 × 200 = $411.43
Question 5
A boy and a girl move to the same two-bar-town on the same day. Each night, the boy visits
one bar, starting the first night in bar 1 and continues by selecting a bar for the next night
according to a Markov chain with transition matrix B below. Similarly, the girl visits one bar a
night, starting with bar 2 and selecting the next bar according to G below.
=
=
9.01.0
1.09.0
8.02.0
2.08.0
GB Where B is the boy’s transition matrix and G is the girl’s
transition matrix.
Once the boy and the girl go to the same bar one night, they keep going to the same bar
(either bar 1 for bar 2) for the obvious reason.
Model the progress of the boy and the girl finding each other as a single Markov chain
where only one state is absorbing.
This is a hard question. The three states are I – boy goes to bar 1 and girl to bar 2; II –
boy goes to bar 2 and girl to bar 1; III – they go to the same bar.
The transition probabilities for the first state:
11
12
13
0.8 0.9 0.72 1 2
0.2 0.1 0.02
0.8 0.1 0.2 0.9 0.26
p boy stays in and girl stays in
p both switchbars
p boy stays and girl swicths OR girl stays and boy switches
= × =
= × =
= × + × =
The transition probabilities for the second state:
21
22
23
0.2 0.1 0.02
0.8 0.9 0.72 2 1
0.8 0.1 0.2 0.9 0.26
p both switchbars
p boy stays in and girl stays in
p boy stays and girl swicths OR girl stays and boy switches
= × =
= × =
= × + × =
The transition probabilities for the third state:
31 32 330; 1; .p p p They always stay together= = =
The transition probability matrix:
0.72 0.02 0.26
0.02 0.72 0.26
0 0 1
Question 6
Consider the following knapsack problem: you are given a set of items {1,2,3, … ,} with
weights and utility . You have a knapsack that can hold at most a total weight of
,ℎ ∑ > .=1 Hence, you are not able to take with you all of the items. The
formulation of the problem we provided in lecture was:
Let be the total utility in steps , + 1, … , ℎ ℎ. The
recursive relationship of costs is = { + +1( − ),+1()}. ℎ 1(), and the boundary condition is+1() = 0.
Assume that you now have two knapsacks with available weights 1 2, .
The weight constraint is now ∑ > 1 + 2.=1 How would your formulation change in
order to accommodate the fact that you have two knapsacks?
Let be the total utility in steps , + 1, … , 1 2 ℎ ℎ 1 2, . The recursive relationship of costs is
= { + +1(1 − ,2), + +1(1,2 − ), 0 + +1(1,2)}. ℎ 1(1,2), and the boundary condition is+1(1,2) = 0.
