assignment_2018_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Η Πλάνη του Φάνη\n",
    "\n",
    "Το «Βραβείο στις Οικονομικές Επιστήμες της Τράπεζας της Σουηδίας στη Μνήμη του Άλφρεντ Νόμπελ», κοινώς γνωστό και ως βραβείο Νόμπελ στα οικονομικά, δώθηκε το 2017 στον [Richard Thaler](https://en.wikipedia.org/wiki/Richard_Thaler), του πανεπιστημίου του Σικάγο, για τις συνεισφορές του στα [Συμπεριφορικά Οικονομικά (Behavioural Economics)](https://en.wikipedia.org/wiki/Behavioral_economics). Σύμφωνα λοιπόν με τη Wikipedia, τα Συμπεριφορικά Οικονομικά μελετούν τον αντίκτυπο των ψυχολογικών, κοινωνικών, γνωσιακών, και συναισθηματικών παραγόντων στις οικονομικές αποφάσεις του ατόμου και των θεσμών, όπως και τα αποτελέσματα των παραγόντων αυτών στον καθορισμό των τιμών, επενδυτικές αποδόσεις, καταμερισμό πόρων, κ.λπ. \n",
    "\n",
    "Εμείς θα δούμε πώς μπορούμε να διερευνήσουμε μια εφαρμογή Συμπεριφορικών Οικονομικών μέσω γράφων. Συγκεκριμένα, θα δούμε πώς ένα άτομο μπορεί να κάνει λάθος επιλογές κάτω από συγκεκριμένες συνθήκες. Ο ψυχολογικός παράγοντας που θα εξετάσουμε είναι η λεγόμενη *μεροληψία του παρόντος* (present bias). Η μεροληψία του παρόντος είναι η τάση που έχουμε να θεωρούμε τα κόστη και τα ωφέλη που έχουμε στο παρόν πιο σημαντικά από αυτά που θα έρθουν στο μέλλον. Για να δούμε δύο παραδείγματα:\n",
    "\n",
    "* Πολλές φορές ένα χρηματικό κέρδος σήμερα μας φαίνεται ελκυστικότερο από ένα χρηματικό κέρδος στο μέλλον, ακομα και αν το μελλοντικό κέρδος είναι μεγαλύτερο.\n",
    "\n",
    "* Πολλές φορές προτιμούμε να αναβάλουμε να πληρώσουμε κάτι σήμερα, ακόμα και αν η αποπληρωμή του στο μέλλον θα μας κοστίσει στην πραγματικότητα περισσότερο.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Έστω τώρα ότι μελετούμε τη συμπεριφορά ενός ατόμου, του Φάνη. Ο Φάνης πρέπει να εκτελέσει μια σειρά εργασιών, ξεκινώντας από μια εργασία $s$ και καταλήγοντας ολοκληρώνοντας μια εργασία $t$. Για να φτάσει στην $t$ πρέπει να εκτελέσει μια σειρά από ενδιάμεσες εργασίες, με συγκεκριμένη σειρά μεταξύ τους. Επίσης, μπορεί να είναι δυνατόν να το κάνει αυτό με περισσότερες από μία σειρά εργασιών. Για παράδειγμα, δείτε τον παρακάτω γράφο (από το άρθρο των Kleinberg και Oren, βλ. στο τέλος), όπου οι κόμβοι είναι οι εργασίες, και τα βάρη στις ακμές δείχνουν το κόστος (π.χ. σε ημέρες) που χρειάζεται ο Φάνης για να προχωρήσει από μια εργασία στην επόμενη."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"example_graph_1.png\" width=\"400\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ο Φάνης μπορεί να ξεκινήσει από το σημείο $s$ και να φτάσει στο σημείο $t$ με τους εξής τρόπους και κόστη:\n",
    "* $s \\rightarrow a \\rightarrow b \\rightarrow t$, με κόστος $16 + 2 + 2 = 20$.\n",
    "* $s \\rightarrow c \\rightarrow d \\rightarrow t$, με κόστος $8 + 8 + 8 = 24$.\n",
    "* $s \\rightarrow c \\rightarrow e \\rightarrow t$, με κόστος $8 + 2 + 16 = 26$.\n",
    "\n",
    "Αν λοιπόν δράσει με βάση τη λογική, θα επιλέξει το μονοπάτι $s \\rightarrow a \\rightarrow b \\rightarrow t$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Στην πραγματικότητα όμως ο Φάνης πλανάται και μεροληπτεί υπέρ του παρόντος. Έτσι, όταν βρίσκεται σε έναν κόμβο, εκτιμά το κόστος των συνδέσμων που πρόσκεινται στον κόμβο με βάση το πραγματικό τους κόστος (γιατί συμβαίνει τώρα), αλλά εκτιμά το κόστος των κατοπινών συνδέσμων υποβαθμίζοντάς το κατά έναν παράγοντα $b < 1$, ώστε αν το πραγματικό κόστος είναι $c$, του Φάνη θα του φανεί ότι είναι $bc$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ας δούμε λοιπόν τι μονοπάτι θα ακολουθήσει ο Φάνης, αν $b = 1/2$.\n",
    "1. Ξεκινάει από τον κόμβο $s$. Υπολογίζει το κόστος των μονοπατιών ως εξής:\n",
    "  * $s \\rightarrow a \\rightarrow b \\rightarrow t$, με κόστος $16 + (1/2)\\times 2 + (1/2)\\times 2 = 18$.\n",
    "  * $s \\rightarrow c \\rightarrow d \\rightarrow t$, με κόστος $8 + (1/2)\\times 8 + (1/2)\\times 8 = 16$.\n",
    "  * $s \\rightarrow c \\rightarrow e \\rightarrow t$, με κόστος $8 + (1/2)\\times 2 + (1/2)\\times 16 = 17$.\n",
    "  \n",
    "  Έτσι αποφασίζει να πάρει το *δεύτερο* μονοπάτι.\n",
    "  \n",
    "2. Τώρα βρίσκεται στον κόμβο $c$. Υπολογίζει εκ νέου το κόστος των μονοπατιών από το $c$ μέχρι το $t$ ως εξής:\n",
    "  * $c \\rightarrow d \\rightarrow t$, με κόστος $8 + (1/2)\\times 8 = 12$.\n",
    "  * $c \\rightarrow e \\rightarrow t$, με κόστος $2 + (1/2)\\times 16 = 10$.\n",
    "  \n",
    "  Έτσι αποφασίζει να αλλάξει, και να πάει στον κόμβο $e$, ακολουθώντας συνεπώς το *τρίτο* μονοπάτι.\n",
    "  \n",
    "3. Από τον κόμβο $e$ είναι μονόδρομος έως το $t$.\n",
    "\n",
    "Βλέπουμε λοιπόν ότι ο Φάνης δεν θα επιλέξει το μονομάτι $s \\rightarrow a \\rightarrow b \\rightarrow t$ με κόστος 20, αλλά το μονοπάτι $s \\rightarrow c \\rightarrow e \\rightarrow t$ με κόστος 26!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Σκοπός της εργασίας είναι, αν σας δίνεται ένας γράφος όπως ο παραπάνω, και μία παράμετρος $b$, να υπολογίζετε:\n",
    "* το βέλτιστο μονοπάτι\n",
    "* το μονοπάτι που πραγματικά θα επιλέξει ο Φάνης"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ένας τρόπος να το βρούμε αυτό, είναι να ακολουθήσουμε τα παρακάτω στάδια:\n",
    "\n",
    "1. Εύρεση όλων των μονοπατιών από το $s$ στο $t$.\n",
    "2. Εύρεση του πραγματικού κόστους κάθε μονοπατιού από το $s$ στο $t$ (και εντοπισμός του βέλτιστου μονοπατιού).\n",
    "3. Εκκίνηση από το $s$.\n",
    "4. Μέχρι να φτάσουμε στο $t$:\n",
    "  1. Υπολογισμός του κόστους κάθε μονοπατιού από τον κόμβο που βρισκόμαστε μέχρι το $t$, λαμβάνοντας υπόψη τη μεροληψία του παρόντος.\n",
    "  2. Μεταφορά στον κόμβο που αντιστοιχεί στο καλύτερο μονοπάτι που βρήκαμε στο βήμα 4.A.\n",
    "  3. Επανάληψη από το βήμα 4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Για να μπορέσουμε να υλοποιήσουμε τα στάδια αυτά, πρέπει να ξέρουμε πώς να βρίσκουμε όλα τα μονοπάτια μεταξύ δύο κόμβων ενός γράφου. Αυτό είναι εύκολο να γίνει, με μια παραλλαγή της κατά βάθος αναζήτησης. \n",
    "\n",
    "<img src=\"all_simple_paths_algorithm.png\" width=\"600\"/>\n",
    "\n",
    "Η παραλλαγή αυτή δουλεύει όπως και η βασική κατά βάθος αναζήτηση, κρατώντας το τρέχον μονοπάτι σε μία στοίβα ονόματι $\\mathit{path}$. Κάθε φορά που φτάνουμε στο στόχο μας, προσθέτουμε τη στοίβα $\\mathit{path}$ σε μία στοίβα $\\mathit{paths}$, η οποία περιέχει όλα τα μονοπάτια."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Απαιτήσεις Προγράμματος\n",
    "\n",
    "Κάθε φοιτητής θα εργαστεί σε αποθετήριο στο GitHub. Για να αξιολογηθεί μια εργασία θα πρέπει να πληροί τις παρακάτω προϋποθέσεις:\n",
    "\n",
    "* Για την υποβολή της εργασίας θα χρησιμοποιηθεί το ιδιωτικό αποθετήριο του φοιτητή που δημιουργήθηκε για τις ανάγκες του μαθήματος και του έχει αποδωθεί. Το αποθετήριο αυτό έχει όνομα του τύπου `username-algo-assignments`, όπου `username` είναι το όνομα του φοιτητή στο GitHub. Για παράδειγμα, το σχετικό αποθετήριο του διδάσκοντα θα ονομαζόταν `louridas-algo-assignments` και θα ήταν προσβάσιμο στο https://github.com/dmst-algorithms-course/louridas-algo-assignments. * Τυχόν άλλα αποθετήρια απλώς θα αγνοηθούν*.\n",
    "\n",
    "* Μέσα στο αποθετήριο αυτό θα πρέπει να δημιουργηθεί ένας κατάλογος `assignment-2018-1`.\n",
    "\n",
    "* Μέσα στον παραπάνω κατάλογο το πρόγραμμα θα πρέπει να αποθηκευτεί με το όνομα `present_bias.py`.\n",
    "\n",
    "* Δεν επιτρέπεται η χρήση έτοιμων βιβλιοθηκών γράφων ή τυχόν έτοιμων υλοποιήσεων των αλγορίθμων, ή τμημάτων αυτών. Επιτρέπεται η χρήση δομών δεδομένων της Python όπως στοίβες, λεξικά, κ.λπ.\n",
    "\n",
    "* Το πρόγραμμα θα πρέπει να είναι γραμμένο σε Python 3.\n",
    "\n",
    "* Το πρόγραμμα θα το καλεί ως χρήστης ως εξής (όπου `python` η κατάλληλη εντολή στο εκάστοτε σύστημα):\n",
    "\n",
    "```\n",
    "python present_bias.py <input_file> <bias_parameter> <start_node> <end_node>\n",
    "```\n",
    "\n",
    "Στην εντολή αυτή:\n",
    "  * Η παράμετρος `<input_file>` είναι ένα όνομα αρχείου που περιέχει το γράφο που θα εξετάσουμε\n",
    "  * Η παράμετρος `<bias_parameter>` είναι η παράμετρος $b$. \n",
    "  * Η παράμετρος `<start_node>` είναι ο κόμβος εκκίνησης.\n",
    "  * Η παράμετρος `<end_node>` είναι ο τελικός κόμβος.\n",
    "\n",
    "Τα αρχεία των γράφων θα έχουν την εξής μορφή:\n",
    "```\n",
    "s a 16\n",
    "s c 8\n",
    "a b 2\n",
    "b t 2\n",
    "c d 8\n",
    "d t 8\n",
    "c e 2\n",
    "e t 16\n",
    "```\n",
    "Βλέπουμε δηλαδή ότι αποτελούνται από γραμμές, όπου η κάθε γραμμή δηλώνει τη σύνδεση δύο κόμβων και το βάρος που έχει ο σχετικός σύνδεσμος. \n",
    "\n",
    "Η έξοδος του προγράμματος θα είναι δύο γραμμές:\n",
    "* Στην πρώτη γραμμή θα εμφανίζεται το βέλτιστο μονοπάτι και το κόστος του.\n",
    "* Στη δεύτερη γραμμή θα εμφανίζεται το μονοπάτι που θα ακολουθήσει ο Φάνης και το κόστος του."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Παραδείγματα Εκτέλεσης\n",
    " \n",
    "### Παράδειγμα 1\n",
    " \n",
    "Αν ο χρήστης καλέσει το πρόγραμμα για το αρχείο [example_graph_1.txt](example_graph_1.txt), με τον ακόλουθο τρόπο:\n",
    "\n",
    "```\n",
    "python present_bias.py example_graph_1.txt 0.5 s t\n",
    "```\n",
    "\n",
    "η έξοδος του προγράμματος θα πρέπει να είναι *ακριβώς* η παρακάτω:\n",
    "\n",
    "```\n",
    "['s', 'a', 'b', 't'] 20\n",
    "['s', 'c', 'e', 't'] 26\n",
    "```\n",
    "\n",
    "### Παράδειγμα 2\n",
    "\n",
    "Αν ο χρήστης καλέσει το πρόγραμμα για το αρχείο [example_graph_2.txt](example_graph_2.txt), με τον ακόλουθο τρόπο:\n",
    "\n",
    "```\n",
    "python present_bias.py example_graph_2.txt 0.5 start end\n",
    "```\n",
    "η έξοδος του προγράμματος θα πρέπει να είναι *ακριβώς* η παρακάτω:\n",
    "\n",
    "```\n",
    "['start', '5', '6', '7', '11', 'end'] 53\n",
    "['start', '5', '6', '7', '11', '8', 'end'] 56\n",
    "```\n",
    "Ο γράφος αυτός απεικονίζεται ως εξής:\n",
    "<img src=\"example_graph_2.png\" width=\"500\"/>\n",
    "\n",
    "### Παράδειγμα 3\n",
    "\n",
    "Ένα ενδιαφέρον φαινόμενο παρουσιάζεται στον παρακάτω γράφο:\n",
    "\n",
    "<img src=\"example_graph_3.png\" width=\"500\"/>\n",
    "\n",
    "Ο γράφος αυτός προσομοιάζει το τι γίνεται όταν αναβάλουμε κάτι, μέρα με την ημέρα. Έστω ότι οι κόμβοι από το 0 έως και το 6 είναι ημέρες και ο κόμβος $e$ αντιστοιχεί σε κάτι που πρέπει να κάνουμε, μία υποχρέωσή μας. Κάθε ημέρα έχουμε δύο επιλογές:\n",
    "\n",
    "* Να εκπληρώσουμε την υποχρέωσή μας. Το κόστος είναι το ίδιο για κάθε ημέρα, 10.\n",
    "\n",
    "* Να το αφήσουμε για την επόμενη. Η αναβολή έχει κόστος 1.\n",
    "\n",
    "Είναι φανερό, ότι το καλύτερο που έχει να κάνει ο Φάνης, προκειμένου να πάει από το 0 στο e, είναι να διασχίσει τον απευθείας σύνδεσμο, δηλαδή να μην το αναβάλει καθόλου. Αλλά αν $b = 0{,}8$, τότε κάθε ημέρα θα το αφήνει για την επόμενη, έτσι ώστε θα εξαντλήσει την προθεσμία που έχει, με το μέγιστο κόστος.\n",
    "\n",
    "Πράγματι, αν τρέξετε το πρόγραμμά σας για το αρχείο [example_graph_3.txt](example_graph_3.txt), που αντιστοιχεί στον παραπάνω γράφο, μπορείτε να εξερευνήσετε τα διάφορα σενάρια:\n",
    "\n",
    "```\n",
    "python present_bias.py example_graph_3.txt 0.5 0 e\n",
    "\n",
    "['0', 'e'] 10\n",
    "['0', '1', '2', '3', '4', '5', '6', 'e'] 16\n",
    "\n",
    "python3 present_bias.py example_graph_3.txt 0.8 0 e\n",
    "['0', 'e'] 10\n",
    "['0', '1', '2', '3', '4', '5', '6', 'e'] 16\n",
    "\n",
    "python3 present_bias.py example_graph_3.txt 0.9 0 e\n",
    "\n",
    "['0', 'e'] 10\n",
    "['0', 'e'] 10\n",
    "```\n",
    "\n",
    "Καλή Επιτυχία!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Για Περισσότερες Πληροφορίες\n",
    "\n",
    "* Αν θέλετε μια ευκολοδιάβαστη εισαγωγή στις εφαρμογές των Συμπεριφορικών Οικονομικών, δείτε το βιβλίο: Richard H. Thaler and Cass R. Susstein, Nudge: Improving Decisions About Health, Wealth and Happiness, Penguin, 2009.\n",
    "\n",
    "* Για μια εισαγωγή στις εφαρμογές των γράφων σε προβλήματα ασυνεπούς συμπεριφοράς δείτε το άρθρο: Jon Kleinberg and Sigal Oren, Time-inconsistent planning: a computational problem in behavioral economics, Communications of the ACM 61, 3 (February 2018), 99-107. DOI: https://doi.org/10.1145/3176189. Από το άρθρο αυτό προέρχεται και ο πρώτος γράφος παράδειγμα, και η έμπνευση για την παρούσα εργασία.\n",
    "\n",
    "* Το θέμα της αναβλητικότητας στα οικονομικά το έχει πραγματευτεί ο Νομπελίστας George Akerlof, βλ.: George A. Akerlof, Procrastination and obedience, American Economic Review, 81, 2 (May 1991), 1-19.\n",
    "\n",
    "* Για τους τρόπους με τους οποίους αλλάζουμε την εκτίμησή μας κατά μήκος του χρόνου, βλ.: Shane Frederick, George Loewenstein and Ted O'Donoghue, Time Discounting and Time Preference: A Critical Review, Journal of Economic Literature, 40, 2 (June 2002), pp. 351-401."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}