Monotoniczny protokół koncesji

Protokół negocjacji, który rozważamy dla domen zadaniowych, jest znany jako protokół koncesji monotonicznych. Zasady tego protokołu są następujące. protokół koncesyjny

• Negocjacje toczą się w serii rund.
• W pierwszej rundzie obaj agenci jednocześnie proponują umowę, D_i = (T₁,T₂), z zestawu negocjacyjnego. (Różni się to od naprzemiennych ofert, które widzieliśmy wcześniej.)
• Porozumienie zostaje osiągnięte, gdy dwaj agenci zaproponują rozdanie odpowiednio D₁ i D₂, tak że albo (i) U₁(D₂) ≥ U1(D1) albo (ii) U₂(D₁) ≥ U₂(D₂), to znaczy jeden z agentów stwierdza, że ​​oferta zaproponowana przez drugiego jest co najmniej tak samo dobra lub lepsza niż propozycja, którą złożył. W przypadku osiągnięcia porozumienia zasada określania umowy jest następująca: Jeśli oferta każdego agenta jest zgodna lub wyższa od oferty innego agenta, wówczas jedna z propozycji jest wybierana losowo. Jeśli tylko jedna propozycja przekracza lub odpowiada propozycji drugiej, to jest to umowa.
• Jeśli nie zostanie osiągnięte porozumienie, negocjacje przechodzą do kolejnej rundy równoczesnych propozycji. W rundzie t +1 każdy agent musi albo powtórzyć propozycję z poprzedniej rundy, albo zrobić ustępstwo – propozycję, która jest bardziej preferowana przez drugiego agenta (tj. ma wyższą użyteczność).
• Jeśli żaden z agentów nie ustąpi, negocjacje się kończą, a obaj agenci realizują porozumienie w sprawie konfliktu, wykonując zadania, które zostały im pierwotnie przydzielone.

Ponieważ zestaw możliwych umów jest ograniczony, agenci nie mogą negocjować w nieskończoność: albo agenci dojdą do porozumienia, albo nastąpi runda, w której żaden z agentów się nie podda. Protokół nie gwarantuje jednak, że porozumienie zostanie osiągnięte szybko: ponieważ liczba możliwych transakcji wynosi O(2^|T|), można sobie wyobrazić, że negocjacje będą trwały przez kilka rund wykładniczych pod względem liczby zadań do przydzielenia.