CHAPTER 4
Scalar Strategy, Efficient and Almost Budget
Balanced Mechanisms
We now consider the case when the valuations functions are private information of the
agents. In the case of divisible goods, the valuation function of agents is infinitely dimen-
sional. Therefore, mechanisms for allocation of divisible goods, based only on scalar bids
from agents, are of interest in many practical applications. Each agent reports a scalar
value that is used to choose a surrogate valuation function from a single parameter fam-
ily of valuation functions as in [19]. As the true valuation functions are unknown to the
social planner, dominant strategy implementation is not possible. Instead, an efficient
Nash equilibrium implementation, that is almost budget balanced, can be achieved.
Let V
i
(a
i
) be the valuation for agent i when a
i
is allocated, where V
i
: [0, ) R
is concave, strictly increasing, and differentiable on (0, ). An efficient allocation is a
solution to the following problem:
max
aA
iN
V
i
(a
i
)
(4.1)
where A is a compact and convex set. Let the efficient allocation be a
v
.
Each agent sends a one-dimensional bid
i
to the social planner. From the reported
bids, the central planner constructs a surrogate valuation function v
s
i
(a
i
,
i
), where v
s
i
(·, ·)
is as follows [19]: