A DISTRIBUTED MEETING SCHEDULING SYSTEM
The system shows a meeting scheduling problem with 3 agents. Each agent has a weekly calendar with some meetings already set, and the goal is to find a common new meeting among all agents.
There are 5 possible cities where a meeting can be held, and 10 possible 1-hour slots every day. For simplicity, meetings are all 1-hour long. Each agent can have preference values over each time slot and for each city. Preferences values range between 0 and 1, with higher numbers denoting a higher preference.
Given a common meeting, denoted by a certain time slot and a certain city, the preference value for the meeting is the minimum among the preference values given to that time/city slot by each of the agents. The problem is to find a common meeting for all the agents with the maximal preference value.
First of all, the user fixes the number of Initial Meeting, via the lower left slider. This number is between 1 to 40, and it is the same for all the agents. The default value is 15.
After setting the number of initial meetings, the user clicks on the button "Initial Slots", and the system generates the initial meetings, which are shown in green on the schedule of each agent, with the label of the city. The red slot of the schedule is a possible common meeting, which is generated to have a solvable problem. By clicking on the tree panel on top-left of the applet, the user can see the initial meetings for each agent, and the distances between cities.
Now the user must click on the "Initial Prefs" button. At this point, a random generator gives a preference value to each city of each slot. If the user clicks on the name of one agent in the tree panel, and then clicks on a slot in the schedule, he/she will see the preference values of that agent for that slot.
Finally, to find an optimal solution, the user must click on the "Gen Solution" button. On the schedule, the solutions found are the cyan slots, with the label of the chosen city. The lower panel shows the strategy used to find an optimal solution. To find a solution, we employ a round-robin strategy where, at each step, an agent proposes a time/city slot to the other agents. When a proposal is accepted by all agents, we have a common solution, whose preference value is the minimum of the values given by the agents. To move from the current solution to a better one, we change the preference values of the agents to make sure that the next solution is better than the previous one (that is, we just set to 0 all values which are smaller than or equal to the value of the last solution). This is repeated until there are no more solutions, at which point the last solution found is an optimal one. The lower panel shown the sequence of solutions found while searching for an optimal one. Moreover, it also gives several data regarding the solving process, like: the number of proposals to find the solution, the number of open slots discovered, and the positive and negative information (which are used to compute the amount of privacy loss, for further details see the paper ).
It is also possible to fix a threshold (by using the menu on the lower center part of the panel) for the final solution: all the solutions with a value lower than the threshold are discarded. If no solution is found with value higher than or equal to the threshold, it is possible to lower the threshold and then to click again on the Gen Solution button to find a solution. The user can do this until a solution to the problem is found.
Run it now!