## Tuesday, May 13, 2008

### Traveler's dilemma and bonus factor

Traveler's dilemma description is following (taken from wikipedia):
-------------------------------------------------------
An airline loses two suitcases belonging to two different travelers. Both suitcases happen to be identical and contain identical antiques. An airline manager tasked to settle the claims of both travelers explains that the airline is liable for a maximum of \$100 per suitcase, and in order to determine an honest appraised value of the antiques the manager separates both travelers so they can't confer, and asks them to write down the amount of their value at no less than \$2 and no larger than \$100. He also tells them that if both write down the same number, he will treat that number as the true dollar value of both suitcases and reimburse both travelers that amount. However, if one writes down a smaller number than the other, this smaller number will be taken as the true dollar value, and both travelers will receive that amount along with a bonus/malus: \$2 extra will be paid to the traveler who wrote down the lower value and a \$2 deduction will be taken from the person who wrote down the higher amount. The challenge is: what strategy should both travelers follow to decide the value they should write down?
-------------------------------------------------------

Experiment was conducted as following:
- BONUS was chosen between 2 and 20
- Possible travelers request was between BONUS and 100.
- Travelers chooses cost randomly (for no-strategy imitation)
- Cost random selection was repeated 5000000 times
- After that optimal request was calculated as travelers choise which gives the greatest profit.
- And finally these optimal requests are plot in diagram as function of BONUS.

C# code which conducted experiments on random travelers choise is this:

`    class Program    {        static void Payoff(int Aoffer, int Boffer, int extra, out int Apayoff, out int Bpayoff)        {            int Aextra, Bextra;            int minoffer = Math.Min(Aoffer, Boffer);            if (Aoffer == Boffer)            {                Aextra = Bextra = 0;            }            else            {                Aextra = (Aoffer == minoffer) ? extra : -extra;                Bextra = (Boffer == minoffer) ? extra : -extra;            }            Apayoff = minoffer + Aextra;            Bpayoff = minoffer + Bextra;        }        static long OptimalSelection(int costFrom, int costTo, int goods)        {            long[] payoffA = new long[costTo + 1];            long[] payoffB = new long[costTo + 1];            Random r = new Random();            int Ac, Bc;            int Pa, Pb;            long Aopt = -1, Bopt = -1;            long Amax = 0, Bmax = 0;            for (int i = 1; i <= goods; i++)            {                Ac = r.Next(costFrom, costTo + 1);                Bc = r.Next(costFrom, costTo + 1);                Payoff(Ac, Bc, costFrom, out Pa, out Pb);                payoffA[Ac] += Pa;                payoffB[Bc] += Pb;            }            for (int j = costFrom; j <= costTo; j++)            {                if (payoffA[j] > Amax) { Amax = payoffA[j]; Aopt = j; }                if (payoffB[j] > Bmax) { Bmax = payoffB[j]; Bopt = j; }            }            return (Aopt + Bopt) / 2;        }        static void MeasureBonusInfluence()        {            double[] bonus = Array.ConvertAll(Enumerable.Range(2, 20).ToArray(),                             v => (double)(v));            double[] optimal = Array.ConvertAll(bonus,                             v => (double)OptimalSelection((int)v, 100, 5000000));            GoogleChart.PlotLineChart(bonus,                                      optimal,                                      "Bonus (\$)",                                      "Optimal request (\$)",                                      "Traveler's dilemma - bonus factor",                                      "400x200");        }        static void Main(string[] args)        {            MeasureBonusInfluence();        }    }    class GoogleChart    {        public static void PlotLineChart(double[] Xvalues,                                        double[] Yvalues,                                        string Xlabel,                                        string Ylabel,                                        string Title,                                        string imgsize)        {            string urltemplate = "http://chart.apis.google.com/chart?cht=lxy&chs=@imgsize@&chd=t:@xvalues@%7C@yvalues@&chds=@xmin@,@xmax@,@ymin@,@ymax@&chxr=0,@xmin@,@xmax@%7C1,@ymin@,@ymax@&chxt=x,y,x,y&chxl=2:%7C@xlabel@%7C3:%7C@ylabel@%7C&chxp=2,50%7C3,50&chtt=@title@";            string xvalagg = Xvalues.Aggregate("", (old, next) =>                             old + ((old == "") ? "" : ",") + next.ToString(CultureInfo.InvariantCulture));            string yvalagg = Yvalues.Aggregate("", (old, next) =>                             old + ((old == "") ? "" : ",") + next.ToString(CultureInfo.InvariantCulture));            if (imgsize == null) imgsize = "300x200";            urltemplate = urltemplate.Replace("@imgsize@", imgsize);            urltemplate = urltemplate.Replace("@xvalues@", xvalagg);            urltemplate = urltemplate.Replace("@yvalues@", yvalagg);            urltemplate = urltemplate.Replace("@xmin@", Xvalues.Min().ToString(CultureInfo.InvariantCulture));            urltemplate = urltemplate.Replace("@xmax@", Xvalues.Max().ToString(CultureInfo.InvariantCulture));            urltemplate = urltemplate.Replace("@ymin@", Yvalues.Min().ToString(CultureInfo.InvariantCulture));            urltemplate = urltemplate.Replace("@ymax@", Yvalues.Max().ToString(CultureInfo.InvariantCulture));            urltemplate = urltemplate.Replace("@xlabel@", Xlabel);            urltemplate = urltemplate.Replace("@ylabel@", Ylabel);            urltemplate = urltemplate.Replace("@title@", Title);            System.Diagnostics.Process.Start(urltemplate);        }    }`

Finally after execution of this program, we get this picture of optimal request relation with bonus amount (if travelers chooses randomly): 