CSCE 782: Problem Set 3

Due: Monday, 19 November 2007 @ 2pm

PAR Algorithm

For this problem set you will implement a NetLogo visualization of the PAR algorithm from preference elicitation in combinatorial auction, as shown in Figure 7.10 of the text book. Specific requirements include:

  1. You will have sliders for the number of agent and number of items for sale.
  2. The agents' valuations will be generated randomly. For simplicity, you can assume these valuations are strictly additive. Also, I think the final graph will be more interesting if the agents have largely non-overlapping interests (set many of their singleton valuations to 0), but this is just a recommendation.
  3. As the program runs you will generate a graph like the one in Figure 7.11 but without tying the nodes to particular point in space. That is, your nodes will be floating and all you care about are the directed links between them. At each step of the algorithm you will create new nodes and add them to the graph at the appropiate position. Notice that this graph is, in fact, a tree with the root being the first node you create. Thus, you will probably want to use the tree (circle) layout function.
  4. Nodes in the fringe should be of a different color.

You are encouraged to try any ideas you have for visualizing the dynamics of the algorithm. Have fun!

José M. Vidal
Last modified: Tue Oct 30 15:00:03 EDT 2007