It was Manwë's decision via the will of Eru*
Manwë foresaw that out of this evil "new good should come."
It is rather clear from the published Silmarillion that Manwë was the deciding vote when it came to Melkor's re-trial. However, Manwë had more knowledge then we can perceive, and although his decision may look wrong, it was the right decision to allow for the growth of good in the world, it was also in line with the Will of Eru Iluvatar, the Maker
When Melkor was chained. He was sentenced to "three ages" (Sil, III) of imprisonment in the Halls of Mandos before he would be allowed a re-trial. The Valar being pure beings were forced to keep their word, and therefore after the time was deemed elapsed, Melkor was once again brought before Manwë,
For it came to pass that Melkor, as the Valar had decreed, completed the term of his bondage, dwelling for three ages in the duress of Mandos, alone. At length, as Manwë had promised, he was brought again before the thrones of the Valar.
Then Manwë granted him pardon; but the Valar would not yet suffer him to depart beyond their sight and vigilance, and he was constrained to dwell within the gates of Valmar.
... therefore in a while he was given leave to go freely about the land, and it seemed to Manwë that the evil of Melkor was cured. For Manwë was free from evil and could not comprehend it, and he knew that in the beginning ... Melkor had been even as he...
The Silmarillion - Chapter VI, Of Fëanor and the Unchaining of Melkor
From the published Silmarillion, we get the idea that Manwë had been deceived once again by the trickery of Melkor and that he had, through deceit, found his freedom and could once again carry out his machinations.
* However, in Myths Transformed, Text VII (HoME X, Morgoth's Ring) in an essay titled Notes on motives in The Silmarillion, specifically in part (iii), Tolkien gives us insight into the motives of the Valar during the Unchaining of Melkor. In Myths Transformed, the Professor notes that one should be wary when finding faults in Manwë's judgement.
But, if we dare to attempt to enter the mind of the Elder King, assigning motives and finding faults, there are things to remember before we deliver a judgement. Manwe was the spirit of greatest wisdom and prudence in Arda. He is represented as having had the greatest knowledge of the Music, as a whole, possessed by any one finite mind; and he alone of all persons or minds in that time is represented as having the power of direct recourse to and communication with Eru. He must have grasped with great clarity what even we may perceive dimly: that it was the essential mode of the process of 'history' in Arda that evil should constantly arise, and that out of it new good should constantly come. One especial aspect of this is the strange way in which the evils of the Marrer, or his inheritors, are turned into weapons against evil.
As Tolkien states in the essay, Manwë had more knowledge than us as a reader and was aware, either through his wisdom or communication with Eru, that the release of Melkor was a necessary part of the "process of 'history' in Arda". This idea is similarly repeated in the Ósanwe-kenta (left at the bottom because it is incredibly long). In the Ósawne-kenta, Tolkien discussed the viewer's perception of the folly of Manwë in his decisions and the ease with which Melkor deceived others. However the professor again suggest that Manwë could not have forced Melkor to speak the truth, nor could the other Valar (through telepathy) as this would be using evil do deceive evil, which the Valar could not do. Manwë was open to the thoughts of Eru and carried out his will, this is perceived to be greater than wisdom. Manwë's actions ensured Eru's plan would unfold. In a similar vain, it was only by word of Eru that Manwë finally beheaded Melkor and sent his spirit to wander the void.
If we speak last of the "folly" of Manwe and the weakness and unwariness of the Valar, let us beware how we judge. In the histories, indeed, we may be amazed and grieved to read how (seemingly) Melkor deceived and cozened others, and how even Manwe appears at times almost a simpleton compared with him: as if a kind but unwise father were treating a wayward child who would assuredly in time perceive the error of his ways. Whereas we, looking on and knowing the outcome, see now that Melkor knew well the error of his ways, but was fixed in them by hate and pride beyond return. He could read the mind of Manwe, for the door was open; but his own mind was false and even if the door seemed open, there were doors of iron within closed for ever.
How otherwise would you have it? Should Manwe and the Valar meet secrecy with subterfuge, treachery with falsehood, lies with more lies? If Melkor would usurp their rights, should they deny his? Can hate overcome hate? Nay, Manwe was wiser; or being ever open to Eru he did His will, which is more than wisdom. He was ever open because he had nothing to conceal, no thought that it was harmful for any to know, if they could comprehend it. Indeed Melkor knew his will without questioning it; and he knew that Manwe was bound by the commands and injunctions of Eru, and would do this or abstain from that in accordance with them, always, even knowing that Melkor would break them as it suited his purpose. Thus the merciless will ever count on mercy, and the liars make use of truth; for if mercy and truth are withheld from the cruel and the lying, they have ceased to be honoured.
Manwe could not by duress attempt to compel Melkor to reveal his thought and purposes, or (if he used words) to speak the truth. If he spoke and said: this is true, he must be believed until proved false; if he said: this I will do, as you bid, he must be allowed the opportunity to fulfill his promise.
The force and restraint that were used upon Melkor by the united power of all the Valar, were not used to extort confession (which was needless); nor to compel him to reveal his thought (which was unlawful, even if not vain). He was made captive as a punishment for his evil deeds, under the authority of the King. So we may say; but it were better said that he was deprived for a term, fixed by promise, of his power to act, so that he might halt and consider himself, and have thus the only chance that mercy could contrive of repentance and amendment. For the healing of Arda indeed, but for his own healing also. Melkor had the right to exist, and the right to act and use his powers. Manwe had the authority to rule and to order the world, so far as he could, for the well-being of the Eruhíni; but if Melkor would repent and return to the allegiance of Eru, he must be given his freedom again. He could not be enslaved, or denied his part. The office of the Elder King was to retain all his subjects in the allegiance of Eru, or to bring them back to it, and in that allegiance to leave them free.
Therefore not until the last, and not then except by the express command of Eru and by His power, was Melkor thrown utterly down and deprived for ever of all power to do or to undo.