=Paper=
{{Paper
|id=Vol-1720/short10
|storemode=property
|title=A Mechanism Design Approach for Allocation of Commodities
|pdfUrl=https://ceur-ws.org/Vol-1720/short10.pdf
|volume=Vol-1720
|authors=Stefano Bistarelli,Rosario Culmone,Paolo Giuliodori,Stefano Mugnoz
|dblpUrl=https://dblp.org/rec/conf/ictcs/BistarelliCGM16
}}
==A Mechanism Design Approach for Allocation of Commodities==
https://ceur-ws.org/Vol-1720/short10.pdf
A Mechanism Design Approach for
Allocation of Commodities ?
Stefano Bistarelli1 , Rosario Culmone2 , Paolo Giuliodori2 and Stefano Mugnoz3
1
University of Perugia, Computer Science Department, Italy
2
University of Camerino, Computer Science Department, Italy
3
U-Space SRL, Rome - Camerino, Italy
Abstract. We deploy a mechanism design approach for allocating a
divisible commodity (electricity in our example) among consumers. We
consider each consumer with an associated personal valuation function of
the energy resource during a certain time interval. We aim to select the
optimal consumption profile for every user avoiding consumption peaks
when the total required energy could exceed the energy production. The
mechanism will be able to drive users in shifting energy consumptions in
different hours of the day. We start by presenting a very basic Vickrey-
Clarke-Groves mechanism, we discuss its weakness and propose several
more complex variants. This is an extended abstract, for additional details
we provide a technical report [1].
1 VCG Mechanisms
Mechanism Design [3–6] is based on the concept of social choice that is simply
an aggregation of the preferences of the different participants toward a single col-
lective decision. Mechanism Design attempts to implement desired social choices
in a strategic setting, assuming that players act rationally in a game theoretic
sense.
Definition 1 (Player’s Valuation Function) Let us consider a set of players
N = {1, . . . , n} and a set of alternatives or outcomes A. Every player i has a
preference over alternatives that is described by a valuation function:
vi : A → R
where vi (a) denotes the valuation that player i assigns to outcome a. Furthermore,
vi ∈ Vi where Vi ⊆ R|A| is a set of possible valuation functions for player i.
?
Research partially supported by: project "Viscolla" co-funded by Fondazione Cassa
di Risparmio di Perugia, project "BitCoins" co-funded by Banca d’Italia and Cassa
di Risparmio di Perugia
Copyright c by the paper’s authors. Copying permitted for private and academic pur-
poses.
V. Biló, A. Caruso (Eds.): ICTCS 2016, Proceedings of the 17th Italian Conference on
Theoretical Computer Science, 73100 Lecce, Italy, September 7–9 2016, pp. 275–279
published in CEUR Workshop Proceedins Vol-1720 at http://ceur-ws.org/Vol-1720
276 Mechanism Design Approach for Energy Efficiency
Definition 2 (Social Choice Function) The social choice function selects an
alternative (or outcome) from the set of alternatives A according to the vector of
users’ valuation functions:
f : V1 × · · · × Vn → A
So, an outcome a, from the set A of alternatives, depends on each possible profile
v = (v1 , v2 , . . . , vn ) :
a = f (v)
This outcome is called social choice for that profile.
When considering a mechanism with money, that is a mechanism where there
are money transfers between the mechanism and players, a payment function
computes money transfers for every players.
Definition 3 (Direct Revelation Mechanism) A direct4 revelation mecha-
nism M is composed of:
M = hf, p1 , . . . , pn i
where f is the social choice function with A as the possible outcomes and p1 , . . . , pn
are the payment vectors where pi : V1 × · · · × . . . Vn → R is the amount that user
i pays to the mechanism.
Definition 4 (Utility Function) Considering a mechanism M = hf, p1 , . . . , pn i,
the valuation set v = (v1 , . . . , vn ) and the alternative chosen a = f (v1 , . . . , vn ),
the utility for every user i is:
ui (a) = vi (a) − pi (vi (a), v−i (a)) (1)
where v−i is the (n-1)-dimensional vector in which the i’th coordinate is removed.
The most famous direct revelation mechanism is the Vickrey-Clarke-Groves
(VCG) Mechanism [5].
Definition 5 (VCG Mechanism) A VCG mechanism determines f (v):
n
X
f (v) ∈ argmaxb∈A vj (b) (2)
j=1
and pi (v) such that:
n
X
pi (v) = hi (v−i ) − vj (f (v)) (3)
j6=i
for some function h1 , . . . , hn where hi : V−i → R.
4
There exists also the indirect revelation mechanism with money, that differs for the
fact that players have private information (player’s preferences) and select strategies
according to this information set. In this work, we do not consider indirect revelation
mechanism because we assume that the users’ valuations functions are known.
A Mechanism Design Approach for Allocation of Commodities 277
Now, there are several versions of the model according to the choice of hi (v−i ).
Important to note that the function hi can be any arbitrary function but it must
not depend on the vi . One of the most important versions is the VCG mechanism
with the Clarke pivot rule, introduced by Clarke [2].
Definition 6 (VCG Mechanism with Clarke Pivot Rule) A VCG mech-
anism with Clarke pivot payments determines hi (vi ):
n
X
hi (v−i ) = maxa vj (a) (4)
j6=i
so pi (v) becomes:
n
X n
X
pi (v) = maxb vj (b) − vj (f (v)) (5)
j6=i j6=i
where b is the selected alternative if the i-th player is not present in the system5 .
By choosing this kind of hi (v−i ) Clarke wants to let the buyer paying only the
influence that he has in the system. In fact, an user influences the system when
the outcome changes depending on the absence or presence of player i. If the
outcome changes significantly when player i is removed, it means that player i
strongly affects the system, so he has to pay for his influence (from this concept
derives the name “Clarke pivot rule").
2 Problem Formulation and System Model
2.1 Problem Description
In our work, we model an energy allocation problem through a VCG mechanism
approach. The main aim is to avoid blackouts when the users’ requested energy
exceeds the available energy and the energy network must be switched off due
to overload. Fig. 1 describes a possible case for one-day time period with trends
for the energy functions. The dashed lightblue line represents the distributor’s
available energy, the continuous darkblue line the energy requested from all con-
sumers. The lines on the bottom represent the single consumption of every user
(five users in this case). So in Fig. 1b, we can consider only the consumers "play-
ers" and the energy available function as a parameter for the mechanism. The
produced energy is a constraint to take into account while maximizing the social
welfare. Fig. 1a describes an example of a situation in which energy availability
function (dashed lightblue line) and aggregate users’ consumption (continuous
darkblue line) are compared. Where the set of players contains the distributor
5
Here, “a" is the optimal assignment including player “i", while “b" is the optimal
assignment when we exclude player “i"
278 Mechanism Design Approach for Energy Efficiency
(a) Trend of energy availability considering (b) Trend of energy availability considering
the energy distributor a player. only consumers as players
Fig. 1: Comparison between energy functions: users’ desired trends, the aggre-
gated desired trend of all of agent and the produced energy function.
and the difference between this two functions (production - consumption, the
dotted red line in the graph) must be greater or equal than zero. In fact, another
way to tackle this problem is that we can consider that the difference between
the production and the aggregate consumption, must be greater or equal than
zero for this purpose we can consider the distributor as a player. The main idea
is to deploy a mechanism in order to drive users in shifting energy consumptions,
according to the produced energy and the consumption preference of the com-
munity.
2.2 Model Description
Our objective is to determine a mechanism that will select the optimal energy ac-
cording to the desired consumption of every player. We were initially inspired by
the "Public Project" example provided in [5]. To better understand the idea, we
could sum up our problem by drawing connections with the classical knapsack op-
timization problem. As first solution, we decide to put all into the knapsack only
if the volume of the knapsack is sufficient, otherwise we do not put in anything.
In the energy case, the distributor will provide energy only if the consumption is
not greater than the available energy. For this reason, we consider a scenario with
an energy distributor and n energy users (n + 1 players). The distributor has an
amount of available energy and each consumer has a desired consumption, that
is represented by a negative value due to the design of the social choice function
of the VCG mechanism showed in Eq. 2. This mechanism has the positive aspect
that it avoids blackout situations.
As a further solution, we assume that we have a set of object to put into the
knapsack minimizing the empty space. We model the scenario removing the
distributor from the set of players and considering the available energy a thresh-
old resulting that the energy is provided only to a subset of users with aim to
avoiding the waste of produced energy. Moreover, each consumer has a positive
desired consumption avoiding a negative net utility introduced in Eq. 1. This
A Mechanism Design Approach for Allocation of Commodities 279
second model with respect to the first one allows to provide energy even if the
the aggregated consumption is greater than the production by selecting a subset
of users. Regarding the next solution, we assume that we have a liquid instead
of a set of objects, so we are able to fill the entire knapsack. So, we introduce a
third solution that assigns to users all the available energy till reaching the total
amount of produced energy. It means that for each user the mechanism calculates
a portion of available energy not greater than his desired consumption. Here as
well, the mechanism selects the consumption for a subset of users, however, un-
like the second case, there is no wasted energy. The next improved mechanism is
similar to the third solution and in addition we introduce the time variable. So,
every energy function become a power function over time and the mechanism
chooses the energy to be provided according to every user’s preferences, allowing
the shifting of the consumption in the time interval considering that each user
must receive at least his aggregated requested energy.
Our final approach is based on the previous one in which we assign a part of
available power thanks to a proportional allocation scheme that provides a posi-
tive amount of power to every user.
A final remark is that this model is essentially a game so players must be moti-
vated to play by getting a positive utility. But, in our case study, energy allocation,
a user usually has to consume and, consequently, play the game for this reason
he can accept also an utility equal to zero.
In this work, we propose several configurations of the mechanism, starting from
the simplest to a more complicated configuration which has the property of as-
signing the available energy to users according to their desired energy minimizing
the energy wasting while maximizing the aggregate utility of all users.
A development is to find a different payment scheme that takes into account the
actual consumption and energy consumption peaks. The final aim is to stimulate
users to behave in a good energy way offering a discount on the electricity bill
that will lead to get a positive net utility.
References
1. Bistarelli, S., Culmone, R., Giuliodori, P., Mugnoz, S.: Mechanism Design Approach
for Energy Efficiency. ArXiv e-prints (Aug 2016)
2. Clarke, E.H.: Multipart pricing of public goods. Public Choice 11(1), 17–33 (1971),
http://dx.doi.org/10.1007/BF01726210
3. Jackson, M.O.: Mechanism theory. In: Derigs, U. (ed.) EOLSS The Encyclopedia of
Life Support Systems. EOLSS Publishers: Oxford UK (2003)
4. Narahari, Y.: Game Theory and Mechanism Design, chap. 14. World Scientific Pub-
lishing Company Pte. Limited (2014)
5. Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory,
chap. 9. Cambridge University Press (2007)
6. Shoham, Y., Leyton-Brown, K.: Multiagent Systems: Algorithmic, Game-Theoretic,
and Logical Foundations, chap. 10. Cambridge University Press, New York, NY, USA
(2008)