**COMP6203: Lab #4** Intelligent Agents _Wednesday, 7 November 2018_ University of Southampton _[Go to Lab Index]("../index.html")_ This lab shows how to evaluate your agent against various benchmark metrics. # Theory Crash Course There are multiple quality metrics that can help you to analyse your negotiating agent: ## Definitions * **A negotiation session**: A single run of a negotiation, beforehand the names of agents, which preference profiles that they are assigned to and some other parameters needs to be given to make a single run. * **A tournament**: Consists of many negotiation sessions. A tournament takes a set of negotiation agents, a domain (with many preference profiles.) and some parameters to determine negotiation sessions such as: * Deadline * Repetitions (_repetition of a negotiation session_) * Data Persistency (_access to data of the previous negotiation sessions_) * Protocol ## Quality Metrics ### Individual Utility The utility that is gained from the perspective of an agent. For Agent A, for instance it is: \begin{equation} U_{A}(b_{accepted}) = \sum_{i=1}^{n} \omega_i \frac{eval(v^{i}_{c_i})}{max(eval(I_i))} \end{equation} $b_{accepted}$ is the accepted bid that is accepted by everybody. !!! note If in the negotiation environment: * the protocol is SAOP * an agent walks-away * or deadline is reached Everyone gets their reservation value (if discounted, they get discounted reservation value) as their own individual utility. ### Social Welfare _Defined in [MultilateralAnalysis.java:299](https://tracinsy.ewi.tudelft.nl/pubtrac/Genius/browser/src/main/java/genius/core/analysis/MultilateralAnalysis.java#L299)_: The social welfare (SW) is the sum of all the individual utilities of all agents. For a bid $b$ and $n$ agents, this is: \begin{equation} SW(b) = \sum_{i=1}^{n} U_{i}(b) \end{equation} ### Distance to Pareto Efficient Frontier _Defined in [MultilateralAnalysis.java:322](https://tracinsy.ewi.tudelft.nl/pubtrac/Genius/browser/src/main/java/genius/core/analysis/MultilateralAnalysis.java#L322)_: The accepted bid's distance to the Pareto efficient frotnier. ![Figure [pareto]: Available bids in the pareto frontier](pareto.png width="500px") _"A negotiation outcome is said to be Pareto efficient if there is no other outcome that will make at least one agent better off without making at least one other agent worse off. Intuitively, if a negotiation outcome is not Pareto efficient, then there is another outcome that will make at least one agent happier while keeping eve- ryone else at least as happy."_ [#Jennings2001] The Pareto efficient frontier (or simply Pareto frontier or Pareto curve) is the set of all Pareto efficient outcomes. The distance is calculated by getting all the bids which are on the curve. Iterating each bid and getting minimum distance, formally (following example Figure [pareto]): \begin{equation} ParetoDist(b) = min(\{||U(b) - U(b_{1})||, ..., ||U(b) - U(b_{j})||, ..., ||U(b) - U(b_{k})||\}) \end{equation} where $b_k$ is an outcome/bid on the Pareto frontier, $k$ is the number of outcomes on the pareto frontier, and $||U(b_{i}) - U(b_{j})||$ is the Euclidean distance between two bids and $U(b_{i})$ is a tuple that holds each utility that each agent would gain from bid $b_{i}$, such that: \begin{equation} U(b) = (U_1(b), ..., U_n(b)) \end{equation} The [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance) is calculated by: \begin{equation} ||U(b)-U(b')||=\sqrt{\sum_{i=1}^n (U_i(b)-U_i(b'))^2} \end{equation} ### Distance to Nash Point _Defined in [MultilateralAnalysis.java:313](https://tracinsy.ewi.tudelft.nl/pubtrac/Genius/browser/src/main/java/genius/core/analysis/MultilateralAnalysis.java#L313)_: The Nash point is also known as the Nash bargaining solution (NOT to be confused with Nash equilibrium), and this is the point which maximises the product of the utilities minus the disagreement utility. Formally, the Nash bargaining solution or Nash point is calculated by: \begin{equation} b_{nash} = \arg\max_{b} \prod_{i=1}^n \left(U_i(b)-U_i(b_{disagr})\right) \end{equation} where $U_i(b_{disagr})$ is the disagreement utility, i.e. the utility agent $i$ receives if there is no agreement (this is zero if there is the reservation value is zero). To see how this point is found, have a look at its implementation ([MultilateralAnalysis.java:333](https://tracinsy.ewi.tudelft.nl/pubtrac/Genius/browser/src/main/java/genius/core/analysis/MultilateralAnalysis.java#L333)) in GENIUS. Once the distance is found, the Euclidean distance is again calculated between the accepted bid $b_{a}$ and $b_{nash}$. # Task 1: Run a simple tournament and plot these metrics 1. Open the GENIUS user interface 2. Create a new tournament with these settings: ![Figure [tournament]: Tournament settings](tournament.png width="1000px") 3. Locate the logs: e.g. `ExampleAgent/genius-{version}/log/tournament-*.(xml|log)` 4. Open `tournament-*.logStats.xml`, you can find the mean results of the metrics that we mentioned. * While you are developing your agent, you can check these for your agents performance Try to get familiar on how to plot these results (MS Excel, Numbers, matplotlib, Matlab) # Task 2: Parse tournament-*.log.xml, calculate additional metrics 1. You can calculate **the standard deviation** of each these metrics to see how much the mean performance deviates. * You can use a scripting language to parse the log files. * You can use MS Excel with `tournament-*log.csv` directly with pivot tables. * More on this is in Genius User Guide. 2. (Extra) Try to come up with additional metrics. Some tips: * How is your agent performing under: * big/small domains many issues and values) * discrete, continuous issues * and so on. !!! note Running tournaments from command line. You can define multiple tournaments in `an xml file` and GENIUS can run them. Have a look at the GENIUS User Guide Section 5.3 and [here](https://github.com/tdgunes/ExampleAgent/wiki/Running-a-negotiation-session-via-command-line). # Bonus Task: Compute & plot pareto efficient frontier Compute and draw pareto efficient frontier of two random preference profiles from laptop domain in a graph such as Figure [pareto]. ## _Hints_ 1. X axis can be for Agent 1, Y axis can be for Agent 2's utilities. 2. You can use `matplotlib` for this task. For example, for a simple scatter plot: 3. **Suggestion:** You can use [Google Colabratory](https://colab.research.google.com), if you don't know how to install `Python` and `matplotlib`. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~python import matplotlib.pyplot as plt # for instance: # X = [0.3, ...,] # Y = [0.6, ...,] # TODO: get X and Y, plot: plt.plot(X, Y, "yo") # yo = yellow dot # TODO: calculate pareto efficient frontier points as X_p and Y_p, plot: plt.plot(X_p, Y_p, "bs") # bs = blue square plt.xlabel("Agent 1") plt.ylabel("Agent 2") plt.show() ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3. Confirm that you points (shown as blue squares) are the pareto efficent frontier. # Bibliography [#Jennings2001]: Jennings, N. R., Faratin, P., Lomuscio, A. R., Parsons, S., Wooldridge, M. J., & Sierra, C. (2001). Automated negotiation: prospects, methods and challenges. Group Decision and Negotiation, 10(2), 199-215. http://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/gdn2001.pdf