Game Development Reference
In-Depth Information
manipulate the outcome (decision). To better understand the notion of a
decision problem consider the following two natural examples.
Example 1.26 [Sealed-bid Auction]
We consider a sealed-bid auction in which there is a single object for
sale. Each player (bidder) simultaneously submits to the central authority
his type (bid) in a sealed envelope and the object is allocated to the highest
bidder.
Given a sequence a := ( a 1 ,...,a j ) of reals denote the least l such that
a l = max k∈{ 1 ,...,j} a k by argsmax a . Then we can model a sealed-bid auction
as the following decision problem ( D, Θ 1 ,..., Θ n ,v 1 ,...,v n ,f ):
D =
{
1 ,...,n
}
,
for all i
∈{
1 ,...,n
}
i =
R + ; θ i
Θ i is player's i valuation of the object,
, v i ( d, θ i ):=( d = i ) θ , where d = i is a Boolean
expression with the value 0 or 1,
• f ( θ ):=argsmax θ.
for all i
∈{
1 ,...,n
}
Here decision d
D indicates to which player the object is sold. Further,
f ( θ )= i , where
θ i = max j∈{ 1 ,...,n} θ j and
j
∈{
1 ,...,i
1
}
θ j i .
So we assume that in the case of a tie the object is allocated to the highest
bidder with the lowest index.
Example 1.27 [Public project problem]
This problem deals with the task of taking a joint decision concerning
construction of a public good , 4 for example a bridge. Each player reports
to the central authority his appreciation of the gain from the project when
it takes place. If the sum of the appreciations exceeds the cost of the project,
the project takes place and each player has to pay the same fraction of the
cost. Otherwise the project is cancelled.
This problem corresponds to the following decision problem, where c , with
c> 0, is the cost of the project:
• D = { 0 , 1 } (reflecting whether a project is cancelled or takes place),
for all i
∈{
1 ,...,n
}
i =
R + ,
c
for all i
∈{
1 ,...,n
}
, v i ( d, θ i ):= d ( θ i
n ),
4 In Economics public goods are so-called not excludable and non-rival goods. To quote from
Mankiw [2001]: 'People cannot be prevented from using a public good, and one person's
enjoyment of a public good does not reduce another person's enjoyment of it.'