MKSE150   Homework 3

Answers

Programming Component

Here is one solution to the Matching programming problem:

public void makeStableMatches(boolean show) {
	for (Player p : index.values()) p.fiancee= null;// initially, everyone has no fiancee
	while(true) {
		Player suitor= null; 
		for(Player s : suitors) if (s.fiancee==null) { suitor=s; break; }
		if (suitor==null) break;
		Player choice= index.get(suitor.advanceChoice());
		if (show) System.out.println("suitor "+suitor.name+" proposing to "+choice.name);
		if (choice.prefers(suitor.name)) engage(suitor,choice);
		}
	}

Here is one solution to the Assignment programming problem:

public int[] POAssignments() {
	int assign[]= new int[size];	// will hold the final assignments that get returned
	status= new stat[size];			// holds one status field for each player
	for (int i=0; i<size; i++) status[i]= stat.open;	// initializes everyone to the open state

	while(true) { // This loop repeatedly searches for a cycle in the preference graph and removes it.
		int node= 0; while (node<size && status[node]==stat.removed) node++;
		if (node==size) break;		// once everyone is removed, we are done 
		//System.out.println("starting search for new cycle");

		int pref[]= bestChoices();	// for each player, finds his current most-favored candidate left in the running
		//System.out.print("prefs: "); for (int i=0; i<size; i++) System.out.print(" "+pref[i]); System.out.println();

		//System.out.print("starting at node "+node+": ");
		while (status[node]==stat.open) {// test to see if we have completed a cycle
			//System.out.print(" "+node);
			status[node]= stat.seen;	// mark this node as having already been seen in this search
			node= pref[node];			// find out what his most preferred node is
		}
		//System.out.println();

		while (status[node]==stat.seen) {// this loop assigns and removes each node in the cycle just discovered
			int next= pref[node]; 
			assign[node]= next;
			status[node]= stat.removed;
			node= next;
		}
		for (int i=0; i<size; i++) 
			if (status[i]==stat.seen) status[i]= stat.open;
	}
	return assign;
}

Written Component

8.4.1
a) x = y = 500 (1 pt)
b)
-- x = y = 1000 (1 pt)
--cost = 20,000, an increase from 17,000 (1 pt)
c)
-- x = y = 500 (1 pt)
-- cost = 10,000 (1 pt)
-- nothing would change if road were closed, since it is not used in the equilibrium (1 pt)

8.4.4
a) (1 pt)
b) x = y = 50 (1 pt)
c) x = y = 100 (1 pt)
d) cost = 200, an increase from 175 (1 pt)
e) x = 50, y = 100
f)
-- cost decreases from 200 to 187.5 (1 pt)
-- the reason for this decrease is that the government is creating an incentive for people to take a less desirable route (1 pt)
-- we could further decrease cost by imposing a subsidy on CB and toll on DB (1 pt)

10.7.1
-- prices are not market clearing (1 pt)
-- the reason is that both buyers prefer b (1 pt)

10.7.11
a)
-- buyers = people, sellers = spots (1 pt)
-- vals = 6 5 2; 7 6 3; 6 7 6 (1 pt)
b)
-- prices after round 1: (1, 0, 0) (1 pt)
-- prices after round 2: (2, 1, 0) 1(1 pt)
-- market clearing prices: (2, 1, 0) (1 pt)
c) The more attractive a spot, i.e. the more central its location is, the higher its price (1 pt)

10.7.12
Some answers:
-- (1, 0)
-- (2, 0)
-- (3,0)
-- (2, 1)
-- (3, 1)
1 pt for each