Bargaining

This talks covers bargaining, task allocation, and coalition formation. It summarizes material from:

Gerhard Weiss. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. [1] MIT Press. 1999. Chapter 5.5-5.7

Bargaining is uses when agents could make a mutually beneficial agreement but have a conflict of interest about which one to make. Like in Battle of the Sexes [2].
Axiomatic Bargaining Theory assumes no equilibrium. Instead it states the desired properties of a solution (axioms of bargaining solution).
The Nash bargaining solution is an early solution concept for a game with two agents trying to decide between a set of outcomes (o) and a fallback outcome (o_fallback). The set of axioms are:
- Invariance: u_i is relative, not absolute. We can multiply it by two the results should still be the same.
- Anonymity: switching the labels on the agents does not affect the outcome.
- Independence of irrelevant alternatives: if o is removed, the solution should not change.
- Pareto efficiency: it is not possible to give both players more utility.
- The best outcome that satisfies them is
- o^* = arg max_o(u₁(o) - u₁(o_fallback))(u₂(o) - u₂(o_fallback))
- Also nice because it's an unique solution
- It can be extended to more than two agents.
For example, say two agents are deciding how to split a dollar with a fallback value of 0. In this case all splits are in the Nash equilibrium (picture the matrix). However, the Nash bargaining solution gives us a .5/.5 split (why?).

Instead of axioms, reformulate as a game and use equilibriums. Unfortunately, equilibriums are not unique. Still, this models humans/smart agents better since it does not impose an artificial fairness requirement.
It consists of successive bids until a deadline is reached. We assume that when the deadline arrives the other guy is willing to take 0.
If agents were to take turns bidding on splitting the dollar, the first one would wait until the end and then bid .9999 and keep the (almost) whole dollar.

To make the problem more realistic (think perishable or time-sensitive products) we can discount the dollar by some amount each time, e.g., multiply it by .9. Such a setting would look like:

Offerer's maximal acceptable claims in a finite game.
Round	1's share	2's share	Total value	Offerer
t-3	.819	.181	.9^t-4	2
t-2	.91	.09	.9^t-3	1
t-1	.9	.1	.9^t-2	2
t	1	0	.9^t-1	1

For example, at t-1, 2 knows that the next round the total value will lose 10% (.1) so if he gets 10% then 1 will get the same as next time. That is, 90% at t-1 is the same as 100% at t.

What if there is no deadline? What if we allow for an infinite number of steps? What is the solution then?
Assume that 1's discount rate is d₁ and 2's is d₂.
Rubenstein's bargaining solution tells us that the solution is for agent 1 to get (1 - d₂)/(1 - d₁d₂) and agent 2 gets the rest.
This agreement will be reached on the first round.

Proof:

Offerer's maximal acceptable claims in a finite game.
Round	1's share	2's share	Offerer
t-2	1 - d₂(1 - d₁P)		1
t-1		1 - d₁P	2
t	P		1

As the number of times goes to infinity the difference between successive steps goes to 0, so we can say that P = 1 - d₂(1 - d₁P) and solve for P.

The task allocation problem consists of:
- T: tasks
- A: agents
- c_i : 2 ^T -> Reals. cost to agent i to do a subset of tasks.
- (t₁, t₂,..., t_|A|): an initial allocation of tasks to agents.
The standard contract net protocol does not specify how much an agent should bid. An simple option is to have the agents bid their marginal cost since Adam Smith tells us that they will eventually converge to it.
MC_add(T^contract | T_q) = c_q(T^contract + T_q) - c_q(T_q) : The cost for agent q to add some tasks in contract.
MC_remove(T^contract | T_r) = c_r(T^r) - c_q(T_r - T^contract) : The cost for agent r to remove some tasks as given in contract.

In the simple individual hill-climbing protocol each agent tries to give/get one task to/from another agent. This protocol will always increase the global utility but will often get stuck in a local optimum.
One way to get around this problem is to connect every single possible task allocation to every other one in one step. This way, the global optimum is always just one step away (ahh, but which step?).
This is what OCSM contracts do. Instead of just trading one task between agents, they make every deal possible, with any number of tasks and agents. OCSM contracts beg the question of how to find the global optimum.

L indicates that lying is profitable.
Deal Type	General TOD			Subadditive TOD			Concave TOD			Modular TOD
	Hid	Pha	Dec	Hid	Pha	Dec	Hid	Pha	Dec	Hid	Pha	Dec
Pure	L	L	L	L	L	L	L	L	L	L
Mixed	L		L	L		L	L			L
All-or-nothing	-	-	-			L

Pure deals: agents are deterministically allocated exhaustive, disjoint task sets.
Mixed deals: specify a probability distribution over such partitions.
All-or-nothing: deals are mixed deals where he alternatives only include partitions where one agent handles the tasks of all agents.
Agents might hide tasks, declare phantom tasks that do not exists, and announce decoy tasks that do not exists but can be generated on demand

A contingency contract might only come into effect after a specified event, e.g., traveler's insurance.
In general, it is very hard to enumerate every possible thing that might go wrong.
If agent 1 does not trust agent 2 enough to pay him $1M for $500K shoes, 1 might instead give him $2 for 1 shoe, then another $2 for the next shoe, and so on. These are called leveled commitment contracts.
They allow some huge contracts to happen which would not do so otherwise because the agents are risk-averse.

We define a coalition formation problem as:
- S: coalition, a subset of A agents.
- V_S: the value of coalition S to its members.
- CS: a coalition structure. The set of all coalitions such that all agents belong to one.
If the costs are supperadditive (V_S+T >= V_S + V_T) then the grand coalition is the best deal.
Otherwise, finding the optimal CS is very hard.

If we explore the lowest two levels of the graph we can be sure that the best coalition is no more than |A| times better than the one we found. Notice that we have examined every possible S, so the best will have to be <= S'|A|, where S' is the best one we have found so far.
Unfortunately, there are 2^{|A| - 1} in just those two levels.
Coalition formation and task allocation are just instances of a more general multiagent search problem.

Even if you did find the optimal CS, it might not be worth much if its not stable. That is, if there are any agents who are motivated to depart from that CS.
We define the core of a CS to be the vector of payoffs to agents such that no subgroup is motivated to depart from the given CS.
The core does not always exists, sometimes there are several of them. The core is reminiscent of the Nash equilibrium.
Another payoff division method can be established by defining:
- i is a dummy if V_{S + i} - V_S = V_i
- i and j are interchangeable if for all S with either i or j, V_S remains the same if i is replaced with j, or viz.
We now want a set of payoffs that exhibit:
- Symmetry: If i and j are interchangeable then x_i = x_j (where x is the set of payoffs).
- Dummies: If i is a dummy then x_i = V_i.
- Additivity: For any two games V and W, x_i in V+W equals x_i in V plus x_i in W, where V+W is the game defined by (V+W)_S = V_S + W_S.
The Shapely Value satisfies all these: It sets x_i = SUM_{S in A} (|A| - |S|)!(|S| - 1)!(V_S - V_{S - i})/ |A|!
It obeys all three properties. It exists, and is unique. It is pareto efficient (all the money is distributed among the agents).
But, there is no guarantee that a subgroup is better off by splitting out. It takes a long time to compute.

Bargaining

1 Axiomatic Bargaining Theory

2 Strategic Bargaining Theory

3 Rubenstein Bargaining Solution

4 Contract Net Task Allocation

5 Task Allocation Search: OCSM Contracts

6 Lying in Task Allocation

7 Other Issues with Contracts

8 Coalition Formation

9 Payoff Division

URLs