An effective balanced budget and a $d$-nonmanipulable technique for processor time allocation

A. B. Khutoretskiĭ^a, S. V. Bredikhin^b, A. S. Belov<sup>c

a</sup> Novosibirsk State Pedagogical University, Novosibirsk, RUSSIA
^b Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk, RUSSIA
^c Novosibirsk State University, Novosibirsk, RUSSIA

Abstract: We propose a technique for processor time allocation in a grid system which is not manipulable by users and satisfies efficiency, individual rationality, and budget balance conditions. We assume that computers in the system differ in speed and running expenses; every user has one job and a linear usefulness function; the budget of a job coincides with the financial estimate of its usefulness. The mechinque suggested in this article generates a balanced distribution of processor time. It establishes the users' payments in accordance with a generalized Vickrey auction, and payments to the suppliers so that to guarantee budget balance and individual rationality.

Keywords: grid system, processor time allocation, generalized Vickrey auction, nonmanipulability, budget balance, liner programming.

UDC: 519.865.3

Received: 10.09.2010

Bibliographic databases:

•