Swindling Car Dealers

usedCar.py

# http://fivethirtyeight.com/features/how-badly-can-a-car-salesman-swindle-you/
# Michael Scott Cuthbert (cuthbert@mit.edu) -- CC-BY 2015

from __future__ import print_function, division

import itertools
from collections import OrderedDict
from pprint import pprint

inf = float('inf')

class ChoiceSet:
    def __init__(self, choices):
        self.c = choices
        self.perms = OrderedDict()
        self.intervals = OrderedDict()
        self.computedValues = OrderedDict()
        self.init()
        
    def init(self):
        '''
        initialize the permutations and the intervals.
        '''
        choiceLength = len(self.c)
        for permLength in range(1, choiceLength + 1):
            thesePerms = sorted(itertools.permutations(self.c, permLength))
            self.perms[permLength] = thesePerms

            intervalDict = OrderedDict()
            for thisPerm in thesePerms:
                intervalTuple = tuple([z - y for y, z in zip(thisPerm, thisPerm[1:])])
                if intervalTuple not in intervalDict:
                    intervalDict[intervalTuple] = []
                intervalDict[intervalTuple].append(thisPerm)
                
            intervalDict = OrderedDict(sorted(intervalDict.items()))
            self.intervals[permLength] = intervalDict 

    def calculate(self):
        '''
        calculate the expected values, from deepest to shallowest games.
        
        This computes the subgame-perfect Nash equilibrium, not just the standard Nash
        (in case you need to take over negotiations after a friend has screwed it up...)
        '''
        maxLen = len(self.c) - 1
        for currentLength in range(maxLen, -1, -1):
            intervalDict = self.intervals[currentLength + 1]
            for intervals in intervalDict:
                stayValue = self.evStay(intervals)
                if currentLength == maxLen:
                    evBest = stayValue
                    strategy = 'end'
                else:
                    continueValue = self.evContinue(intervals)
                    evBest = min([stayValue, continueValue])
                    strategy = getStrategy(stayValue, continueValue)
                self.computedValues[intervals] = (evBest, len(intervalDict[intervals]), strategy)
            
    def evStay(self, intervals=None):
        '''
        expected value of staying on an interval.
        '''
        if intervals is None:
            intervals = ()
        keyLen = len(intervals) + 1
        permList = self.intervals[keyLen][intervals]
        currVals = [t[-1] for t in permList]
        return avg(currVals)

    def evContinue(self, intervals=None):
        '''
        expected value of continuing from an interval.  Assumes that parts of `calculate`
        have already been run on the deeper games.
        '''
        if intervals is None:
            intervals = ()
        
        intervalLen = len(intervals)
        keyLen = intervalLen + 2
        
        intervalLenList = self.intervals[keyLen]
        
        totalNum = 0
        totalValue = 0
        
        for intervalTuple in intervalLenList:
            if not tstartswith(intervalTuple, intervals):
                continue
            ev, numWays, unused_strategy = self.computedValues[intervalTuple]
            totalNum += numWays
            totalValue += ev * numWays
            
        return totalValue/totalNum
    
    def explain(self, currentInterval=()):
        '''
        explain the reasoning and strategy and values.  Only the first line is necessary
        to get the EV for the entire exercise, but to actually do the negotiation, you'll
        need it all.
        '''
        skipIntervals = []
        ev, unused_numWays, strategy = self.computedValues[currentInterval]
        print(niceExplain(currentInterval, ev, strategy))
        if strategy == 'continue':
            for i in self.computedValues:
                if not tstartswith(i, currentInterval) or len(i) != len(currentInterval) + 1:
                    continue
                self.explain(i)

def niceExplain(currentInterval, ev, strategy):
    '''
    given an interval set, expected value, and strategy, explain what to do nicely.
    '''
    spaces = "  " * len(currentInterval)
    if currentInterval == ():
        begin = 'At the start, '
    elif strategy == 'end':
        begin = ''
    else:
        joint = ', '.join([str(i) for i in currentInterval])
        begin = 'If the pattern seen is ' + joint + ', '
        
    if strategy != 'end':
        strategic = 'you should ' + strategy + ' playing. '
        ending = 'And your expected ' 
    else:
        strategic = 'You are now on the last card. '
        strategic += 'If the last interval was ' + str(currentInterval[-1]) + ', '
        ending = 'your '
    
    
    ending += 'cost is N + %.1f' % ev
    return spaces + begin + strategic + ending


def tstartswith(t, i):
    '''helper: does a tuple t begin with tuple i?'''
    if t[:len(i)] == i:
        return True
    else:
        return False

def avg(vals):
    '''return avg of vals'''
    return sum(vals)/len(vals) if len(vals) > 0 else float('nan')

def getStrategy(sv, cv):
    '''gives the strategy (if not end)'''
    if sv == cv:
        return "stop (or carefully continue)"
    if sv <= cv:
        return "stop"
    else:
        return "continue"


if __name__ == '__main__':
    cs = ChoiceSet({0, 100, 200, 300, 400})
    cs.calculate()
    cs.explain()