Since participants in a computational Grid may be independent bodies, some mechanisms are necessary for resolving their differences. The contribution of this work is designing a bargaining protocol for agents representing Grid participants in negotiating for computational resources. The protocol in this work discerns from existing protocols because agents in this work are programmed to follow a set of fuzzy rules for relaxing bargaining terms with the hope of increasing their chance of successfully acquiring resources before their deadlines. This relaxed-criteria bargaining protocol and an agent-based testbed for simulating Grid resource allocation were implemented in Java 1.5. A series of simulations was carried out using the testbed, and favorable (preliminary) empirical results show that following the relaxed-criteria bargaining protocol, agents achieved higher success rates in negotiating for resources.