API tools faq
paste
Advertisement
Sax

MAS Study Guide

Sax
Mar 9th, 2017
489
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Latex 33.47 KB | None | 0 0
raw download clone embed print report
  1. \documentclass[titlepage, letterpaper, fleqn]{article}
  2. \usepackage[utf8]{inputenc}
  3. \usepackage{fancyhdr}
  4. \usepackage{amsmath}
  5. \usepackage{extramarks}
  6. \usepackage{enumitem}
  7. \usepackage{amssymb}
  8. \usepackage{booktabs}
  9. \usepackage{tcolorbox}
  10. \usepackage{gensymb}
  11. \usepackage{booktabs}
  12. \usepackage{graphicx}
  13. \usepackage{caption}
  14.  
  15. \topmargin=-0.45in
  16. \evensidemargin=0in
  17. \oddsidemargin=0in
  18. \textwidth=6.5in
  19. \textheight=9.0in
  20. \headsep=0.25in
  21. \setlength{\parskip}{1ex}
  22. \setlength{\parindent}{0ex}
  23.  
  24. %
  25. % You should change this things~
  26. %
  27.  
  28. \newcommand{\mahclass}{Multi-Agents Systems}
  29. \newcommand{\mahtitle}{Study Guide}
  30. \newcommand{\mahdate}{\today}
  31. \newcommand{\spacepls}{\vspace{5mm}}
  32.  
  33. %
  34. % Header markings
  35. %
  36.  
  37. \pagestyle{fancy}
  38. \lhead{Study Guide}
  39. \chead{}
  40. \rhead{}
  41. \lfoot{}
  42. \rfoot{}
  43.  
  44.  
  45. \renewcommand\headrulewidth{0.4pt}
  46. \renewcommand\footrulewidth{0.4pt}
  47. \renewcommand{\familydefault}{\sfdefault} %The sans-serif font and the like
  48.  
  49. % Alias for the Solution section header
  50. \newcommand{\solution}{\textbf{\large Solución}}
  51.  
  52. %Alias for the new step section
  53. \newcommand{\steppy}[1]{\textbf{\large #1}}
  54.  
  55. %
  56. % My actual info
  57. %
  58.  
  59. \title{
  60. \vspace{1in}
  61. \textbf{Tecnológico de Monterrey} \\
  62. \vspace{0.5in}
  63. \textmd{\mahclass} \\
  64. \vspace{0.5in}
  65. \textsc{\mahtitle}
  66. \author{01170065  - MIT \\
  67. Xavier Fernando Cuauhtémoc Sánchez Díaz \\
  68. \texttt{xavier.sanchezdz@gmail.com}}
  69. \date{\mahdate}
  70. }
  71.  
  72. \begin{document}
  73.  
  74. \begin{titlepage}
  75.    \maketitle
  76. \end{titlepage}
  77.  
  78. %
  79. % Actual document starts here~
  80. %
  81.  
  82. \section{Agent Architectures}
  83.  
  84. \subsection{What is an Agent and Environment types}
  85.  
  86. An \textbf{Agent} is a computer system capable of autonomous action in some \textbf{Environment} in order to meet its design objectives.
  87.  
  88. \textbf{Environments} can be classified in many ways:
  89.  
  90. \begin{itemize}
  91.    \item \textbf{Accessible} or \textbf{inaccessible}.
  92.    \item \textbf{Deterministic} or \textbf{non-deterministic}.
  93.    \item \textbf{Static} or \textbf{dynamic}.
  94.    \item \textbf{Discrete} or \textbf{continuous}.
  95. \end{itemize}
  96.  
  97. An \textbf{accessible} environment is one in which the agent can obtain complete, accurate, up-to-date information about the environment's state.
  98. On the other hand, an \textbf{inaccessible} environment is one in which the agent can't obtain all this info. E.g. the Internet is an inaccesible environment for all of us!
  99.  
  100. An environment can also be \textbf{deterministic} if any action (of the agents) has a single guaranteed effect – there is no uncertainty about the state that will result from performing an action.
  101. This means that for each action there is a single (JUST ONE) state of the environment. If there's more than one state, then it is \textbf{non-deterministic}.
  102. Remember about the waves of the sea or the braking example: even if the agent does an action, there could be MORE THAN ONE final result.
  103.  
  104. A \textbf{static} environment is one that changes its states ONLY by the action of an agent. A Tetris game is static, because the environment only changes with our actions.
  105.  
  106. A \textbf{dynamic} environment is the opposite: an environment which changes EVEN IF an agent does nothing.
  107.  
  108. Another way to classify environments is depending on the \texttt{cardinality} of its set of possible states (the \textit{size} of the set, how many elements it has).
  109. If the environment has a finite cardinality (a natural number of elements), then it is considered as \textbf{discrete}. A Rubik's cube, even if it has TRILLIONS of combinations, it is a finite number. Thus, the Rubik's cube is a discrete environment.
  110.  
  111. BUT IF AN ENVIRONMENT'S CARDINALITY IS THE SAME CARDINALITY OF THE SET OF NATURAL NUMBERS (if it's infinite) then this environment is a \textbf{continuous} environment.
  112.  
  113. \subsection{How to describe a set}
  114.  
  115. The set notation is useful for describing an agent's actions, environment's states or state transformers. To describe a set, you usually use CAPITAL LETTERS. If it's a set of agent actions, usually you'll use \(A\) or if it's a set of environment states you could use \(E\).
  116. After that, you'll use \{ and then list all elements using lower-case letters (use \(a, \alpha\) or \(e\) with a sub-index if there's no need to describe the actual action/state). Put \} at the end to mark the END of the elements and thus delimiting your set. Like this:
  117. \[A=\{a_0, a_1, a_2, a_3, ..., a_n\}\]
  118.  
  119. \pagebreak
  120.  
  121. \subsection{How to describe a run}
  122.  
  123. Runs are described as a SEQUENCE of environment STATES that are altered via an agent's ACTION. To describe a run, we usually use (yeah, we usually use) lowercase \(r\), followed by the \texttt{such as} operator (a colon, :). After that, we need to write the state, then an arrow with the action that modifies that state, in order to get to ANOTHER state, and so on. Like this:
  124.  
  125. \[r : e_0 \xrightarrow{\alpha_0} e_1 \xrightarrow{\alpha_1} e_2 \xrightarrow{\alpha_2} e3 \xrightarrow{a_3} \dots \xrightarrow{a_{n-1}} e_n\]
  126.  
  127. \begin{tcolorbox}
  128.    REMEMBER, KIDDO: the number of iterations depends on the number of ACTIONS, not states. If you're asked to do a 5 second run using an action per second, you should use 5 actions and thus end up with 6 environment states.
  129. \end{tcolorbox}
  130.  
  131. \subsection{How to describe a State Transformer Function}
  132.  
  133. Now this is a little bit trickier. First of all, you should know what a state transformer function is. It is a FUNCTION that represents BEHAVIOR of the environment. It looks something like this when you define it:
  134. \[\tau : \mathcal{R}^{Ac} \rightarrow \wp (E)\]
  135.  
  136. NOW WAIT A SECOND. This is perhaps too much to handle, but no, it isn't.
  137. \begin{itemize}
  138.    \item \(\tau\) is TAU, a Greek letter that refers to the state transformer function.
  139.    \item \(:\) means that this is a function MAPPING what is on the right of the arrow to what is on the left of the arrow (even if : meant something else for runs, this is complete BS).
  140.    \item \(\mathcal{R}^{Ac}\) is the left side, which is a SET OF RUNS which end with an action.
  141.    \item \(\wp\) means the POWER SET of whatever is next to \(\wp\) (to the right). A power set is A SET which contains ALL POSSIBLE SUBSETS of whatever is next. By definition, its cardinality is \(2^n\), where \(n\) is the number of elements in the original set (whatever is next to \(\wp\)).
  142.    \item \(E\) is the SET of Environment states.
  143. \end{itemize}
  144.  
  145. SO ALL OF THIS MEANS that you should write down a FUNCTION which RECEIVES an ACTION and then RETURNS A SET, which contains ALL POSSIBLE STATES FOR THAT ACTION.
  146. If \texttt{drinking water} is an action done by me, what could happen to the \texttt{water} is to be \texttt{drunk}, or to be \texttt{spilled} on my keyboard.
  147.  
  148. To write this function, we usually write (yeah, we don't use \textit{use} this time) it like this:
  149.  
  150. \[\tau (\dots , \sigma, \alpha) = \{\sigma_1, \sigma_2, \dots\}\]
  151.  
  152. Where \(\sigma\) is an environment state, and \(\alpha\) is an action. \(\sigma_1\) is one of the possible states that COULD HAPPEN after the \(\alpha\) action (and so on with 2, 3...). You could use any variable instead of alpha. Actually you should use whatever the actions are called in your exam!
  153.  
  154. \pagebreak
  155.  
  156. \section{Game Theory}
  157.  
  158. \subsection{Expected Value and Expected Utility}
  159.  
  160. The \textbf{expected value} is (you can guess, I guess!) the value expected of a transaction or \textit{agreement} between the agents.
  161. The expected value is the sum of the product of the value of each of the possible outcomes by their probability.
  162. Remember the deal or no deal TV show, 5M USD if you guess right, or 0 if you don't, or instead 2M NOW and you don't get to choose any of the suitcases.
  163. This would be calculated as:
  164.  
  165. \begin{align*}
  166.    EV_1 & = (0.5)(5000000) + (0.5)(0) = 2,500,000 \\
  167.    EV_2 & = (1)(2000000) + (0)(0) = 2,000,000
  168. \end{align*}
  169.  
  170. But the expected value is kinda useless, so we often use the \textbf{expected utility}, which is kinda the same, but different.
  171. Each additional unit has less value than the previous one.
  172. Remember the ice cream example, 1 ice cream is incredible in a summer day. 2 are good. 3 are too much. 4 is horrible my stomach can't handle it please stop.
  173.  
  174. \subsection{Representing games}
  175.  
  176. To summarize a story (a game) we used two different approaches.
  177.  
  178. The first approach is the \textbf{game tree} (also called the \textbf{extensive form}).
  179. The game tree uses nodes and branches, and lists (extensively) all the outcomes (utilities for each agent).
  180. To get the solution of the game, one should prune out terminal nodes which have less expected utility than the others in the same branch,
  181. and then keep comparing between the non-pruned branches until getting the solution.
  182. As you can see, this approach is valid IF we know what the other agent is going to do.
  183.  
  184. However, in a simultaneous world, the approach we used was the \textbf{game table} (also called the \textbf{strategic form}).
  185. In this form, you use columns to describe all possible actions for an agent and rows for all possible actions for the other agent (or all other agents that are not me).
  186. Each cell (a row, column tuple) contains the expected utility for each agent.
  187. This is the representation that we used the most.
  188.  
  189. \subsection{Some already defined behaviors in games}
  190.  
  191. There are some games already defined. For example, there are situations in which both agents hate themselves, and in which what an agent chooses will affect the other agent.
  192. This game is called a \textbf{zero-sum game}, because if you sum all the utilities in a single cell you should get 0 lol.
  193.  
  194. The \textbf{Prisoner's Dilemma} is another game already defined, in which the pay-offs are better IFF (if and only if) both agents choose the same.
  195. If they choose different solutions, then a catastrophe is on its way.
  196.  
  197. We also reviewed some other games like the \textbf{Battle of the Sexes}, the \textbf{Chicken} and the \textbf{Battle of Bismarck Sea}. Refresh your memory, young Padawan.
  198.  
  199. \subsection{Dominance}
  200.  
  201. An strategy is dominant IFF we choose this strategy there is no other strategy better than this one. There are two \textit{kinds} of dominance, weak and strict.
  202.  
  203. A \textbf{strictly dominant strategy} is a strategy in which ALL my decisions (not considering what the other agent will do) are the best decisions I could take.
  204. If you're the row player, check each cell against its corresponding column (in another row) to see if the strategy REALLY is better.
  205. If my strategy is ALWAYS better, then it's a strictly dominant strategy.
  206.  
  207. If SOMETIMES it's better and some other times it is the same, then it is \textbf{weakly dominant}.
  208.  
  209. BUT IF SOMETIMES IT'S BETTER AND SOME OTHER TIMES IT`S WORSE THEN IT IS NOT A DOMINANT STRATEGY.
  210.  
  211. If a strategy is not dominant, and there EXISTS a dominant strategy, then that non-dominant strategy is also called a \textbf{dominated strategy}.
  212. The same concepts (weakly and strictly) apply: If there is a weakly dominant strategy, then this strategy is weakly dominated by that dominant strategy.
  213.  
  214. Now, the fun part is when THERE'S NO DOMINANT STRATEGY for EITHER of the agents.
  215. If that happens, you should ELIMINATE dominated strategies until you get a rational solution!
  216.  
  217. \subsection{Nash Equilibrium}
  218.  
  219. The \textbf{Nash Equilibrium} is achieved IFF an agent can't increase its pay-off by changing strategy IF the other agents were to stick with its strategy.
  220. The safest way to determine a Nash Equilibrium is by \textbf{cell-by-cell} inspection.
  221.  
  222. \begin{tcolorbox}
  223.    REMEMBER KIDDO: ask yourself (as an agent): IF the other agent doesn't move, should I move? IF YES, then it is not a Nash Equilibrium point.
  224.    IF NO, then ask the same question for the other agent. IF the answer is NO for both agents, then the cell is a Nash Equilibrium point.
  225. \end{tcolorbox}
  226.  
  227. The \textbf{min-max method} is useful to get the Nash Equilibrium point BUT ONLY FOR ZERO-SUM GAMES.
  228.  
  229. \subsection{Pareto Optimality}
  230.  
  231. A cell is said to be \textbf{Pareto optimal} if, to the eyes of an outsider, that is a preferable outcome.
  232. The easiest way to determine if a cell is Pareto optimal is using the cell-by-cell method.
  233.  
  234. \begin{tcolorbox}
  235. REMEMBER KIDDO: ask yourself (as a non-agent): IF we change the cell, do the agents get hurt? IF YES, then don't change cell!
  236. IF after asking the same for ALL CELLS you're on the same spot, then it is Pareto Optimal!
  237. \end{tcolorbox}
  238.  
  239. \subsection{Mixed Strategies (in Game Theory)}
  240.  
  241. In a mixed strategy, agents have a probability distribution over their actions.
  242.  
  243. \subsubsection{Expected Utility of a Strategy}
  244.  
  245. To calculate the \textbf{expected utility} of an agent strategy,
  246. you should take into account the pay-off of each strategy and multiply by their probability (as you did with expected utility before).
  247.  
  248. \begin{table}[h!]
  249. \centering
  250. \begin{tabular}{@{}ccc@{}}
  251. \toprule
  252.                       & F (0.5)                    & B (0.5)                    \\ \midrule
  253. \multicolumn{1}{c|}{F} & \multicolumn{1}{c|}{90,10} & \multicolumn{1}{c|}{20,80} \\ \cmidrule(l){2-3}
  254. \multicolumn{1}{c|}{B} & \multicolumn{1}{c|}{30,70} & \multicolumn{1}{c|}{60,40} \\ \bottomrule
  255. \end{tabular}
  256. \end{table}
  257.  
  258. The expected utility for the row player is \((0.5)(0.9)+(0.5)(0.2)=55\%\) for F, and \((0.5)(0.3)+(0.5)(0.6)=45\%\) for B,
  259. so the row player should always choose F GIVEN THAT the column player maintains its probability distribution.
  260.  
  261. So, because the row player will always choose F, the expected utility of the Server is BASED ON the fact that the row player's strategy is F:
  262.  
  263. \[(0.5)(0.1) + (0.5)(0.8) = 0.45\]
  264.  
  265. This is already better than 40 (BB), so it is a preferable mixed strategy.
  266.  
  267. \subsubsection{Finding the best probability distribution}
  268.  
  269. \begin{table}[h!]
  270. \centering
  271. \begin{tabular}{@{}ccc@{}}
  272. \toprule
  273.                       & F (q)                    & B (1-q)                    \\ \midrule
  274. \multicolumn{1}{c|}{F} & \multicolumn{1}{c|}{90,10} & \multicolumn{1}{c|}{20,80} \\ \cmidrule(l){2-3}
  275. \multicolumn{1}{c|}{B} & \multicolumn{1}{c|}{30,70} & \multicolumn{1}{c|}{60,40} \\ \bottomrule
  276. \end{tabular}
  277. \end{table}
  278.  
  279. In order to get the best probability distribution for the server (column player),
  280. we should calculate first the expected utility of each strategy of the receiver (row player).
  281.  
  282. \begin{align*}
  283.    EU_{RF} & = (q)(90) + (1-q)(20) \\
  284.    & = 90q + 20 - 20q \\
  285.    & = 20 + 70q \\[2ex]
  286.    EU_{RB} & =(q)(30) + (1-q)(60) \\
  287.    & = 30q + 60 - 60q \\
  288.    & = 60 - 30q
  289. \end{align*}
  290.  
  291. We now solve by equating both equations (yeah boi), so we end up with this:
  292.  
  293. \begin{align*}
  294.    & 20 + 70q = 60 - 30q \\
  295.    & 70q + 30q = 60 - 20 \\
  296.    & 100q = 40 \therefore q = 0.4
  297. \end{align*}
  298.  
  299. Now this is ONLY AN ASSUMPTION. Why, you ask? Well, because we equated both equations. That means that EACH STRATEGY IS INDIFFERENT.
  300. That's right. IF \(q = 0.4\), then the receiver is indifferent between F and B.
  301.  
  302. Now, onto the server side. The equations end up like this:
  303.  
  304. \begin{align*}
  305.    & 80 - 70q = 40 + 30q \\
  306.    & 80 - 40 = 100q \\
  307.    & q = \dfrac{40}{100} \therefore q = 0.4
  308. \end{align*}
  309.  
  310. SO, YES, \(q\) is 0.4. That means \(1-q\) is 0.6, and thus, receiver is, JUST AS PLANNED, indifferent to both strategies.
  311. But we haven't seen if the receiver uses a \(p\) probability for F, and –of course– \(1-p\) for B.
  312.  
  313. For that, the receiver should ASSUME that server alternatives are indifferent.
  314. So calculate for which probability \(p\) the server will be indifferent:
  315.  
  316. \begin{align*}
  317.    & 10p + 70(1-p) = 80p + 40(1-p) \\
  318.    & 10p + 70 - 70p = 80p + 40 - 40p \\
  319.    & 70 - 40 = 80p + 70p - 40p - 10p \\
  320.    & 30 = 100p \therefore p = 0.3
  321. \end{align*}
  322.  
  323. So, \(p=0.3\) in order for server to be indifferent between MY receiving alternatives. You can later check if that's true using MY (receiver's payoff equations) to find \(p\), but it's no use.
  324.  
  325. \begin{tcolorbox}
  326.    REMEMBER KIDDO: If you were to find the probability distribution of an agent, use THE OPPOSING AGENT'S EXPECTED VALUE, not yours!
  327.    E.g. If I want to get \(q\) for the column player, then I should use row's expected value equations.
  328. \end{tcolorbox}
  329.  
  330. \section{Contract Net}
  331.  
  332. A \textbf{Contract Net} is a network of contracts! Guess you didn't expect that, did you?
  333. Since we're dealing with self-interested agents, it's important to note that each agent will act to further their own interests,
  334. and possibly at expense of others. This means that maybe, there is potential \textbf{conflict}.
  335.  
  336. Contract Net can be summarized in this 5 steps:
  337.  
  338. \begin{enumerate}
  339.    \item Recognition
  340.    \item Announcement
  341.    \item Bidding
  342.    \item Awarding
  343.    \item Expediting
  344. \end{enumerate}
  345.  
  346. \subsection{Recognition}
  347.  
  348. In the first stage, the agent recognizes (heh) it needs help to solve a problem. It could either be because the agent can't achieve its goal alone or
  349. because working with the help of other agents will yield a better utility).
  350.  
  351. \subsection{Announcement}
  352.  
  353. The agent with the task sends an \textit{announcement} (heheh) which includes a specification of the task to be achieved.
  354. This announcement should encode a \texttt{description of the task}, if there are any \texttt{constraints} and some additional information
  355. (often referred to as \texttt{meta-task info}).
  356.  
  357. \subsection{Bidding}
  358.  
  359. Ok, you should guess that this step is where every other agent bids, right? That's right.
  360. Those agents that received the announcement decide whether or not they wish to bid for the task.
  361. This wish to bid depends on many factors like if an agent is actually capable of satisfying the constraints of the \textbf{manager} (the agent who sent the announcement).
  362. It can also depend on price information (if relevant).
  363.  
  364. THEN THEY CHOOSE TO BID, and if they DID CHOOSE then they submit a \textbf{tender}.
  365.  
  366. \subsection{Awarding and Expediting}
  367.  
  368. These two are more or less at the same time. The manager needs to decide whom to award the contract to.
  369. Then, the result of his process is communicated to all agents that submitted a bid. The successful contractor then expedites the task, and a contract is made! Voila!
  370.  
  371. \section{Negotiation}
  372.  
  373. Negotiation is a way to coordinate selfish interests. It solves characteristics-form games and more complex versions.
  374. It can also be seen as \textbf{bargaining}. This bargaining problem is defined with some already defined features:
  375.  
  376. \begin{itemize}
  377. \item The \textbf{utility of a deal} is a function mapping a \textbf{real value} to a \textbf{deal}.
  378. \item One of the possible deals is the \textbf{no-deal}.
  379. \item The utility of the no-deal is zero, always.
  380. \end{itemize}
  381.  
  382. ONWARDS TO THE MATHEMATICAL NOTATION SYSTEMS! To represent the utility we use a lower-case \(u\) with a sub-index \(i\) for the sake of generalization, like this: \(u_i\)
  383.  
  384. As we previously stated, the utility of a deal can be seen as a FUNCTION. So we define it as follows:
  385.  
  386. \[u_i : \Delta \rightarrow \mathbb{R}\]
  387.  
  388. Where \(u_i\) is the expected utility of a deal, \(\Delta\) is the set of all possible deals, and \(\mathbb{R}\) is the set of all real numbers
  389. (that means, any non-imaginary numerical value). Remember that the colon (:) assigns what is to the right of the arrow to what is on its left.
  390.  
  391. Because \(\Delta\) is the set of all deals, then \(\delta_i\)  (or \(\delta'\)) is any possible deal. Using \(d\) instead of lower-case delta is also common.
  392. To refer to the no-deal, we use \(\delta^-\).
  393.  
  394. \begin{tcolorbox}
  395.    REMEMBER KIDDO: \(u_i(\delta^-) = 0\), ALWAYS, FOR BOTH AGENTS.
  396. \end{tcolorbox}
  397.  
  398. \subsection{Axiomatic Solution Concepts}
  399.  
  400. \subsubsection{Pareto Optimal deals}
  401.  
  402. As well as in games (since this is also kinda like a game theory analysis from hell), Negotiation deals (no pun intended) with Pareto Optimality.
  403. A deal \(\delta\) is \textbf{Pareto optimal} if there is NO OTHER DEAL such that everyone prefers it over \(\delta\).
  404. This means that there is no \(\delta'\) such that
  405.  
  406. \[\forall_i u_i(\delta') > u_i(\delta)\]
  407.  
  408. which reads as: FOR ALL DEALS, the utility of that deal is better than the deal I'm currently analyzing. THAT'S WHAT WE DON'T WANT.
  409. IF there exists AT LEAST ONE which is better FOR BOTH AGENTS, then it's not Pareto optimal.
  410.  
  411. \begin{tcolorbox}
  412.    REMEMBER KIDDO: Ask yourself (as a non-agent): does moving to another deal hurt anyone? IF YES, then don't change deal!
  413.    Keep asking the same question for ALL OTHER DEALS. If at the end you're still on the same deal, then it is Pareto Optimal!
  414. \end{tcolorbox}
  415.  
  416. \subsubsection{Pareto Frontier}
  417.  
  418. There's also another concept involving Pareto optimal deals, which is the \textbf{Pareto frontier}.
  419. The Pareto frontier is the set of ALL DEALS which are Pareto optimal.
  420. These, when plotted, look like a line on top of the other deals, which is the upper-rightmost set of points. Like a frontier, you know.
  421.  
  422. This set of deals is also called the \textbf{negotiation set}, since its elements are the best deals available and all rational agents will look for
  423. the \textit{very best} of these deals.
  424.  
  425. \subsubsection{Symmetry}
  426.  
  427. The concept of \textbf{Symmetry} applies to negotiation protocols. The protocol is said to be symmetric if the solution remains the same as long
  428. as the set of utility functions \(U\) remains the same, regardless of which agent has which utility.
  429.  
  430. \begin{tcolorbox}
  431.    REMEMBER KIDDO: a protocol is symmetric IF and ONLY IF you switch the utility functions between agents, the solution is the same.
  432.    Think about equality. All of us citizens have the same RIGHTS, FREEDOM, 'MURICA.
  433. \end{tcolorbox}
  434.  
  435.  
  436. \subsubsection{Individual Rationality}
  437.  
  438. The concept of \textbf{individual rationality} applies to DEALS. A deal \(\delta\) is individually ration if:
  439.  
  440. \[\forall_i u_i(\delta) \ge u_i(d^-)\]
  441.  
  442. This mathematically beautiful and complex assumption means that a deal is individually rational if, by itself, is rational (duh).
  443. What we consider rational here is a value greater or equal to the value of the no-deal, which is always 0.
  444. So ANY DEAL with positive utility is individually rational. Or you can say that \(u_i(\delta) \in \mathbb{R^+}\)
  445. but the easiest way to remember all of this is that any deal yielding a positive utility it's individually rational.
  446.  
  447. \subsubsection{Independence from Irrelevant Alternatives}
  448.  
  449. This one is tricky. The \textbf{independence from irrelevant alternatives} applies to negotiation protocols.
  450. A negotiation protocol is independent from irrelevant alternatives if it's true that when given \(\Delta\) it chooses \(\delta\),
  451. AND when given \(\Delta' \subset \Delta \) where \(\delta \in \Delta'\),
  452. the protocol STILL chooses \(\delta\) assuming \(U\) stays the same.
  453.  
  454. This is kinda confusing at first, but gets easy if you think about it:
  455. \(\delta\) is the deal, \(\Delta\) is the set of deals, and \(U\) the set of utility functions for all deals.
  456. If you take a sample of the deals, another set of deals (which we call \(\Delta'\)) which also contains the deal we're analyzing,
  457. the protocol will still choose that deal as the winning deal. BUT since \(\Delta'\) can be any subset, this condition should hold TRUE
  458. for ANY subset of \(\Delta\).
  459.  
  460. \begin{tcolorbox}
  461.    REMEMBER KIDDO: a protocol is independent of irrelevant alternatives if,
  462.    after choosing the best deal, you remove a \textit{bad} deal and the solution is the same.
  463.    Keep removing bad deals until you stay with the best deal, the winning one.
  464.    If the winning deal is ALWAYS the same, then the protocol is independent of irrelevant alternatives!
  465. \end{tcolorbox}
  466.  
  467. \subsubsection{Egalitarian Solution}
  468.  
  469. An \textbf{egalitarian solution} is formally defined as follows:
  470.  
  471. \[\delta = \arg \max_{\delta'\in E}\sum_i u_i(\delta')\]
  472.  
  473. where \(E\) is the set of all deals where all agents receive the same utility, namely
  474.  
  475. \[E = \{\delta \vert \forall_{ij}u_i(\delta) = u_j(\delta)\}\]
  476.  
  477. Blah blah, read the kiddo tip below.
  478.  
  479. \begin{tcolorbox}
  480.    REMEMBER KIDDO: an egalitarian solution is a solution where ALL AGENTS receive the SAME utility.
  481.    When plotted, the solution should be in a (theoretical) line that looks like \(f(x)=x\) (that is a straight, 45\degree line).
  482. \end{tcolorbox}
  483.  
  484. \subsubsection{Egalitarian Social Welfare Solution}
  485.  
  486. An \textbf{egalitarian social welfare solution} is formally defined as follows:
  487.  
  488. \[\delta = \arg \max_{\delta} \min_{i} u_i(\delta)\]
  489.  
  490. This means PICK the DEAL which MINIMUM UTILITY is BIGGER. Does this make sense?
  491. \begin{tcolorbox}
  492.    REMEMBER KIDDO: Check all the deals, and pick the one that has the GREATER MINIMUM UTILITY.
  493.    That means, in all deals one agent could win less. Based on the agent that loses a little bit, pick the greater.
  494. \end{tcolorbox}
  495.  
  496. \subsubsection{Utilitarian Solution}
  497.  
  498. This solution is based on the utility of the deals, really easy to grasp. Formally, is like this:
  499.  
  500. \[\delta = \arg \max \sum_i u_i (\delta)\]
  501.  
  502. which means that you should pick the deal with the greatest utility.
  503. It doesn't matter if it's 100 + 1 for agent 1 and 2 respectively, if that solution is better than 100 with 50 + 50, then pick the first one.
  504. No kiddo tip for you here, this is too easy.
  505.  
  506. \begin{tcolorbox}
  507.    Just kidding.
  508.    REMEMBER KIDDO: the \textbf{utilitarian solution} can be easily checked in a plot with a \textit{moving}, diagonal line with a
  509.    negative slope of -45 \degree (\(f(x) = -x\)).
  510.    Keep moving this theoretically invisible line towards the origin (0,0) until you touch a deal. That first deal you just touched, that is the utilitarian solution.
  511. \end{tcolorbox}
  512.  
  513. \subsubsection{Nash Bargaining Solution}
  514.  
  515. This solution is interesting. It is formally defined as follows:
  516.  
  517. \[\delta = \arg \max_{\delta'} \prod u_i (\delta')\]
  518.  
  519. The definition of the \textbf{Nash Bargaining Solution} described in common words is
  520. `pick the solution in which the product of the utility for each player is the greater'.
  521. This approach addresses the issue that if one agent gets too little utility, then the other should also get little utility.
  522.  
  523. Some things to remember are described in the kiddo tip below
  524.  
  525. \begin{tcolorbox}
  526.    A Nash bargaining solution is also Pareto efficient, independent of utility units, symmetric and also independent of irrelevant alternatives.
  527.    Cool, isn't it?
  528. \end{tcolorbox}
  529.  
  530. \subsection{Rubinstein's Alternating Offers}
  531.  
  532. This model features two agents (\(i, j\)). At each time step \(t\), one agent proposes a deal \(\delta\).
  533. After that, the other agent can either accept or reject that \(\delta\) deal.
  534. BUT, utilities decrease over time! So you better accept quickly, you greedy seller! YOU IMPERIALIST!
  535. But that's all for \textbf{Rubinstein's Alternating Offers} model.
  536.  
  537. \subsection{Monotonic-concession}
  538.  
  539. A \textbf{monotonic-concession} protocol has some interesting steps:
  540.  
  541. \begin{enumerate}
  542.    \item First both agents propose a deal which maximizes their utility, that is \(\delta_i \leftarrow \arg \max_{\delta} u_i(\delta)\).
  543.    \item After that, each agent receives the other agent's proposal.
  544.    \item THEN each agent CHECKS if the other agent's proposal is better than their own proposal, \(u_i(\delta_j) > u_i(\delta_i)\):
  545.    \begin{enumerate}
  546.        \item IF YES, ACCEPT OF COURSE!
  547.        \item IF NOT, then propose another deal. Of course, this deal has to yield a better utility for the opposing agent, and also needs to be better than not making a deal at all.
  548.    \end{enumerate}
  549.    \item If there is not a solution, go to number 2 and try again!
  550. \end{enumerate}
  551.  
  552. Mathematically speaking, a \textit{better deal} \(\delta'_i\) would be
  553. \(\delta'_i : u_j(\delta') \ge \epsilon + u_j (\delta_i), u_i(\delta'_i) \ge u_i(\delta^-)\)
  554.  
  555. \subsection{Zeuthen Strategy}
  556.  
  557. The \textbf{Zeuthen strategy} works as follows:
  558.  
  559. As an agent:
  560.  
  561. \begin{enumerate}
  562.    \item Propose my best deal.
  563.    \item Receive a proposal.
  564.    \item Calculate the risk of creating conflict by not accepting the other agent's proposal.
  565.    \item If my risk is less than the other agent's risk, then I must concede JUST ENOUGH so that in the next round I don't concede again.
  566.    \item Of course, if no agreement was settled, keep proposing deals that are slightly better for the other agent (goto 2)
  567. \end{enumerate}
  568.  
  569. How do you calculate risk? That's the quotient of the utility loss of ACCEPTING the proposal, over the utility of not conceding and cause conflict. Like this:
  570.  
  571. \[risk_i = \frac{u_i(\delta_i) - ui(\delta_j)}{u_i(\delta_i)}\]
  572.  
  573. Be aware that you need to calculate risk for BOTH AGENTS and then compare the risk of BOTH.
  574.  
  575. There are some interesting features on this strategy, as it is not guaranteed to succeed or to maximize social welfare.
  576. It is, however, guaranteed to terminate, and any agreement will be individually rational and also Pareto optimal. It is also in a Nash equilibrium.
  577.  
  578. \section{Negotiation in Task Oriented Domains}
  579.  
  580. \subsection{Basic concepts}
  581.  
  582. In \textbf{Task Oriented Domains} (abbreviated as TOD), agents have TASKS to achieve, and they look to redistribute those tasks.
  583.  
  584. A TOD is a triple in the form of \(\langle T, Ag, c \rangle\), where \(T\) is the finite set of all possible tasks,
  585. \(Ag\) is the set of participating agents and \(c : \wp (T) \rightarrow \mathbb{R^+}\) (the power set of the set of tasks mapped to a real positive number).
  586.  
  587. Additionally, an \textbf{encounter} is a collection of tasks, of the form \(\langle T_1, \dots , T_n \rangle\) where \(T_i \subseteq T\) for each \(i \in Ag\)
  588. (\(T_i\) is a subset of \(T\) –including \(T\) itself– for each agent).
  589.  
  590. A \textbf{deal} in TOD is a pair in the form of \((D_1, D_2) : D_1 \bigcup D_2 = T_1 \bigcup T_2\)
  591. (such that the union of \(D_1\) and \(D_2\) is the same as the the union of \(T_1\) and \(T_2\)).
  592.  
  593. The \textbf{utility} of a deal is calculated with \(Cost(T_i) - Cost(D_i)\).
  594.  
  595. \subsection{Deception in TODs}
  596.  
  597. \textbf{Deception} occurs because it can benefit the agent in two ways: pretending that you have been given taks that you don't really have,
  598. and pretending NOT to have a task you really have.
  599. The former is called \textbf{phantom or decoy} task, while the latter is a \textbf{hidden} task.
  600.  
  601. \subsection{Mixed Deals in TODs}
  602.  
  603. A \textbf{mixed deal} is, again, a double in the form \((D_1, D_2) : p\).
  604. The agents will perform (\(D_1, D_2\)) with probability \(p\), and the symmetric deal (\(D_2, D_1\)) with probability \(1-p\).
  605.  
  606. For this, we will simplify by assuming both agents agree to the GO HAM OR GO HOME principle:
  607. \textbf{all-or-nothing} means that if I win, you will do all your homework AND MINE, but if I lose I'll have to do yours TOO.
  608.  
  609. The next examples will be hard to explain, hold your horses, KIDDO!
  610.  
  611. \pagebreak
  612.  
  613. \subsubsection{Hiding with mixed all-or-nothing deals}
  614.  
  615. This example shows how to get to that \(\dfrac{3}{8}\) which they agree upon in the figure below.
  616.  
  617. \begin{figure}[h!]
  618. \includegraphics[width=0.5\textwidth]{hiding}
  619. \caption*
  620. \centering
  621. \end{figure}
  622.  
  623. First of all, we need to assume that postmen are going to flip a coin, so the expected utility of both agents (which will do all the job)
  624. is the probability of NOT doing all the job (0.5, because of coin) multiplied by the cost of the job you actually had:
  625. \(EU_1 = (0.5)(8) = 4\).
  626.  
  627. Then, we can analyze what the supposed expected cost and expected utility (in case of not doing the deal) are.
  628. The expected utility is calculated as the cost of what I'm supposed to do, minus the expected cost of doing all the job.
  629.  
  630. \begin{align*}
  631.    EC_1 & = 8p\\[1ex]
  632.    EU_1 & = 6 - 8p\\[2ex]
  633.    EC_2 & = 8(1-p)\\[1ex]
  634.    EU_2 & = 8 - 8(1-p)\\[2ex]
  635.    6-8p & = 8 - 8(1-p)\\
  636.    6-8p & = 8 - 8 + 8p\\
  637.    6 & = 16p \therefore p = \dfrac{6}{16} = \dfrac{3}{8}
  638. \end{align*}
  639.  
  640. Notice how we used \(1-p\) to denote the probability of the other agent doing all the work.
  641.  
  642. The next step consists in getting the expected utility (in case of doing all work, including what he lied about) using the probability we just got:
  643.  
  644. \[EU_1 = 6 - 8\left(\dfrac{3}{8}\right) = 6 - 3 = 3\]
  645.  
  646. The expected utility of doing all the work is LESS than the original expected utility. It really makes no sense to hide your tasks!
  647.  
  648. \subsubsection{Phantom letters with mixed deals}
  649.  
  650. This example shows how to get to that \(\dfrac{3}{4}\) which they agree upon in the figure below.
  651.  
  652. \begin{figure}[h!]
  653. \includegraphics[width=0.5\textwidth]{phantom}
  654. \caption*
  655. \centering
  656. \end{figure}
  657.  
  658. Same here, we need to calculate the expected utility of each agent (which is the same for both).
  659. Remember that EU is the probability of doing all the job multiplied by the cost of doing all the job:
  660. \(EU_1 = (0.5)(12) = 6\).
  661.  
  662. Now we can analyze what the supposed expected cost and expected utility (in case of not doing the deal) are.
  663. Remember, EU is now cost of what I'm supposed to do, minus the expected cost of doing all work.
  664.  
  665. \begin{align*}
  666.    EC_1 & = 12p\\[1ex]
  667.    EU_1 & = 12 - 12p\\[2ex]
  668.    EC_2 & = 12(1-p)\\[1ex]
  669.    EU_2 & = 6 - 12(1-p)\\[2ex]
  670.    12-12p & = 6 - 12(1-p)\\
  671.    12 -12p & = 6 - 12 + 12p\\
  672.    12 + 6 & = 12p + 12p\\
  673.    18 &= 24p \therefore p = \dfrac{18}{24} = \dfrac{3}{4}
  674. \end{align*}
  675.  
  676. Now, let's check against the ACTUAL, REAL expected utility in case of doing all work (lying agent).
  677. Notice how if agent 1 does all the work, the actual work would be LESS than what he claimed it to be
  678. (as opposed to hiding letters).
  679.  
  680. \[EU_1 = 6 - 6\left(\dfrac{3}{4}\right) = 6 - \dfrac{18}{4} = 1.5\]
  681.  
  682. Again, lying doesn't work in mixed deals in TOD!
  683.  
  684. \begin{tcolorbox}
  685.    REMEMBER KIDDO: \(EC\) is cost of doing all the job, \(EU\) is COST of doing MY SUPPOSED JOB minus \(EC\).
  686.    Then equate, and get \(p\) (or \(1-p\)). Then use \(p\) to get the supposed EU, it should always be LESS than what it was originally!
  687.    If you HIDE info and you lose, you'll have to do more work than what you said you'd do. \\
  688.    If you create PHANTOM info and you lose, you'll do less than what you said you'd do.
  689. \end{tcolorbox}
  690.  
  691. \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!