Λήμμα των Σάπλεϊ-Φόλκμαν

Προκαταρκτικά

Το λήμμα των Σάπλεϊ- Φόλκμαν εξαρτάται από τους ακόλουθους ορισμούς και τα αποτελέσματα από την κυρτή γεωμετρία.

Κυρτό κύτους

Για κάθε υποσύνολο Q ενός πραγματικού διανυσματικού χώρου, είναι κυρτό κύτους του Conv(Q) και μάλιστα είναι το ελάχιστο κυρτό σύνολο που περιέχει το Q. Έτσι Conv(Q) είναι η τομή όλων των κυρτών συνόλων που καλύπτουν το Q.Το κυρτό περίβλημα ενός συνόλου μπορεί ισοδύναμα να ορίζεται να είναι το σύνολο όλων των κυρτών συνδυασμών σημείων στο Q.  Για παράδειγμα, το κυρτό του κύτους του συνόλου των ακεραίων {0,1} είναι το κλειστό διάστημα των πραγματικών αριθμών [0,1], το οποίο περιέχει τον ακέραιο αριθμό τελικών σημείων. Το κυρτό κύτους του μοναδιαίου κύκλου είναι ο δίσκος που περιέχει τον μοναδιαίο κύκλο.

Διάσταση ενός πραγματικού διανυσματικού χώρου

Αντίθετα, το λήμμα Σάπλει-Φόλκμαν χαρακτηρίζει τη διάσταση των πεπερασμένων διαστάσεων πραγματικών διανυσματικών χώρων. Δηλαδή, αν ένας διανυσματικός χώρος υπακούει στο λήμμα των Σάπλει-Φόλκμαν για ένα φυσικό αριθμό D, και για κανένα αριθμό μικρότερο από το D, τότε διάσταση είναι ακριβώς D.  Το λήμμα Σάπλει-Φόλκμαν ισχύει μόνο για πεπερασμένης διάστασης διανυσματικών χώρων .

Αποδείξεις και υπολογισμοί

Η πρωτότυπη απόδειξη του λήμματος των Σάπλει-Φόλκμαν διαπίστωσε μόνο την ύπαρξη της παράστασης, αλλά δεν παρείχε έναν αλγόριθμο για τον υπολογισμό της παράστασης: Παρόμοιες αποδείξεις έχουν δοθεί από τους Arrow και Hahn, Cassels, και Schneider  μεταξύ άλλων. Μια αφηρημένη και κομψή απόδειξη από τον Ekeland έχει επεκταθεί από Artstein. Οι διάφορες αποδείξεις έχουν εμφανιστεί σε αδημοσίευτα έγγραφα, επίσης.  Το 1981, ο Σταρ δημοσίευσε μια επαναληπτική μέθοδο για τον υπολογισμό μιας εκπροσώπησης ενός δοσμένου σημείου. Ωστόσο, η υπολογιστική απόδειξη του παρέχει πιο αδύναμη δέσμευση από ό, τι το αρχικό αποτέλεσμα.

Εφαρμογές

Το λήμμα Σάπλει-Φόλκμαν επιτρέπει στους ερευνητές να επεκτείνουν τα αποτελέσματα για τα αθροίσματα Μινικόφσκι στα κυρτά σύνολα σε αθροίσματα γενικών συνόλων, τα οποία δεν χρειάζεται να είναι κυρτά. Τέτοια αθροίσματα συνόλων προκύπτουν στην οικονομία, στη μαθηματική βελτιστοποίηση, και στη θεωρία πιθανοτήτων, σε κάθε μία από αυτές τις τρεις μαθηματικές επιστήμες, η μη-κυρτότητα είναι ένα σημαντικό χαρακτηριστικό των εφαρμογών.

Οικονομικά

Στα οικονομικά, οι προτιμήσεις του καταναλωτή ορίζονται πάνω από όλα τα «καλάθια» των εμπορευμάτων. Κάθε καλάθι εκπροσωπείται από ένα μη-αρνητικό διάνυσμα, των οποίων οι συντεταγμένες αντιπροσωπεύουν τις ποσότητες των εμπορευμάτων. Σε αυτό το σύνολο από τα καλάθια, μια καμπύλη αδιαφορίας ορίζεται για κάθε καταναλωτή. Η καμπύλη αδιαφορίας του καταναλωτή περιλαμβάνει όλα τα καλάθια των προϊόντων που ο καταναλωτής θεωρεί ότι είναι ισοδύναμα: Δηλαδή, για κάθε ζεύγος καλαθιών στην ίδια καμπύλη αδιαφορίας, οι καταναλωτές δεν προτιμούν ένα καλάθι περισσότερο από ένα άλλο. Μέσα από κάθε καλάθι εμπορευμάτων περνάει μια καμπύλη αδιαφορίας. Το σύνολο προτίμησης ενός καταναλωτή (σε σχέση με μια καμπύλη αδιαφορίας) είναι η ένωση της καμπύλης αδιαφορίας και όλα τα καλάθια αγαθών που ο καταναλωτής προτιμά επί της καμπύλης αδιαφορίας. Οι προτιμήσεις ενός καταναλωτή είναι κυρτές αν όλα αυτά τα σύνολα προτίμησης είναι κυρτά.
Η βελτιστοποίηση των καλαθιών αγαθών συμβαίνει όταν η γραμμή του προϋπολογισμού υποστηρίζει το σύνολο προτιμήσεων του καταναλωτή, όπως φαίνεται στο διάγραμμα. Αυτό σημαίνει ότι το βέλτιστο καλάθι είναι στο υψηλότερο δυνατό σημείο της καμπύλη αδιαφορίας όταν δοθεί η γραμμή του προϋπολογισμού, η οποία ορίζεται από την άποψη το διάνυσμα τιμών και εισοδήματος του καταναλωτή (κληροδότημα vector). Έτσι, το σύνολο των βέλτιστων καλαθιών είναι η συνάρτηση των  τιμών, και η λειτουργία αυτή ονομάζεται ζήτηση του καταναλωτή. Αν το σύνολο προτίμησης είναι κυρτό, τότε κάθε τιμή της ζήτησης του καταναλωτή είναι ένα κυρτό σύνολο, για παράδειγμα, ένα μοναδικό βέλτιστο καλάθι ή μία γραμμή τμημάτων των καλαθιών.

Μη κυρτές προτιμήσεις

Ωστόσο, εάν ένα σύνολο προτίμησης είναι μη-κυρτό, τότε ορισμένες τιμές καθορίζονται σε μια γραμμή του προϋπολογισμού που υποστηρίζει δύο ξεχωριστά βέλτιστα καλάθια. Για παράδειγμα, μπορούμε να φανταστούμε ότι, για ζωολογικούς κήπους, ένα λιοντάρι έχει κόστος όσο ένας αετό, και επιπλέον ότι ο προϋπολογισμός ενός ζωολογικού κήπου αρκεί για έναν αετό ή ένα λιοντάρι. Μπορούμε να υποθέσουμε, επίσης, ότι ένας φύλακας σε ζωολογικό κήπο βλέπει κάθε ζώο, εξίσου πολύτιμα. Στην περίπτωση αυτή, ο ζωολογικός κήπος θα αγοράζε είτε ένα λιοντάρι ή ένα αετό. Φυσικά, ένας σύγχρονος ζωολογικός κήπος δεν θέλει να αγοράσει το ήμισυ του αετού και το ήμισυ του λιονταριού (ή γρύπα)! Έτσι, οι προτιμήσεις του ζωολογικού είναι μη-κυρτό: Ο ζωολογικός κήπος προτιμά να έχουν ζώα που να μην είναι κυρτά ή και τα δύο.
Όταν τα σύνολα προτιμήσεων των καταναλωτών είναι μη-κυρτά,τότε (για ορισμένες τιμές), η ζήτηση των καταναλωτών δεν είναι συνδέεται. Μια ασύνδετη ζήτηση συνεπάγεται κάποια ασυνεχή συμπεριφορά του καταναλωτή, όπως συζητήθηκε από Harold Hotelling:
Αν οι καμπύλες αδιαφορίας για τις αγορές θεωρηθεί ότι διαθέτουν έναν κυματιστό χαρακτήρα, κυρτά προς την προέλευση, σε ορισμένες περιφέρειες και κοίλα σε άλλα, καταλήγουμε στο συμπέρασμα ότι μόνο τα τμήματα που είναι κυρτά προς την καταγωγή, μπορούν να θεωρηθούν ότι κατέχουν κάποια σημασία , δεδομένου ότι τα άλλα είναι ουσιαστικά μη παρατηρήσιμα. Μπορούν να ανιχνευθούν μόνο από τις ασυνέχειες που μπορεί να εμφανιστούν σε ζήτηση με διακύμανση στην τιμή-αναλογίες, οδηγεί σε ένα απότομα άλμα από ένα σημείο επαφής σε ένα χάσμα, όταν η ευθεία γραμμή περιστρέφεται. Ενώ οι εν λόγω ασυνέχειες μπορούν να αποκαλύψουν την ύπαρξη χασμάτων, ποτέ όμως δεν μπορούν να μετρήσουν το βάθος τους. Τα κοίλα τμήματα των καμπυλών αδιαφορίας και πολλών διαστάσεων γενίκευσής τους, εάν υπάρχουν, πρέπει να παραμείνουν για πάντα στην αφάνεια αμέτρητης. 
Οι δυσκολίες της μελέτης σε μη κυρτές προτιμήσεις τονίζεται από τον Herman Wold  και πάλι από τον Paul Samuelson, ο οποίος έγραψε ότι οι μη κυρτές είναι «τυλιγμένες στο αιώνιο σκοτάδι ...»,  σύμφωνα με τον Diewert.
Παρ 'όλα αυτά, οι μη κυρτές προτιμήσεις φωτίστηκαν το 1959-1961 με μια σειρά από εργασίες στο The Journal of Political Economy (JPE). Οι κύριοι παράγοντες που συνέβαλαν ήταν ο Farrell, 
 Bator,  ο Koopmans,  και ο Rothenberg.  Ειδικότερα, η εργασία του Rothenberg ανέφερε την προσέγγιση της κυρτότητας αθροισμάτων των μη κυρτών συνόλων. Αυτές οι JPE-εργασίες διεγείρονται από ένα έγγραφο από τους Lloyd Shapley και Martin Shubik, οι οποίες θεωρούνται κυρτές προτιμήσεις του καταναλωτή και εισήγαγαν την έννοια της «κατά προσέγγισης ισορροπίας».  Οι JPE εργασίες και η εργασία των Shapley-Shubik επηρέασε μια άλλη έννοια της «οιωνοί ισορροπίας», σύμφωνα με τον Robert Aumann.

Η εργασία του Σταρ το 1969 και η σύγχρονη οικονομία

Οι προηγούμενες δημοσιεύσεις σχετικά με τη μη-κυρτότητα και τα οικονομικά συλλέχθηκαν σε μια σχολιασμένη βιβλιογραφία από τον Kenneth Arrow. Αποτέλεσαν τη βιβλιογραφία, ώστε ο [[Starr}}, ο οποίος ήταν τότε ένας προπτυχιακός φοιτητής του Arrow σε προηγμένα μαθήματα μαθηματικών-οικονομικών.
Ο Starr διαπίστωσε ότι
«Στο σύνολό τους, η διαφορά μεταξύ μιας κατανομής στην πλασματική οικονομία που παράγεται από [τη λήψη των κυρτών καταναλωτών και των παραγόμενων συνόλων] και κάποια κατανομή στην πραγματική οικονομία οριοθετείται κατά τρόπο που να είναι ανεξάρτητη από τον αριθμό των οικονομικών παραγόντων. Ως εκ τούτου, ο μέσος παράγοντας βιώνει μια απόκλιση από την προβλεπόμενη ενέργεια που εξαφανίζει τη σημασία, καθώς ο αριθμός των παραγόντων πηγαίνει στο άπειρο ».
Μετά το 1969 η εργασία του Starr και τα αποτελέσματα των Shapley-Folkman-Starr έχουν χρησιμοποιηθεί ευρέως στην οικονομική θεωρία. Ο Roger Guesnerie συνοψίζει τις οικονομικές επιπτώσεις τους: «Μερικά βασικά αποτελέσματα που επιτεύχθηκαν με την παραδοχή της κυρτότητας παραμένει (περίπου) σχετικό σε περιπτώσεις όπου δεν υπάρχει κυρτότητα. Για παράδειγμα, σε οικονομίες με μεγάλη πλευρά κατανάλωσης, οι nonconvexities προτίμησεις δεν καταστρέφουν τα πρότυπα αποτελέσματα».  «Η παραγωγή αυτών των αποτελεσμάτων σε γενική μορφή υπήρξε ένα από τα σημαντικότερα επιτεύγματα της μεταπολεμικής οικονομικής θεωρίας», έγραψε ο Guesnerie.  Το θέμα των μη κυρτών συνόλων στα οικονομικά έχει μελετηθεί από πολλούς νομπελίστες: Arrow (1972) , Robert Aumann (2005), Gérard Debreu  (1983), Tjalling Koopmans (1975), Paul Krugman (2008), και Paul Samuelson (1970). Το συμπληρωματικό θέμα των κυρτών συνόλων στα οικονομικά έχει τονιστεί από αυτούς, μαζί με τους Leonid Hurwicz, Leonid Kantorovich (1975), και Robert Solow (1987).  Τα αποτελέσματα των Shapley-Folkman-Starr έχουν προβληθεί στην οικονομική βιβλιογραφία : στην μικροοικονομική θεωρία, στην κλασική θεωρία της γενικής ισορροπίας,  στα δημόσια οικονομικά   (συμπεριλαμβανομένων των ανεπαρκειών της αγοράς), καθώς και στην θεωρία των παιγνίων, στη μαθηματική οικονομία, και στα εφαρμοσμένα μαθηματικά (για τους οικονομολόγους) . Τα αποτελέσματα των Shapley-Folkman-Starr έχουν επίσης επηρεάσει την οικονομία της έρευνας με τη χρήση του μέτρου και της θεωρίας ολοκλήρωσης.

Μαθηματική βελτιστοποίηση

Το λήμμα των Σάπλει-Φόλκμαν έχει χρησιμοποιηθεί για να εξηγήσει γιατί τα μεγάλα προβλήματα ελαχιστοποίησης με μη-κοιλότητα μπορούν σχεδόν να λυθούν (με επαναληπτικές μεθόδους των οποίων η σύγκλιση απόδειξης δηλώνεται μόνο για κυρτά προβλήματα). Το λήμμα των Σάπλει-Φόλκμαν έχει ενθαρρύνει τη χρήση των μεθόδων ελαχιστοποίησης των κυρτών σε άλλες εφαρμογές με αθροίσματα από πολλές λειτουργίες.