Main.java

import java.util.*;

public class Main {

	static TreeSet<Double> bidHistory;

	public static void main(final String[] args) {
		final EnumMap<Participant, Double> cuts = new EnumMap<Participant, Double>(Participant.class);
		final double paidToBill = 1;
		cuts.put(Participant.BILL, 0.0);
		optimizeCut(paidToBill, cuts, Participant.ME);
		for (int x = 0; x < 15; x++) {
			System.out.println(toString(cuts) + "\t\t" + toString(netProf(paidToBill, cuts)) + "\t"
					+ ttl(netProf(paidToBill, cuts)));
			optimizeCut(paidToBill, cuts, Participant.BILL);
			optimizeCut(paidToBill, cuts, Participant.ME);
		}

		metaOptimizeCut(paidToBill, cuts, Participant.ME, Participant.BILL);

		System.out.println("Evil Me: " + toString(cuts) + "\t" + toString(netProf(paidToBill, cuts)) + "\t"
				+ ttl(netProf(paidToBill, cuts)));

		metaOptimizeCut(paidToBill, cuts, Participant.BILL, Participant.ME);

		System.out.println("Evil Bill: " + toString(cuts) + "\t" + toString(netProf(paidToBill, cuts)) + "\t"
				+ ttl(netProf(paidToBill, cuts)));
	}

	static double bidWinProb(final double bid) {
		if (bidHistory == null) {
			final int sampleWins = 100000, bidders = 10;
			final Random r = new Random();
			bidHistory = new TreeSet<Double>();
			for (int x = 0; x < sampleWins; x++) {
				double maxBid = 0;
				for (int y = 0; y < bidders; y++) {
					final double b = 0.5 + r.nextGaussian() * 0.1;
					if (b > maxBid) {
						maxBid = b;
					}
				}
				// System.out.println(maxBid);
				bidHistory.add(maxBid);
			}
		}
		return ((double) bidHistory.headSet(bid).size()) / bidHistory.size();
	}

	static void metaOptimizeCut(final double paidToBill, final EnumMap<Participant, Double> cuts,
			final Participant participant, final Participant other) {
		double bestNetCut = 0, bestNetProf = 0;
		for (double x = 0; x < 1; x += 0.01) {
			cuts.put(participant, x);
			optimizeCut(paidToBill, cuts, other);
			final double netProf = netProf(paidToBill, cuts).get(participant);
			// System.out.println(x + "\t" + netProf);
			if (netProf > bestNetProf) {
				bestNetProf = netProf;
				bestNetCut = x;
			}
		}
		cuts.put(participant, bestNetCut);
		optimizeCut(paidToBill, cuts, other);
	}

	static EnumMap<Participant, Double> netProf(final double paidToBill, final EnumMap<Participant, Double> cuts) {
		final double adCut = cuts.get(Participant.BILL);
		final double netCut = cuts.get(Participant.ME);
		final double bid = paidToBill * (1 - adCut) * (1 - netCut);
		final double winProb = bidWinProb(bid);
		final EnumMap<Participant, Double> ret = new EnumMap<Participant, Double>(Participant.class);
		ret.put(Participant.BILL, paidToBill * adCut * winProb);
		ret.put(Participant.ME, paidToBill * (1 - adCut) * netCut * winProb);
		return ret;
	}

	static void optimizeCut(final double paidToBill, final EnumMap<Participant, Double> cuts, final Participant participant) {
		double bestCut = 0;
		double bestProf = 0;
		for (double x = 0.0; x < 1.0; x += 0.01) {
			cuts.put(participant, x);
			final double prof = netProf(paidToBill, cuts).get(participant);
			// System.out.println(x + "\t" + prof);
			if (prof > bestProf) {
				bestProf = prof;
				bestCut = x;
			}
		}
		cuts.put(participant, bestCut);
	}

	static String toString(final EnumMap<Participant, Double> cuts) {
		return String.format("Bill: %.3f\tMe: %.3f", cuts.get(Participant.BILL),
				cuts.get(Participant.ME));
	}

	static String ttl(final EnumMap<Participant, Double> cuts) {
		final double ttl = cuts.get(Participant.BILL) +
		cuts.get(Participant.ME);
		return String.format("Ttl: %.3f, each: %.3f", ttl, ttl / 2);
	}
}

enum Participant {
	BILL, ME;
}