In this paper we present a negotiation agent based on Genetic Algorithm (GA) and Surrogate Modelling for a multi-player multi-issue negotiation model under incomplete information scenarios to solve a resource-allocation problem. We consider a multi-lateral negotiation protocol by which agents make offers sequentially in consecutive rounds until the deadline is reached. Agents' offers represent suggestions about how to divide the available resources among all agents participating in the negotiation. Each agent may “Accept” or “Reject” the offers made by its opponents through selecting the “Accept” or “Reject” option. The GA is used to explore the space of offers and surrogates used to model the behaviours of individual opponent agents for enhanced genetic evolution of offers that is agreeable upon all agents. The GA population comprises of solution individuals that are formulated as matrices where a specialised three different search operators that take the matrix representation into considerations are considered. Experimental studies of the proposed negotiation agent under different scenarios demonstrated that the negotiations by the agents completed in agreement before the deadline is reached, while at the same time, maximising profits.