Index: exampleparties/timedependentparty/src/main/java/geniusweb/exampleparties/timedependentparty/ExtendedUtilSpace.java
===================================================================
--- exampleparties/timedependentparty/src/main/java/geniusweb/exampleparties/timedependentparty/ExtendedUtilSpace.java	(revision 4)
+++ exampleparties/timedependentparty/src/main/java/geniusweb/exampleparties/timedependentparty/ExtendedUtilSpace.java	(revision 4)
@@ -0,0 +1,102 @@
+package geniusweb.exampleparties.timedependentparty;
+
+import java.math.BigDecimal;
+import java.math.BigInteger;
+import java.util.Collections;
+import java.util.LinkedList;
+
+import geniusweb.bidspace.BidsWithUtility;
+import geniusweb.bidspace.Interval;
+import geniusweb.bidspace.IssueInfo;
+import geniusweb.issuevalue.Bid;
+import geniusweb.issuevalue.Value;
+import geniusweb.profile.utilityspace.LinearAdditiveUtilitySpace;
+import tudelft.utilities.immutablelist.ImmutableList;
+
+/**
+ * Inner class for TimeDependentParty, made public for testing purposes. This
+ * class may change in the future, use at your own risk.
+ *
+ */
+public class ExtendedUtilSpace {
+	private LinearAdditiveUtilitySpace utilspace;
+	private BigDecimal tolerance; // utility tolerance for a bid.
+	private BidsWithUtility bidutils;
+	// min and max achievable utility
+	private BigDecimal minUtil;
+	private BigDecimal maxUtil;
+
+	public ExtendedUtilSpace(LinearAdditiveUtilitySpace space) {
+		this.utilspace = space;
+		bidutils = new BidsWithUtility(utilspace);
+		computeMinMax();
+		this.tolerance = computeTolerance();
+
+	}
+
+	/**
+	 * Computes the fields minutil and maxUtil.
+	 * <p>
+	 * TODO this is simplistic, very expensive method and may cause us to run
+	 * out of time on large domains.
+	 * <p>
+	 * Assumes that utilspace and bidutils have been set properly.
+	 */
+	private void computeMinMax() {
+		Interval range = bidutils.getRange();
+		this.minUtil = range.getMin();
+		this.maxUtil = range.getMax();
+
+		Bid rvbid = utilspace.getReservationBid();
+		if (rvbid != null) {
+			BigDecimal rv = utilspace.getUtility(rvbid);
+			if (rv.compareTo(minUtil) > 0)
+				minUtil = rv;
+		}
+	}
+
+	/**
+	 * Tolerance is the Interval we need when searching bids. When we are close
+	 * to the maximum utility, this value has to be the distance between the
+	 * best and one-but-best utility.
+	 * 
+	 * @return the minimum tolerance required, which is the minimum difference
+	 *         between the weighted utility of the best and one-but-best issue
+	 *         value.
+	 */
+	protected BigDecimal computeTolerance() {
+		BigDecimal tolerance = BigDecimal.ONE;
+		for (IssueInfo iss : bidutils.getInfo()) {
+			if (iss.getValues().size().compareTo(BigInteger.ONE) > 0) {
+				// we have at least 2 values.
+				LinkedList<BigDecimal> values = new LinkedList<BigDecimal>();
+				for (Value val : iss.getValues()) {
+					values.add(iss.getWeightedUtil(val));
+				}
+				Collections.sort(values);
+				Collections.reverse(values);
+				tolerance = tolerance
+						.min(values.get(0).subtract(values.get(1)));
+			}
+		}
+		return tolerance;
+	}
+
+	public BigDecimal getMin() {
+		return minUtil;
+	}
+
+	public BigDecimal getMax() {
+		return maxUtil;
+	}
+
+	/**
+	 * @param utilityGoal
+	 * @return bids with utility inside [utilitygoal-tolerance, utilitygoal]
+	 */
+	public ImmutableList<Bid> getBids(BigDecimal utilityGoal) {
+		return bidutils.getBids(
+				new Interval(utilityGoal.subtract(tolerance), utilityGoal));
+	}
+
+}
Index: exampleparties/timedependentparty/src/main/java/geniusweb/exampleparties/timedependentparty/TimeDependentParty.java
===================================================================
--- exampleparties/timedependentparty/src/main/java/geniusweb/exampleparties/timedependentparty/TimeDependentParty.java	(revision 3)
+++ exampleparties/timedependentparty/src/main/java/geniusweb/exampleparties/timedependentparty/TimeDependentParty.java	(revision 4)
@@ -3,4 +3,5 @@
 import java.io.IOException;
 import java.math.BigDecimal;
+import java.math.BigInteger;
 import java.net.URI;
 import java.net.URISyntaxException;
@@ -14,6 +15,4 @@
 import geniusweb.actions.Offer;
 import geniusweb.actions.PartyId;
-import geniusweb.bidspace.AllBidsList;
-import geniusweb.bidspace.BidsWithUtility;
 import geniusweb.issuevalue.Bid;
 import geniusweb.party.Capabilities;
@@ -24,6 +23,6 @@
 import geniusweb.party.inform.Settings;
 import geniusweb.party.inform.YourTurn;
+import geniusweb.profile.Profile;
 import geniusweb.profile.utilityspace.LinearAdditiveUtilitySpace;
-import geniusweb.profile.utilityspace.UtilitySpace;
 import geniusweb.profileconnection.ProfileConnectionFactory;
 import geniusweb.profileconnection.ProfileInterface;
@@ -31,4 +30,5 @@
 import geniusweb.progress.ProgressRounds;
 import geniusweb.references.ProtocolRef;
+import tudelft.utilities.immutablelist.ImmutableList;
 import tudelft.utilities.logging.Reporter;
 
@@ -41,10 +41,12 @@
 public abstract class TimeDependentParty extends DefaultParty {
 
+	private static final BigDecimal DEC0001 = new BigDecimal("0.0001");
+	private static final BigDecimal DEC100 = new BigDecimal("100");
 	private ProfileInterface profileint;
+	private LinearAdditiveUtilitySpace utilspace = null; // last received space
 	private PartyId me;
 	private Progress progress;
-	private Double minUtil = null, maxUtil = null;
 	private Bid lastReceivedBid = null;
-	private double tolerance;
+	private ExtendedUtilSpace extendedspace;
 
 	public TimeDependentParty() {
@@ -77,5 +79,4 @@
 				this.me = settings.getID();
 				this.progress = settings.getProgress();
-				computeMinMax();
 			} else if (info instanceof ActionDone) {
 				Action otheract = ((ActionDone) info).getAction();
@@ -117,13 +118,15 @@
 
 	private void myTurn() throws IOException {
-		Action myAction = null;
+		updateUtilSpace();
 		Bid bid = makeBid();
-		UtilitySpace utilspace = getUtilSpace();
 
-		if (lastReceivedBid != null && utilspace.getUtility(lastReceivedBid)
-				.compareTo(utilspace.getUtility(bid)) >= 0) {
+		Action myAction;
+		if (bid == null || lastReceivedBid != null
+				&& utilspace.getUtility(lastReceivedBid)
+						.compareTo(utilspace.getUtility(bid)) >= 0) {
+			// if bid==null we failed to suggest next bid.
 			myAction = new Accept(me, lastReceivedBid);
 		} else {
-			myAction = new Offer(me, makeBid());
+			myAction = new Offer(me, bid);
 		}
 		getConnection().send(myAction);
@@ -131,51 +134,23 @@
 	}
 
-	private UtilitySpace getUtilSpace() {
-		return (LinearAdditiveUtilitySpace) profileint.getProfile();
+	private LinearAdditiveUtilitySpace updateUtilSpace() {
+		Profile newutilspace = profileint.getProfile();
+		if (!newutilspace.equals(utilspace)) {
+			utilspace = (LinearAdditiveUtilitySpace) newutilspace;
+			extendedspace = new ExtendedUtilSpace(utilspace);
+		}
+		return utilspace;
 	}
 
 	/**
-	 * Computes the fields minutil and maxUtil if not yet computed. minutil is
-	 * the minimum utility of any bid, but at least the utility of the
-	 * reservation bid. maxUtil is the maximum util of any bid.
-	 * <p>
-	 * TODO this is simplistic, very expensive method and may cause us to run
-	 * out of time on large domains.
-	 * <p>
-	 * Can be called only after profileint has been set.
+	 * @return next possible bid with current target utility, or null if no such
+	 *         bid.
 	 */
-	private void computeMinMax() {
-		if (this.maxUtil != null && this.minUtil != null)
-			return;
-		this.minUtil = 1d;
-		this.maxUtil = 0d;
-		UtilitySpace utilspace = getUtilSpace();
-		AllBidsList allbidslist = new AllBidsList(
-				profileint.getProfile().getDomain());
-		for (Bid bid : allbidslist) {
-			double util = utilspace.getUtility(bid).doubleValue();
-			if (util < minUtil)
-				minUtil = util;
-			if (util > maxUtil)
-				maxUtil = util;
-		}
-
-		Bid rvbid = utilspace.getReservationBid();
-		if (rvbid != null) {
-			double rv = utilspace.getUtility(rvbid).doubleValue();
-			if (rv > minUtil)
-				minUtil = rv;
-		}
-		tolerance = 100 / allbidslist.size().longValue();
-		tolerance = Math.max(tolerance, 0.1);
-	}
-
 	private Bid makeBid() {
 		double time = progress.get(System.currentTimeMillis());
-		double utilityGoal = utilityGoal(time, getE());
-		BidsWithUtility options = new BidsWithUtility(
-				(LinearAdditiveUtilitySpace) profileint.getProfile(),
-				BigDecimal.valueOf(utilityGoal),
-				BigDecimal.valueOf(utilityGoal + tolerance));
+		BigDecimal utilityGoal = utilityGoal(time, getE());
+		ImmutableList<Bid> options = extendedspace.getBids(utilityGoal);
+		if (options.size() == BigInteger.ZERO)
+			return null;
 		// pick a random one.
 		return options.get(new Random().nextInt(options.size().intValue()));
@@ -190,10 +165,15 @@
 	 * @return the utility goal for this time and e value
 	 */
-	private double utilityGoal(double t, double e) {
+	private BigDecimal utilityGoal(double t, double e) {
+		BigDecimal minUtil = extendedspace.getMin();
+		BigDecimal maxUtil = extendedspace.getMax();
+
 		double ft = 0;
 		if (e != 0)
 			ft = Math.pow(t, 1 / e);
-		// we subtract 0.000001 to correct possibly small round-up errors
-		return minUtil + (maxUtil - minUtil) * (1 - ft) - 0.000001;
+		// we subtract epsilon to correct possibly small round-up errors
+		return new BigDecimal(minUtil.doubleValue()
+				+ (maxUtil.doubleValue() - minUtil.doubleValue()) * (1 - ft))
+						.min(maxUtil).max(minUtil);
 	}
 }
