# CSCE 782: Problem Set 2

## Due: Monday, 3 October 2005, 11am

### Negotiating Complex Workflow Allocations

In this problem set you will apply the solution presented in

to the multiagent workflow enactment problem.

#### The Multiagent Workflow Enactment Problem

Let num-agents be the number of agents. Each agent is randomly give two skills from a fixed list of 10 skills. At each time step a number of new workflows appears. This number is taken from a Poisson random distribution with mean workflow-arrival-rate. Each workflow contains a set of 5 randomly generated skills (repetitions are allowed) and a payment which is taken from a normal distribution with mean mean-payment. In order to perform (enact) a workflow, we need to find 5 agents with the appropriate skills. An agent can only perform 1 skill for 1 workflow at each time step.

The system must allocate as many of the workflows as possible. The agents, on the other hand, want to maximize their own payments. The workflow payments are divided equally among the agents in a workflow. Since all our workflows have 5 skills, this means that for a workflow of payment p each agent would receive a payment of p/5. The optimal solution maximizes the sum of the payments given to the agents, at every time step.

#### The Annealing Mediator Solution

We modify the annealing mediator solutions, as presented in the paper above (Section 5), as follows (We do this to handle more than 2 agents) . Once a new set of workflows appears we begin a new negotiation. At each negotiation time step a mediator chooses an allocation of agents to workflows (note that there might not be enough agents or workflows, so some workflows might not get enacted or some agents might be idle). It broadcasts this allocation to all and they all give it one of their four votes: strong accept, weak accept, weak reject, strong reject. The mediator converts these votes into numbers using the values

• strong accept: 2
• weak accept: 1
• weak reject: -1
• strong reject: -2
and adds these number. If the final number is 1 or more then the proposal is accepted. But, the mediator also occasionally accepts allocations with a smaller number using the annealing scheme described in the paper (replace the number above for utility in the equation). If the contract is accepted then the new one is generated via a small mutation of it---assigning one of the agents to a different workflow). If not then we use the last accepted contract.

The process ends when the temperature is low enough, at which point we say that the workflows have been allocated.

#### The Agent Strategies

An agent determines its vote by first calculating the highest payment it could get, which is 1/5 of the payment of the highest-paid workflow that includes one of the agent's skills. Let this payment be maxp. Let p be the agent's payment under the proposed allocation. The truth-telling agent's vote is then decided as follows:

• If p < maxp/4 then strong reject.
• If p < 2 * maxp/4 then weak reject.
• If p < 3 * maxp/4 then weak accept.
• Else, strong accept.
The exaggerating agent's vote is decided using
• If p < 2 * maxp/4 then strong reject.
• Else, strong accept.

#### Testing

The new problem raises two immediate questions.

1. Does this solution also find allocations that are near the pareto frontier?
2. Does this solution also reward exaggerators in the presence of truth tellers?
Answering the first question requires verifying whether the final allocation is a pareto optimal. That seems like it will require a lot of computation, so you will skip that.

The second question is easier to answer since it only requires you to compare the payments accrued by the various types of agents. You will run tests to show the payments accrued in situations where

1. All agents but one use the same strategy.
2. Half the agents use one strategy and half the other.
3. All agents use the same strategy.
Do your results echo Table 3 from the paper? Why or why not? You should have one button (run-tests) which runs the set of tests and prints out the final data. These tests might take a while to run as you will be running many negotiations.

Finally, note that num-agents, workflow-arrival-rate, and mean-payment should be sliders in your model.

#### Visualization

I cannot think of a good way of using the turtle space to visualize the negotiation process. If you can, that would be great! Otherwise just use the plot command to draw some graphs representing the payment distribution among the agents and the accumulated payment in each run.

### Submission Instructions

As will all the problem sets, you will hand them in using our department's dropbox. You will only hand in your .nlogo file. You will place all your documentation in the documentation tab of your NetLogo model. The information tab needs to start with:

Name:
email:

I understand that it is the responsibility of every member of the Carolina community to uphold an maintain the academic standards and integrity of the University of South Carolina. Any member of the University community, who has reasonable grounds to believe that an infraction of the Code of Student Academic Responsibility has occurred, has an obligation to report the alleged violation.

I certify that I have neither given nor received unauthorized aid on this problem set.

José M. Vidal