Shaheen Fatima - Principles of Automated Negotiation

We thank our many co-authors for giving their permission to adapt material from papers that we have written with them. We are very grateful to Yaakov (Kobi) Gal, Enrico Gerding, Raz Lin, Valentin Robu, and Mateusz Tarkowski, who gave us extremely useful comments on drafts of the book. Jordan Summers-Young carefully proofread several drafts for us, and gave detailed and enormously helpful comments. Many thanks to Jeff Rosenschein for answering questions about his work and for his advice and friendship over the years. It goes without saying that any remaining errors are entirely the responsibility of the authors.

Sarit Kraus would like to acknowledge the support of the European Research Council under Advanced Grant 267523. Michael Wooldridge would like to acknowledge the support of the European Research Council under Advanced Grant 291528.

Proof of ).

), Ua(X, n) will be maximised for X = {mg + 1, , m}, that is, OAg = {mg + 1, , m}.

Next, consider the case where b is the last mover. For a given agenda, as equilibrium offer for t = n 1 will be a solution (x) to the following maximisation problem:

(A.1)

Let k be an integer such that, in the solution to this maximisation problem, a will get 100% of the issues {k + 1, , g} and b will get 100% of the issues {1, , k 1}. In other words, for k + 1 cg, xc = 1 and for 1 ck 1, xc = 0. Substituting these xc in the constraint for TRADEOFFA we get:

Solving this equation for xk, we get xk = kg. This x will give a an equilibrium utility of From is defined as follows:

(A.2) (A.3)

Since all weights are positive and xk = kg must be non-negative, we get OAg = {mg + 1, , m}.

Proof of ).

Let the agendas in be comprised of the issues in the set iI, that is, Suppose that the issues in i are in increasing order of as weights. Given this, we begin by proving that Specifically, we do this for the time t = n 1. Then, by backward induction, be true for all previous time periods.

We are given that Agent b is the proposer for t = n 1. For an let (xXc, yXc) denote, we know that (xXc, yXc) will be a solution to the following maximisation problem:

(A.4)

As per , the solution (x, y) to the above problem will be in category i iff and Then, for category i, the solution will be yXc = 0 for gi + 2 cg, yXc = 1 for 1 cgi, and

(A.5)

We know that In this equation for Bg, substitute yXc = 0 for gi +2 cg, yXc = 1 for 1 cgi, and yXgi+1 from Equation (to get:

(A.6)

Note that, since all weights are positive, maximising (minimising) the sum of weights is the same as maximising (minimising) individual weights that constitute the sum. Now, depends on the relation between and There are two possible relations:

For relation R1, we have:

(A.7)

For relation R2, we have:

(A.8)

Thus, )).

We know that, for time t and category i, the equilibrium for none of the agendas in AGg will be in any of the categories 1 , , i1 . We also know that the equilibrium for at least one agenda in AGg will be in the category i, that is, In addition, we know that bs utility for agenda X will be

We prove that bs equilibrium utility for agenda X (where and d > i) will be less than her utility for X. If we denote the equilibrium package for X and time t = n 1 as ( x , ), then bs utility from ( x , ) will be Since