חלוקה הוגנת

חלוקה הוגנת היא בעיה בתורת המשחקים הדנה בחלוקת משאב ו/או נכסים מוחשיים בעלי ערך כלכלי בין קבוצת אנשים בעלי זכויות  באופן ששביעות הרצון של כלל חברי הקבוצה יהיה מרבי ולא תמצא חלוקה אחרת שתגדיל את שביעות הרצון של הקבוצה כולה. על המשאב להיות ניתן לחלוקה, כלומר שאינו מאבד את ערכו עם החלוקה. חלוקה זו מוגדרת כחלוקה יציבה .
הבעיה קלה יותר כאשר לשחקנים יש העדפות שונות לכל אחד מחלקי המשאב. לדוגמה, בבעיית חלוקת העוגה, אם שחקן A מעדיף את החלק עם קרם השוקולד בעוגה, ושחקן B מעדיף את החלק עם הקרם וונילה בעוגה. בתנאים כאלו, n השחקנים יקבלו יותר מהחלק היחסי שלהם בעוגה, כלומר יותר מ-. מצד שני, קיום עדיפויות שונות לשחקנים שונים גורר צורות רבות יותר של חלוקות הוגנות.
'הוגנות' משמעה שכל אחד מהשחקנים מקבל לפחות את החלק היחסי שלו בעוגה. חלוקה הוגנת חלשה יותר מחלוקה נטולת-קנאה. חלוקת משימות היא סוג של חלוקה הוגנת. 
רוב החלוקות שנקראות חלוקות הוגנות, אינן באמת נחשבות לחלוקות הוגנות על-פי הגדרה זו, כיוון שהן מערבות בורר. חלוקות אלו הן בדרך כלל תאוריות מתמטיות שמחקות בעיות מהחיים האמיתיים. בתלמוד מוצגות הלכות סבוכות על חלוקת רכוש שבעליו הפסיד את רכושו בפשיטת רגל, רוב האנשים יחשיבו הלכות אלו כהוגנות. אך החלטות אלו נקבעות על ידי גורם חיצוני ולא על ידי תובעי הרכוש, לכן חלוקה כזו אינה חלוקה הוגנת. חלוקה הוגנת מבוססת על כך שהחלוקה תעשה על ידי השחקנים עצמם או על ידי מגשר, אך לא על ידי בורר.

שני שחקנים

הפתרון עבור שני שחקנים נעשה באמצעות שיטת 'חלק ובחר'. שחקן אחד מחלק פרוסת עוגה לשני חלקים הנראים לו שווים והשחקן השני בוחר ראשון איזה חלק הוא רוצה מבין השניים. לשחקן שמחלק יש סיבה לחלק בצורה כמה שיותר הוגנת. אחרת, הוא עלול להישאר עם החלק הקטן יותר. חלוקה זו היא חלוקה נטולת-קנאה וגם חלוקה יחסית.
פרוצדורת הסכין הזז מאת אוסטין קובעת חלוקה מדויקת עבור שני שחקנים. השחקן הראשון מחזיק שני סכינים מעל העוגה, אחד בצד השמאלי ואחד בצד הימני של העוגה וחצי עוגה נמצאת ביניהם. הוא מזיז את הסכינים ימינה תוך שהוא שומר תמיד על חלק ששווה בעינו לחצי עוגה בין שני הסכינים.  אם הוא הגיע לקצה הימני, הסכין השמאלי הקיצוני צריך להיות ממוקם היכן שהסכין הימני מוקם לראשונה. השחקן השני עוצר את הסכינים כאשר הוא חושב שיש חלק השווה בעינו לחצי מהעוגה בין שני הסכינים. נקודה זו תמיד קיימת על-פי משפט ערך הביניים.

הרבה שחקנים

חלוקה הוגנת לשלושה שחקנים ויותר מסובכת מחלוקה הוגנת עבור שני שחקנים.
חלוקה יחסית היא הקלה ביותר במצב זה. ניתן להגביל את מספר החתכים ובכך להקשות את הבעיה.
חלוקה נטולת-קנאה עבור שלושה שחקנים הוצגה לראשונה ב-1960 על ידי ג'ון סלפרידג' מאוניברסיטת צפון-אלינוי וג'ון הורטון קונווי מאוניברסיטת קיימברידג'. האלגוריתם הטוב ביותר משתמש בלכל הפחות חמישה חתכים.
פרוצדורת חלוקת העוגה הראשונה עבור ארבעה שחקנים או יותר שמציגה חלוקה נטולת-קנאה לכל מספר של שחקנים פורסמה ב-1992 על ידי סטיב ברהמס ואלן טיילור. מספר החתכים אינו חסום. ב-1997 פורסם פתרון חסום לארבעה שחקנים.
לא קיימות פרוצדורות דיסקרטיות לחלוקה מדויקת, אפילו לא לשני שחקנים. פרוצדורת הסכין הזז היא הפתרון הטוב ביותר שקיים. פרוצדורות לחלוקה מדויקת עבור שלושה שחקנים או יותר לא קיימות כלל. פרוצדורה לחלוקה 'כמעט מדויקת' קיימת והיא גם חלוקה נטולת-קנאה שיכולה להשיג כל רמה של דייקנות. 
החלוקה מסתמכת על המכרז ההולנדי, כאשר סכין עוברת לאט לאורך העוגה (מימין לשמאל לדוגמה)  והראשון שעוצר את הסכין - מקבל את החלק שנמצא מימין וכך ממשיכים. ההיגיון הוא שכל "שחקן" עוצר את הסכין בהתאם לכמה הוא מעריך את החלק של העוגה. כך ממשיכים עד לסוף העוגה ומי שלא הציע בזמן - מפסיד ולא מקבל כלום.

סוגי חלוקה

ישנן פרוצדורות דיסקרטיות לבעיית חלוקת עוגה, בהם השחקנים פועלים לפי מספר פעולות סופיות. לעומת זאת, פרוצדורת הסכין הזז נעשית על ידי פעולות רציפות. כלומר, שחקן אחד מזיז את הסכין מעל העוגה ושחקן שני עוצר אותו כשהוא רוצה שיחתוך את העוגה.
בעיית חלוקת משימות היא שימוש ידוע בחלוקה הוגנת. בעיית חלוקת משימות מקבילה לבעיית חלוקת העוגה. כעת המשאב אותו מחלקים הוא לא רצוי וכל אחד מהשחקנים מקווה לקבל כמה שפחות. שיטת 'חלק ובחר' טובה לבעיית חלוקת משימות.
הלמה של שפרנר משיגה פתרון יעיל ומהיר למספר בעיות בחלוקה הוגנת. כמו כן, ניתן להשתמש בלמה של שפרנר כדי לקבל פתרון קרוב ככל האפשר לחלוקה נטולת-קנאה למספר רב של שחקנים. 
כאשר מחלקים קרקע, תנאי עיקרי וחשוב הוא שהקרקעות יהיו רציפות ולא נפרדות. דוגמה לכך היא חלוקת ברלין לאחר מלחמת העולם השנייה  יצרה ארבעה חלקים רציפים.