Development of a competitive automated negotiating agentDevelopment of a competitive automated negotiating agentΔημιουργία ανταγωνιστικού πράκτορα για αυτοματοποιημένες διαπραγματεύσεις Διπλωματική Εργασία Diploma Work 2020-02-252020enRational players negotiate in many real-life domains, such us the Smart Grids, health care, business and various economics environments in several. The optimal agreement to be reached from a negotiation is the one that best represents the player’s desires. A new challenge for negotiating autonomous agents is having limited or uncertain prior information about the preferences of the user they represent, as for example is demanded by the rules of the international Autonomous Negotiation Agents Competition (ANAC). This thesis aims to develop an agent which is able to negotiate given partial information about the user’s preferences, and can thus participate in ANAC. We present the design of an agent which builds mostly on the work of Srinivasan and Shocker (1973) and Tsimpoukis et al (2019). Our agent calculates its utility space from partial information based on categorical data in the form of pairwise comparisons of outcomes, instead of precise utility information. Moreover, our approach uses linear optimization for the estimation and translation of the partial information into utility estimates, by deploying the simplex algorithm. The strategy of our opponent modeling component is inspired by the Thomas-Kilmann Conflict Mode Instrument (TKI), which predicts the opponent’s strategy based on earlier counter-offers or an experience profile, as detailed in the work of Fujita (2016). Our acceptance strategy is based on the definition given by Fujita (2016), and its values corresponding to possible outcomes of the agent’s utility space. We tested our method in eleven different negotiation scenarios using four or sometimes five different domains. The strategy of our method and certain variants are deployed utilizing the well-known negotiation GENIUS platform. The negotiation tournaments that took place, involved agents with limited prior information, and also agents with complete prior information about their preference profiles. Negotiating agents that participated in past ANAC competitions comprise the agents with known preference profiles that were pitted against our agent. We conduct a systematic experimental evaluation, which demonstrates that our methodology has the ability to estimate the utility space from partial information with remarkable proximity to the real utility space. The results also verify that the algorithm’s acceptance strategy is working well while our agent accept bids based on its set acceptance threshold. Unsurprisingly, our results also demonstrate the unfairness of pitting agents with uncertain preferences against agents with known preferences. Finally, based on a close examination of our agent’s behavior during the simulations, we infer that we can improve its performance by making its acceptance strategy less cooperative.Ορθολογικοί παίκτες διαπραγματεύονται σε πολλά πεδία στην πραγματική ζωή όπως για παράδειγμα σε ευφυή δίκτυα, τον υγειονομικό τομέα, στις επιχειρήσεις και γενικά σε περιβάλλοντα που συσχετίζονται με τα οικονομικά. Η βέλτιστη συμφωνία η οποία μπορεί να αποκτηθεί από μία διαπραγμάτευση αντιπροσωπεύει με τον καλύτερο τρόπο τις επιθυμίες ενός παίκτη. Μία νέα πρόκληση για τους αυτόνομους πράκτορες που διαπραγματεύονται είναι να έχουν ελλιπή ή αβέβαιη πληροφορία για τις προτιμήσεις ενός χρήστη που αντιπροσωπεύουν, όπως απαιτείται για να συμμετάσχει στον παγκόσμιο διαγωνισμό αυτόνομων πρακτόρων (ANAC). Η συγκεκριμένη διπλωματική εργασία έχει ως στόχο να αναπτύξει ένα πράκτορα ο οποίος είναι ικανός να διαπραγματεύεται με δοθείσα περιορισμένη πληροφορία σχετικά με τις προτιμήσεις ενός χρήστη, και στην συνέχεια να μπορεί να συμμετάσχει στον διαγωνισμό ANAC. Στην εργασία παρουσιάζεται ο σχεδιασμός του πράκτορα ο οποίος βασίστηκε στις εργασίες των Srinivasan and Shocker (1973) και Tsimpoukis et al (2019). Ο πράκτορας υπολογίζει το διάστημα χρησιμότητας του (utility space), έχοντας περιορισμένες πληροφορίες στην μορφή κατηγορικών δεδομένων που προέρχονται μέσω συζευκτικής σύγκρισης αποτελεσμάτων, αντί για τις ακριβείς πληροφορίες χρησιμότητας. Χρησιμοποιούμε γραμμική βελτιστοποίηση για τον υπολογισμό των μερικών πληροφοριών και την μετατροπή τους σε υπολογισμούς τιμών χρησιμότητας, εφαρμόζοντας τον γνωστό αλγόριθμο simplex. Η στρατηγική μοντελοποίησης του αντιπάλου είναι εμπνευσμένη από το Tomas-Kilmann conflict mode Instrument (ΤΚΙ) γνωστό και ως ερωτηματολόγιο διάγνωσης προσεγγίσεων το οποίο προβλέπει την στρατηγική του αντιπάλου βασισμένο σε παλιότερες συγκρούσεις ή ένα εμπειρικό προφίλ όπως περιγράφεται στην έρευνα του Fujita (2016). Τέλος, η στρατηγική αποδοχής του αλγορίθμου βασίζεται στον ορισμό που έχει προταθεί απο τον Fujita (2016), με τις τιμές της να αντιστοιχούν είναι πιθανά αποτελέσματα του πεδίου χρησιμότητας του πράκτορα. Η προτεινόμενη μέθοδος αξιολογείται σε έντεκα διαφορετικά σενάρια χρησιμοποιώντας τέσσερα και μερικές φορές πέντε διαφορετικά πεδία διαπραγματεύσεων. Η στρατηγική της μεθόδου μας και διάφορες παραλλαγές της δοκιμάστηκαν σε μία πολύ γνωστή πλατφόρμα διαπραγματεύσεων, το GENIUS. Έλαβαν χώρα πρωταθλήματα διαπραγματεύσεων τα οποία συμπεριέλαβαν πράκτορες τόσο με τέλεια πληροφορία, όσο και με ελλιπή ενημέρωση σχετικά με το προφίλ προτιμήσεων τους. Ως αντίπαλοι με τέλεια πληροφόρηση για τις προτιμήσεις τους, χρησιμοποιήθηκαν πράκτορες οι οποίοι διαγωνίστηκαν σε παλαιότερους διαγωνισμούς του ANAC. Διεξήχθη μία συστηματική πειραματική αξιολόγηση η οποία παρουσιάζει την ικανότητα της μεθόδου μας να υπολογίζει το πεδίο χρησιμότητας που προέρχεται από ελλιπή πληροφόρηση με εξαιρετική εγγύτητα στο πραγματικό πεδίο χρησιμότητας. Τα αποτελέσματα επίσης επιβεβαιώνουν ότι η στρατηγική αποδοχής του αλγόριθμου δέχεται προσφορές βασισμένες στο όριο αποδοχής το οποίο τέθηκε. Επιπρόσθετα, στα αποτελέσματα επίσης υπογραμμίζεται το πόσο άδικο είναι να ανταγωνίζονται πράκτορες οι οποίοι γνωρίζουν τις ακριβείς προτιμήσεις τους με πράκτορες με ελλιπή αρχική πληροφορία. Η προσεκτική παρατήρηση της συμπεριφοράς του πράκτορά μας και η αποτίμηση των αποτελεσμάτων των πειραμάτων μας, μας οδηγεί στο συμπέρασμα πως μια λιγότερο συνεργατική (περισσότερο συντηρητική) στρατηγική αποδοχής προσφορών θα βελτίωνε την αποτελεσματικότητα της μεθόδου μας.http://creativecommons.org/licenses/by-nc-nd/4.0/Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών ΥπολογιστώνZiogas_Ioannis-Panagiotis_Dip_2020.docxZiogas_Ioannis-Panagiotis_Dip_2020.pdfChania [Greece]Library of TUC2020-02-24Chania [Greece]Library of TUC2020-02-25application/vnd.openxmlformats-officedocument.wordprocessingml.documentapplication/pdf2.6 MB1.2 MBcampuscampusZiogas_Ioannis-Panagiotis_Dip_2020.docxZiogas_Ioannis-Panagiotis_Dip_2020.pdfChania [Greece]Library of TUC2020-02-24Chania [Greece]Library of TUC2020-02-25application/vnd.openxmlformats-officedocument.wordprocessingml.documentapplication/pdf2.6 MB1.2 MBcampuscampus Ziogas Ioannis-Panagiotis Ζιωγας Ιωαννης-Παναγιωτης Chalkiadakis Georgios Χαλκιαδακης Γεωργιος Samoladas Vasilis Σαμολαδας Βασιλης Deligiannakis Antonios Δεληγιαννακης Αντωνιος Πολυτεχνείο Κρήτης Technical University of Crete Autonomous negotiation agents competition Negotiation Automated agent