Multi-Attribute Reverse Auctions (MARAs) allow negotiation between the buyer and sellers over price along with other non-price attributes such as delivery time, sellers' reputation, and product quality. The seller with the most preferable product speci cation over multiple attributes wins. Much research has been done in the con- text of MARAs, but several challenging problems still need to be addressed. Eliciting the buyer's requirements, which consist of constraints and preferences, and deter- mining the winner, which has been shown to be computationally complex, are hot research topics. Multi-Attribute Utility Theory (MAUT), which has been used in MARAs, only permits the buyer to specify his preferences quantitatively. Often, the buyer is more comfortable expressing his preferences about the product qualitatively. Moreover, there should be options for the buyer to specify constraints. As well, the constraints and preferences can both be non-conditional or conditional. On the other hand, for the purpose of e ciency, it is more suitable for the auction systems to process quantitative data. Hence, there are remaining challenges to provide the buyer with more comfort as well as to keep the system e cient. Motivated by these issues, we develop a novel MARA protocol in which the buyer can specify his non- conditional and conditional constraints as well as qualitative non-conditional and conditional preferences. Moreover, we enhance MAUT by incorporating new algo- rithms and conversion methods that can convert qualitative values into quantitative ones. In this way, we not only provide the buyer with more comfort, but also keep the system e cient. We design the MARA protocol with 3-layer software architec- ture based on the Multi-Agent technology and the Belief-Desire-Intention model. We implement it using the agent simulation framework named Jadex. The system assists the buyer to specify his requirements step by step through friendly graphical user interfaces and assists the sellers to submit bids. We conduct a case study of a re- verse auction over ten attributes to demonstrate the feasibility of our MARA system. We report on a series of experiments that show that the system is able to elicit the buyer's requirements adequately and to determine the winner e ciently, in terms of processing time. ii