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.'

Search Nedrilad ::

Custom Search