# CSCE 782: Problem Set 3

## Meeting Scheduling as a Negotiation Problem

You are hired by Microsoft to improve Exchange's calendar. Specifically, they are looking to add a distributed meeting scheduling feature, which they have unfortunately dubbed iSchedule. The idea is that each person has a set of preferences over times for the various meetings he must attend. These preferences are given to his agent. The agents then negotiate in order to schedule as many meetings as possible while keeping the most people happy. That is, the system should maximize social welfare.

You think about this problem for a little bit and quickly realize that there are a lot of variables here and that the best approach is to distill the problem to its simplest possible expression, come up with a solution(s) to this problem, and simulate them in NetLogo to see how well they work (or, don't).

Specifically, you define the problem as consisting of

• A set A of agents.
• A set V of variables.
• A set D of values for the variables. We will assume the domain to be 1..10.
• Each agent is assigned a subset of the variables.
• Each agent has a set C of constraints over its variables. We will assume that these are all of the form: a < v <, meaning that v must be between a and b. Agents do not want to violate their constraints.
• The system should make it so that all agents with the same variable assign it the same value.

As you can see, the variables correspond to meetings and the agents that are assigned a particular variable are the agents that need to attend that meeting. The value of the variables are the scheduled times.

We can now view this as a negotiation problem where the agents try to assign values to their variables so as to minimize their constraint violations, if possible. From the system perspective, however, all we care about is that all variables have the same value in all the agents. That is, all meetings are scheduled. Your job is to

1. Design, document, and implement a reasonable negotiation strategy for the agents.
2. Test to see how well it performs (how close to optimal, how do you define optimal?) as you change the number of variables (meetings) per agent and the number of agents per variable.

## Visualization

You should use the patches to help visualize the variable assignments. Namely, each column in the grid corresponds to a variable and each row to an agent. The color of a particular patch then corresponds to the value that particular agent has assigned to it. In this way if a column has all the same color (and black, which is the default if that particular agent is not assigned that value) it means that all agents have assigned it the same value.

You should also again use the plots to show measures of how well the system is doing scheduling all meetings and how well the agents are doing in satisfying their constraints.

## References

The formalization of this problem comes from

You might want to read that paper to get some ideas into possible strategies but note their problem is slightly more complex than the one we are solving. Namely, we are not worried about incremental additions or privacy.

### 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