Welfare maximization
ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಯು ಅರ್ಥಶಾಸ್ತ್ರ ಮತ್ತು ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದಲ್ಲಿ ಅಧ್ಯಯನ ಮಾಡಲಾದ ಉತ್ತಮಗೊಳಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಯಾಗಿದೆ. ವಿವಿಧ ಉಪಯುಕ್ತತೆ ಕಾರ್ಯಗಳನ್ನು ಹೊಂದಿರುವ ಏಜೆಂಟ್ಗಳ ನಡುವೆ ವಸ್ತುಗಳ ಗುಂಪನ್ನು ವಿಭಜಿಸುವುದು ಇದರ ಗುರಿಯಾಗಿದೆ, ಉದಾಹರಣೆಗೆ ಕಲ್ಯಾಣ-ಏಜೆಂಟ್ಗಳ ಉಪಯುಕ್ತತೆಗಳ ಮೊತ್ತ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ-ಸಾಧ್ಯವಾದಷ್ಟು ಹೆಚ್ಚು. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಉಪಯುಕ್ತತೆಯ ನಿಯಮವನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಐಟಂ ಹಂಚಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಗುರಿಯಾಗಿದೆ. ಸಂಯೋಜಿತ ಹರಾಜಿನ ಸಂದರ್ಭದಲ್ಲಿ ಸಮಾನವಾದ ಸಮಸ್ಯೆಯನ್ನು ವಿಜೇತರ ನಿರ್ಣಯದ ಸಮಸ್ಯೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಪ್ರತಿ ಏಜೆಂಟ್ ವಸ್ತುಗಳ ಸೆಟ್ಗಳ ಮೇಲೆ ಬಿಡ್ಗಳ ಪಟ್ಟಿಯನ್ನು ಸಲ್ಲಿಸುತ್ತಾರೆ ಮತ್ತು ಯಾವ ಬಿಡ್ ಅಥವಾ ಬಿಡ್ಗಳನ್ನು ಗೆಲ್ಲಬೇಕು ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವುದು ಗುರಿಯಾಗಿದೆ, ಅಂದರೆ ಗೆಲ್ಲುವ ಬಿಡ್ಗಳ ಮೊತ್ತವು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನಗಳು m ವಸ್ತುಗಳ ಒಂದು ಸೆಟ್ M ಇದೆ, ಮತ್ತು n ಏಜೆಂಟ್ಗಳ ಒಂದು ಸೆಟ್ N ಇದೆ. ಎನ್ ನಲ್ಲಿರುವ ಪ್ರತಿ ಏಜೆಂಟ್ ಐ ಒಂದು ಉಪಯುಕ್ತತೆಯ ಕಾರ್ಯವನ್ನು ಹೊಂದಿದೆ. ಕಾರ್ಯವು ವಸ್ತುಗಳ ಪ್ರತಿಯೊಂದು ಸಂಭವನೀಯ ಉಪಗುಂಪಿಗೆ ನೈಜ ಮೌಲ್ಯವನ್ನು ನಿಗದಿಪಡಿಸುತ್ತದೆ. ಯುಟಿಲಿಟಿ ಕಾರ್ಯಗಳು ಮೊನೊಟೋನ್ ಸೆಟ್ ಕಾರ್ಯಗಳಾಗಿವೆ ಎಂದು ಸಾಮಾನ್ಯವಾಗಿ ಭಾವಿಸಲಾಗುತ್ತದೆ, ಅಂದರೆ, ಸೂಚಿಸುತ್ತದೆ. ಎಂದು ಕೂಡ ಊಹಿಸಲಾಗಿದೆ. ಏಕತಾನತೆಯೊಂದಿಗೆ, ಇದು ಎಲ್ಲಾ ಉಪಯುಕ್ತತೆಗಳು ಋಣಾತ್ಮಕವಲ್ಲವೆಂದು ಸೂಚಿಸುತ್ತದೆ. ಹಂಚಿಕೆಯು, ಪ್ರತಿ ಏಜೆಂಟ್ಗೆ ಒಂದು ಉಪಗುಂಪನ್ನು ಸೂಚಿಸುವ ರೀತಿಯಲ್ಲಿ, ವಸ್ತುಗಳನ್ನು ಪ್ರತ್ಯೇಕವಾದ ಉಪಗುಂಪುಗಳಾಗಿ ವಿಂಗಡಿಸುವ ಕ್ರಮವಾಗಿದೆ. ಹಂಚಿಕೆಯ ಕಲ್ಯಾಣವು ಏಜೆಂಟ್ಗಳ ಉಪಯುಕ್ತತೆಗಳ ಮೊತ್ತವಾಗಿದೆಃ ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಯೆಂದರೆಃ W (X) ಅನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವ X ಹಂಚಿಕೆಯನ್ನು ಹುಡುಕಿ. ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಯು ಅನುಮತಿಸಲಾದ ಉಪಯುಕ್ತತೆ ಕಾರ್ಯಗಳ ಪ್ರಕಾರ, ಅಲ್ಗಾರಿದಮ್ ಉಪಯುಕ್ತತೆ ಕಾರ್ಯಗಳನ್ನು ಪ್ರವೇಶಿಸುವ ವಿಧಾನ ಮತ್ತು ಅನುಮತಿಸಲಾದ ಹಂಚಿಕೆಗೆ ಹೆಚ್ಚುವರಿ ನಿರ್ಬಂಧಗಳಿವೆಯೇ ಎಂಬುದನ್ನು ಅವಲಂಬಿಸಿ ಅನೇಕ ರೂಪಾಂತರಗಳನ್ನು ಹೊಂದಿದೆ. ಅಡಿಟಿವ್ ಏಜೆಂಟ್ ಒಂದು ಯುಟಿಲಿಟಿ ಫಂಕ್ಷನ್ ಅನ್ನು ಹೊಂದಿದ್ದು ಅದು ಅಡಿಟಿವ್ ಸೆಟ್ ಫಂಕ್ಷನ್ ಆಗಿದೆಃ ಪ್ರತಿ ಅಡಿಟಿವ್ ಏಜೆಂಟ್ i ಮತ್ತು ಐಟಂ j ಗೆ, ಒಂದು ಮೌಲ್ಯವಿದೆ, ಅಂದರೆ ಪ್ರತಿ ಸೆಟ್ Z ಐಟಂಗಳಿಗೆ. ಎಲ್ಲಾ ಏಜೆಂಟ್ಗಳು ಸಂಯೋಜಕವಾಗಿದ್ದಾಗ, ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯನ್ನು ಸರಳ ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಯಿಂದ ಮಾಡಬಹುದುಃ ಪ್ರತಿ ಐಟಂ ಜೆ ಅನ್ನು ಗರಿಷ್ಠವಾದ ಏಜೆಂಟ್ಗೆ ನೀಡಿ (ಸಂಬಂಧಗಳನ್ನು ಅನಿಯಂತ್ರಿತವಾಗಿ ಮುರಿಯುವುದು). ಹಂಚಿಕೆಗೆ ಹೆಚ್ಚುವರಿ ನಿರ್ಬಂಧಗಳು ಇದ್ದಾಗ ಸಮಸ್ಯೆಯು ಹೆಚ್ಚು ಸವಾಲಿನದ್ದಾಗುತ್ತದೆ. ನ್ಯಾಯೋಚಿತತೆಯ ನಿರ್ಬಂಧಗಳು ನ್ಯಾಯಯುತವಾದ ಎಲ್ಲಾ ಹಂಚಿಕೆಗಳಲ್ಲಿ ಕಲ್ಯಾಣವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು ಒಬ್ಬರು ಬಯಸಬಹುದು, ಉದಾಹರಣೆಗೆ, ಒಂದು ವಸ್ತುವಿನವರೆಗೆ ಅಸೂಯೆ-ಮುಕ್ತ (ಇಎಫ್ 1), ಒಂದು ವಸ್ತುವಿನವರೆಗೆ ಅನುಪಾತದಲ್ಲಿ (ಪಿಆರ್ಒಪಿ 1), ಅಥವಾ ಒಂದು ವಸ್ತುವಿನವರೆಗೆ (ಇಕ್ಯೂ 1) ಸಮಾನವಾಗಿರುತ್ತದೆ. n ಬದಲಾಗುತ್ತಿರುವಾಗ ಈ ಸಮಸ್ಯೆಯು ಬಲವಾಗಿ NP-ಗಟ್ಟಿಯಾಗಿರುತ್ತದೆ. ಯಾವುದೇ ಸ್ಥಿರ n ≤ 2 ಗೆ, ಸಮಸ್ಯೆಯು ದುರ್ಬಲವಾಗಿ NP-ಕಠಿಣವಾಗಿದೆ, ಮತ್ತು ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಆಧರಿಸಿದ ಹುಸಿ-ಬಹುಪದೀಯ ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಹೊಂದಿದೆ. n = 2 ಗೆ, ಸಮಸ್ಯೆಯು ಸಂಪೂರ್ಣ ಬಹುಪದ-ಸಮಯದ ಅಂದಾಜು ಯೋಜನೆಯನ್ನು ಹೊಂದಿದೆ. ಕೆಲವು ಏಜೆಂಟ್ ಪ್ರಕಾರಗಳು, ಕೆಲವು ಐಟಂ ಪ್ರಕಾರಗಳು ಅಥವಾ ಸಣ್ಣ ಮೌಲ್ಯದ ಮಟ್ಟಗಳು ಇದ್ದಾಗ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಕ್ರಮಾವಳಿಗಳಿವೆ. ಏಜೆಂಟ್ಗಳ ಸಂಯೋಜಕ ಉಪಯುಕ್ತತೆಗಳು ದ್ವಿಮಾನವಾಗಿರುವಾಗ (ಪ್ರತಿ ವಸ್ತುವಿನ ಮೌಲ್ಯವು 0 ಅಥವಾ 1 ಆಗಿರುತ್ತದೆ), ಹಾಗೆಯೇ ಸಾಮಾನ್ಯೀಕೃತ ದ್ವಿಮಾನ ಎಂದು ಕರೆಯಲಾಗುವ ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ವರ್ಗದ ಉಪಯುಕ್ತತೆಗಳಿಗೂ ಸಹ ಈ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಗಳು ಹಂಚಿಕೆಗೆ ಮತ್ತೊಂದು ನಿರ್ಬಂಧವೆಂದರೆ ಕಟ್ಟುಗಳು ಮ್ಯಾಟ್ರಾಯಿಡ್ನ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳಾಗಿರಬೇಕು. ಉದಾಹರಣೆಗೆ, ಪ್ರತಿ ಬಂಡಲ್ ಗರಿಷ್ಠ ಕೆ ಐಟಂಗಳನ್ನು ಹೊಂದಿರಬೇಕು, ಅಲ್ಲಿ ಕೆ ಒಂದು ಸ್ಥಿರ ಪೂರ್ಣಾಂಕವಾಗಿದೆ (ಇದು ಏಕರೂಪದ ಮ್ಯಾಟ್ರಾಯಿಡ್ಗೆ ಅನುರೂಪವಾಗಿದೆ). ಅಥವಾ, ವಸ್ತುಗಳನ್ನು ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು, ಮತ್ತು ಪ್ರತಿ ಬಂಡಲ್ ಪ್ರತಿ ವರ್ಗ ಸಿ ಯಿಂದ ಗರಿಷ್ಠ ಕೆಸಿ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರಬೇಕು (ಇದು ಪಾರ್ಟಿಷನ್ ಮ್ಯಾಟ್ರಾಯಿಡ್ಗೆ ಅನುರೂಪವಾಗಿದೆ). ಸಾಮಾನ್ಯವಾಗಿ, ಪ್ರತಿ ಏಜೆಂಟ್ಗೆ ವಿಭಿನ್ನ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಇರಬಹುದು, ಮತ್ತು ಹಂಚಿಕೆಯು ಪ್ರತಿ ಏಜೆಂಟ್ಗೆ ಅವರ ಸ್ವಂತ ಮ್ಯಾಟ್ರಾಯಿಡ್ನ ಸ್ವತಂತ್ರ ಸೆಟ್ ಆಗಿರುವ ಉಪಗುಂಪು ಕ್ಸಿ ಅನ್ನು ನೀಡಬೇಕು. ಹೆಟೆರೋಜೀನಿಯಸ್ ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಗಳ ಅಡಿಯಲ್ಲಿ ಸಂಯೋಜಕ ಉಪಯುಕ್ತತೆಗಳೊಂದಿಗೆ ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ, ತೂಕದ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಛೇದಕ ಸಮಸ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಮೂಲಕ ಮಾಡಬಹುದು. ಒಟ್ಟು-ಪರ್ಯಾಯ ಏಜೆಂಟ್ಗಳು ಒಟ್ಟು-ಪರ್ಯಾಯ ಉಪಯುಕ್ತತೆಗಳು ಸಂಯೋಜಕ ಉಪಯುಕ್ತತೆಗಳಿಗಿಂತ ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿವೆ. ಒಟ್ಟು-ಪರ್ಯಾಯ ಏಜೆಂಟ್ಗಳೊಂದಿಗೆ ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಮಾಡಬಹುದು. ಏಕೆಂದರೆ, ಒಟ್ಟು-ಪರ್ಯಾಯ ಏಜೆಂಟ್ಗಳೊಂದಿಗೆ, ವಾಲ್ರಾಸಿಯನ್ ಸಮತೋಲನವು ಯಾವಾಗಲೂ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ, ಮತ್ತು ಇದು ಉಪಯುಕ್ತತೆಗಳ ಮೊತ್ತವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುತ್ತದೆ. ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ವಾಲ್ರಾಸಿಯನ್ ಸಮತೋಲನವನ್ನು ಕಾಣಬಹುದು. ಸಬ್ ಮಾಡ್ಯುಲರ್ ಏಜೆಂಟ್ಗಳು ಸಬ್ ಮಾಡ್ಯುಲರ್ ಏಜೆಂಟ್ ಒಂದು ಯುಟಿಲಿಟಿ ಕಾರ್ಯವನ್ನು ಹೊಂದಿದೆ, ಅದು ಸಬ್ ಮಾಡ್ಯುಲರ್ ಸೆಟ್ ಕಾರ್ಯವಾಗಿದೆ. ಇದರರ್ಥ ಏಜೆಂಟ್ನ ಉಪಯುಕ್ತತೆಯು ಕಡಿಮೆಯಾಗುತ್ತಿರುವ ಅಂಚುಗಳನ್ನು ಹೊಂದಿದೆ. ಸಬ್ ಮಾಡ್ಯುಲರ್ ಉಪಯುಕ್ತತೆಗಳು ಒಟ್ಟು-ಪರ್ಯಾಯ ಉಪಯುಕ್ತತೆಗಳಿಗಿಂತ ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿವೆ. ಸಬ್ ಮಾಡ್ಯುಲರ್ ಏಜೆಂಟ್ಗಳೊಂದಿಗೆ ಗಡಸುತನ ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದೆ. ಇದಲ್ಲದೆ, P = NP ಹೊರತು ಇದನ್ನು (1-1/e) ≈ 0.632 ಗಿಂತ ಉತ್ತಮವಾದ ಅಂಶಕ್ಕೆ ಅಂದಾಜು ಮಾಡಲಾಗುವುದಿಲ್ಲ. ಇದಲ್ಲದೆ, (1-1/ಇ) ಅಂದಾಜುಗಿಂತ ಉತ್ತಮವಾದದ್ದು, ಪಿ = ಎನ್. ಪಿ. ಆಗಿದೆಯೇ ಎಂಬುದನ್ನು ಲೆಕ್ಕಿಸದೆ, ಮೌಲ್ಯ ಒರಾಕಲ್ಗೆ ಘಾತೀಯ ಸಂಖ್ಯೆಯ ಪ್ರಶ್ನೆಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ. ದುರಾಸೆಯ ಕ್ರಮಾವಳಿ ಈ ಕೆಳಗಿನ ಬಹುಪದ-ಸಮಯದ ದುರಾಸೆಯ ಕ್ರಮಾವಳಿಯಿಂದ ಗರಿಷ್ಠ ಕಲ್ಯಾಣವನ್ನು ಅಂದಾಜು ಮಾಡಬಹುದುಃ X1 = X2 =. = Xn = ಖಾಲಿ. ಪ್ರತಿ ವಸ್ತು g ಗೆ (ಅನಿಯಂತ್ರಿತ ಕ್ರಮದಲ್ಲಿ): ಲೆಕ್ಕಾಚಾರ ಮಾಡಿ, ಪ್ರತಿ ಏಜೆನ್ i ಗೆ, g ಗೆ ಅವನ ಕನಿಷ್ಠ ಉಪಯುಕ್ತತೆ, ಇದನ್ನು ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆಃ ui (xi + g)-xi (xi). ಅತಿದೊಡ್ಡ ಕನಿಷ್ಠ ಉಪಯುಕ್ತತೆಯನ್ನು ಹೊಂದಿರುವ ಏಜೆಂಟ್ಗೆ ಐಟಂ ಜಿ ಅನ್ನು ನೀಡಿ. ಲೆಹ್ಮನ್, ಲೆಹ್ಮನ್ ಮತ್ತು ನಿಸಾನ್ ಅವರು ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ 1/2-ಅಂಶದ ಅಂದಾಜನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ (ಈ ಫಲಿತಾಂಶವು ಫಿಶರ್, ನೆಮ್ಹೌಸರ್ ಮತ್ತು ವೋಲ್ಸಿ ಅವರ ಫಲಿತಾಂಶದಿಂದ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಮೇಲೆ ಒಂದೇ ಸಬ್ ಮಾಡ್ಯುಲರ್ ಮೌಲ್ಯಮಾಪನವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವ ಬಗ್ಗೆ ಅನುಸರಿಸುತ್ತದೆ ಎಂದು ಅವರು ಗಮನಿಸುತ್ತಾರೆ). ಪ್ರೂಫ್ ಐಡಿಯಾ ಈ ಕೆಳಗಿನಂತಿದೆ. ಅಲ್ಗಾರಿದಮ್ ಕೆಲವು ಏಜೆಂಟ್ i ಗೆ ಐಟಂ g ಅನ್ನು ನಿಗದಿಪಡಿಸುತ್ತದೆ ಎಂದು ಭಾವಿಸೋಣ. ಇದು ಕಲ್ಯಾಣಕ್ಕೆ ಕೆಲವು ಮೊತ್ತವನ್ನು ಕೊಡುಗೆ ನೀಡುತ್ತದೆ, ಇದು ಆ ಸಮಯದಲ್ಲಿ i ಗೆ g ನ ಕನಿಷ್ಠ ಉಪಯುಕ್ತತೆಯಾಗಿದೆ. ಅತ್ಯುತ್ತಮ ಪರಿಹಾರದಲ್ಲಿ, g ಅನ್ನು ಮತ್ತೊಂದು ಏಜೆಂಟ್ಗೆ ನೀಡಬೇಕು ಎಂದು ಭಾವಿಸೋಣ, ಉದಾಹರಣೆಗೆ k. ನಾವು g ಅನ್ನು i ನಿಂದ k ಗೆ ಸ್ಥಳಾಂತರಿಸಿದರೆ ಕಲ್ಯಾಣವು ಹೇಗೆ ಬದಲಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಪರಿಗಣಿಸಿಃ k ನ ಉಪಯುಕ್ತತೆಯು ಅದರ ಕನಿಷ್ಠ ಉಪಯುಕ್ತತೆಯಿಂದ ಹೆಚ್ಚಾಗುತ್ತದೆ, ಇದು ಗರಿಷ್ಠ v ಅನ್ನು ದುರಾಸೆಯ ಆಯ್ಕೆಯಿಂದ ಹೆಚ್ಚಿಸುತ್ತದೆ. i ನ ಉಳಿದ ಬಂಡಲ್ನ ಕನಿಷ್ಠ ಉಪಯುಕ್ತತೆಯು ಗರಿಷ್ಠ v ಯಿಂದ ಹೆಚ್ಚಾಗುತ್ತದೆ. ಇದು ಸಬ್ ಮಾಡ್ಯುಲಾರಿಟಿಯಿಂದ ಅನುಸರಿಸುತ್ತದೆಃ g ನ ಕನಿಷ್ಠ ಉಪಯುಕ್ತತೆಯು, ಉಳಿದ ಬಂಡಲ್ಗೆ ಸೇರಿಸಿದಾಗ, ಅಲ್ಗಾರಿದಮ್ ಅದನ್ನು ಸಂಸ್ಕರಿಸಿದಾಗ ಅದರ ಕನಿಷ್ಠ ಉಪಯುಕ್ತತೆಗಿಂತ ಹೆಚ್ಚಾಗಿರಬಾರದು. ಆದ್ದರಿಂದ, ಅಲ್ಗಾರಿದಮ್ ಕಲ್ಯಾಣಕ್ಕೆ v ಯ ಪ್ರತಿಯೊಂದು ಕೊಡುಗೆಗೆ, ಅತ್ಯುತ್ತಮ ಕಲ್ಯಾಣಕ್ಕೆ ಸಂಭಾವ್ಯ ಕೊಡುಗೆ ಗರಿಷ್ಠ 2v ಆಗಿರಬಹುದು. ಆದ್ದರಿಂದ, ಅತ್ಯುತ್ತಮ ಕಲ್ಯಾಣವು ಅಲ್ಗಾರಿದಮ್ ಕಲ್ಯಾಣಕ್ಕಿಂತ ಗರಿಷ್ಠ 2 ಪಟ್ಟು ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ಗೆ 2 ರ ಅಂಶವು ಬಿಗಿಯಾಗಿರುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, x, y ಎಂಬ ಎರಡು ಅಂಶಗಳಿವೆ ಎಂದು ಭಾವಿಸೋಣ ಮತ್ತು ಮೌಲ್ಯಮಾಪನಗಳು ಹೀಗಿವೆಃ ಅತ್ಯುತ್ತಮ ಹಂಚಿಕೆಯು ಆಲಿಸ್ಃ {y}, ಜಾರ್ಜ್ಃ {x}, ವೆಲ್ಫೇರ್ 2. ಆದರೆ ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಮೊದಲು x ಅನ್ನು ನಿಗದಿಪಡಿಸಿದರೆ, ಅದು ಅದನ್ನು ಆಲಿಸ್ಗೆ ನಿಯೋಜಿಸಬಹುದು. ನಂತರ, y ಅನ್ನು ಹೇಗೆ ಹಂಚಲಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಲೆಕ್ಕಿಸದೆ, ಕಲ್ಯಾಣವು ಕೇವಲ 1 ಆಗಿದೆ. ಮೌಲ್ಯ ಒರಾಕಲ್ ಅನ್ನು ಬಳಸುವ ಕ್ರಮಾವಳಿಗಳು ಒಂದು ಮೌಲ್ಯ ಒರಾಕಲ್ ಒಂದು ಒರಾಕಲ್ ಆಗಿದ್ದು, ಇದು ವಸ್ತುಗಳ ಗುಂಪನ್ನು ನೀಡಿದರೆ, ಏಜೆಂಟ್ನ ಮೌಲ್ಯವನ್ನು ಈ ಗುಂಪಿಗೆ ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಈ ಮಾದರಿಯಲ್ಲಿಃ ಡೊಬ್ಜಿನ್ಸ್ಕಿ ಮತ್ತು ಶಪಿರಾ ಪಾಲಿಟೈಮ್-ಅಪ್ರೊಕ್ಸಿಮೇಷನ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಮತ್ತು ಏಜೆಂಟ್ಗಳ ಉಪಯುಕ್ತತೆಗಳು ಸೆಟ್-ವ್ಯಾಪ್ತಿ ಕಾರ್ಯಗಳಾಗಿರುವ ವಿಶೇಷ ಪ್ರಕರಣಕ್ಕಾಗಿ (1-1/ಇ) ≈ 0.632-approximation ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ವೊಂಡ್ರಾಕ್ ಮತ್ತು ಕ್ಯಾಲಿನೇಸ್ಕು, ಚೆಕುರಿ, ಪಾಲ್ ಮತ್ತು ವೊಂಡ್ರಾಕ್ ಯಾದೃಚ್ಛಿಕ ಪಾಲಿಟೈಮ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಇದು ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ (1-1/ಇ)-ಹೊಂದಾಣಿಕೆಯನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಅವರ ಅಲ್ಗಾರಿದಮ್ ನಿರಂತರ-ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸುತ್ತದೆ-ಒಂದು ಭಾಗಶಃ ಬಂಡಲ್ ಅನ್ನು (ಪ್ರತಿ ಐಟಂ ಜೆ ನ ಭಾಗ pj ಅನ್ನು ಒಳಗೊಂಡಿರುವ ಬಂಡಲ್) ದುರಾಸೆಯ ದಿಕ್ಕಿನಲ್ಲಿ (ಗ್ರೇಡಿಯಂಟ್ ಡಿಸೆಂಟ್ನಂತೆಯೇ) ವಿಸ್ತರಿಸುವ ಅಲ್ಗಾರಿದಮ್. ಅವರ ಅಲ್ಗಾರಿದಮ್ ಫ್ರ್ಯಾಕ್ಷನಲ್ ಬಂಡಲ್ಗಳ ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಬೇಕಾಗುತ್ತದೆ, ಪ್ರತಿ ಐಟಂ ಜೆ ಅನ್ನು ಸಂಭವನೀಯತೆಯ pj ಯೊಂದಿಗೆ ಸ್ವತಂತ್ರವಾಗಿ ಆಯ್ಕೆ ಮಾಡಿದಾಗ ಪಡೆದ ಬಂಡಲ್ನ ನಿರೀಕ್ಷಿತ ಮೌಲ್ಯ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಫ್ರ್ಯಾಕ್ಷನಲ್ ಬಂಡಲ್ನ ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಮೌಲ್ಯ ಒರಾಕಲ್ಗೆ 2 ಮಿ ಕರೆಗಳು ಬೇಕಾಗಬಹುದು; ಆದಾಗ್ಯೂ, ಯಾದೃಚ್ಛಿಕ ಮಾದರಿಯ ಮೂಲಕ ಇದನ್ನು ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಅಂದಾಜು ಮಾಡಬಹುದು. ಇದು ಯಾದೃಚ್ಛಿಕ ಅಲ್ಗಾರಿದಮ್ಗೆ ಕಾರಣವಾಗುತ್ತದೆ, ಅದು ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ (1-1/ಇ)-ಹೊಂದಾಣಿಕೆಯನ್ನು ಸಾಧಿಸುತ್ತದೆ. ಭಾಗಶಃ ಕಟ್ಟುಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮೌಲ್ಯಮಾಪನ ಮಾಡಬಹುದಾದ ಸಂದರ್ಭಗಳಲ್ಲಿ (ಉದಾ. ಯುಟಿಲಿಟಿ ಫಂಕ್ಷನ್ಗಳು ಸೆಟ್-ಕವರೇಜ್ ಫಂಕ್ಷನ್ಗಳಾಗಿದ್ದಾಗ), ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನಿರ್ಣಾಯಕವಾಗಿಸಬಹುದು. ಸಾಮಾನ್ಯ ಸಬ್ ಮಾಡ್ಯುಲರ್ ಕಾರ್ಯಗಳಿಗಾಗಿ ನಿರ್ಣಾಯಕ ಪಾಲಿಟೈಮ್ (1-1/ಇ)-ಅಪ್ರೊಕ್ಸಿಮೇಷನ್ ಅಲ್ಗಾರಿದಮ್ ಇದೆಯೇ ಎಂದು ಅವರು ಮುಕ್ತ ಸಮಸ್ಯೆ ಎಂದು ಉಲ್ಲೇಖಿಸುತ್ತಾರೆ. ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಯನ್ನು (n ವಿಭಿನ್ನ ಸಬ್ ಮಾಡ್ಯುಲರ್ ಕಾರ್ಯಗಳೊಂದಿಗೆ) ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಕ್ಕೆ ಒಳಪಟ್ಟು ಒಂದೇ ಸಬ್ ಮಾಡ್ಯುಲರ್ ಸೆಟ್ ಕಾರ್ಯವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವ ಸಮಸ್ಯೆಗೆ ಕಡಿಮೆ ಮಾಡಬಹುದುಃ m ಐಟಂಗಳು ಮತ್ತು n ಏಜೆಂಟ್ಗಳೊಂದಿಗೆ ಒಂದು ಉದಾಹರಣೆಯನ್ನು ನೀಡಿದರೆ, m * n (ಏಜೆಂಟ್, ಐಟಂ) ಜೋಡಿಗಳೊಂದಿಗೆ ಒಂದು ಉದಾಹರಣೆಯನ್ನು ನಿರ್ಮಿಸಿ, ಅಲ್ಲಿ ಪ್ರತಿ ಜೋಡಿಯು ಏಜೆಂಟ್ಗೆ ಒಂದು ವಸ್ತುವಿನ ನಿಯೋಜನೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಪ್ರತಿ ಜೋಡಿಗಳ ಗುಂಪಿಗೆ, ಅನುಗುಣವಾದ ಹಂಚಿಕೆಯ ಒಟ್ಟು ಕಲ್ಯಾಣವನ್ನು ನಿಯೋಜಿಸುವ ಒಂದೇ ಕಾರ್ಯವನ್ನು ರಚಿಸಿ. ಎಲ್ಲಾ ಉಪಯುಕ್ತತೆಗಳು ಸಬ್ ಮಾಡ್ಯುಲರ್ ಆಗಿದ್ದರೆ, ಈ ಕಲ್ಯಾಣ ಕಾರ್ಯವು ಸಬ್ ಮಾಡ್ಯುಲರ್ ಆಗಿರುತ್ತದೆ ಎಂದು ತೋರಿಸಬಹುದು. ಈ ಕಾರ್ಯವನ್ನು ಪಾರ್ಟಿಷನ್ ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಕ್ಕೆ ಒಳಪಟ್ಟು ಗರಿಷ್ಠಗೊಳಿಸಬೇಕು, ಪ್ರತಿ ವಸ್ತುವನ್ನು ಗರಿಷ್ಠ ಒಬ್ಬ ಏಜೆಂಟ್ಗೆ ಹಂಚಲಾಗುತ್ತದೆ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಬೇಕು. ಬೇಡಿಕೆ ಒರಾಕಲ್ ಅನ್ನು ಬಳಸುವ ಕ್ರಮಾವಳಿಗಳು ಏಜೆಂಟ್ಗಳ ಉಪಯುಕ್ತತೆಗಳನ್ನು ಪ್ರವೇಶಿಸಲು ಮತ್ತೊಂದು ಮಾರ್ಗವೆಂದರೆ ಬೇಡಿಕೆ ಒರಾಕಲ್ ಅನ್ನು ಬಳಸುವುದು (ಬೆಲೆ-ವಾಹಕವನ್ನು ನೀಡಿದ ಒರಾಕಲ್, ಏಜೆಂಟ್ನ ಅತ್ಯಂತ ಅಪೇಕ್ಷಿತ ಬಂಡಲ್ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ). ಈ ಮಾದರಿಯಲ್ಲಿಃ ಡೋಬ್ಜಿನ್ಸ್ಕಿ ಮತ್ತು ಶಪಿರಾ ಪಾಲಿಟೈಮ್ (1-1/ಇ)-ಅಪ್ರೊಕ್ಸಿಮೇಷನ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಕೆಲವು ಸಣ್ಣ ಧನಾತ್ಮಕ ε ಗೆ ಫೀಜ್ ಮತ್ತು ವೊಂಡ್ರಾಕ್ ಇದನ್ನು (1-1/e + ε) ಗೆ ಸುಧಾರಿಸುತ್ತಾರೆ (ಇದು ಮೇಲಿನ ಗಡಸುತನದ ಫಲಿತಾಂಶವನ್ನು ವಿರೋಧಿಸುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ಗಡಸುತನದ ಫಲಿತಾಂಶವು ಮೌಲ್ಯದ ಒರಾಕಲ್ ಅನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತದೆ; ಗಡಸುತನದ ಉದಾಹರಣೆಗಳಲ್ಲಿ, ಬೇಡಿಕೆಯ ಒರಾಕಲ್ಗೆ ಸ್ವತಃ ಘಾತೀಯವಾಗಿ ಅನೇಕ ಪ್ರಶ್ನೆಗಳು ಬೇಕಾಗುತ್ತವೆ). ಏಜೆಂಟ್ಗಳ ಉಪಯುಕ್ತತೆಗಳು ಸಬ್ಅಡಿಟಿವ್ ಸೆಟ್ ಫಂಕ್ಷನ್ಗಳಾಗಿದ್ದಾಗ (ಸಬ್ ಮಾಡ್ಯುಲರ್ಗಿಂತ ಹೆಚ್ಚು ಸಾಮಾನ್ಯ), ಒಂದು ಅಂದಾಜುಗೆ ಘಾತೀಯ ಸಂಖ್ಯೆಯ ಮೌಲ್ಯದ ಪ್ರಶ್ನೆಗಳು ಬೇಕಾಗುತ್ತವೆ. ಈ ಸಮಸ್ಯೆಗೆ ಎಲ್ಪಿ ಸಡಿಲಿಕೆಗೆ ಯಾವುದೇ ಭಾಗಶಃ ಪರಿಹಾರವನ್ನು ಕನಿಷ್ಠ ಭಾಗಶಃ ಪರಿಹಾರದ ಮೌಲ್ಯದ ಅರ್ಧದಷ್ಟು ಕಲ್ಯಾಣದೊಂದಿಗೆ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಪರಿಹಾರಕ್ಕೆ ಪೂರ್ಣಗೊಳಿಸುವ ಮಾರ್ಗವನ್ನು ಫೀಜ್ ಒದಗಿಸುತ್ತದೆ. ಇದು ಸಾಮಾನ್ಯ ಸಬ್ಅಡಿಟಿವ್ ಏಜೆಂಟ್ಗಳಿಗೆ 1/2-ಪ್ರಾಕ್ಸಿಮೇಷನ್ ನೀಡುತ್ತದೆ, ಮತ್ತು ಭಾಗಶಃ-ಸಬ್ಅಡಿಟಿವ್ ಮೌಲ್ಯಮಾಪನಗಳ ವಿಶೇಷ ಪ್ರಕರಣಕ್ಕೆ (1-1/ಇ)-ಪ್ರಾಕ್ಸಿಮೇಷನ್ ನೀಡುತ್ತದೆ. ಏಜೆಂಟ್ಗಳ ಉಪಯುಕ್ತತೆಗಳು ಸೂಪರ್ಅಡಿಟಿವ್ ಸೆಟ್ ಫಂಕ್ಷನ್ಗಳಾಗಿದ್ದಾಗ (ಸೂಪರ್ ಮಾಡ್ಯುಲರ್ಗಿಂತ ಹೆಚ್ಚು ಸಾಮಾನ್ಯ), ಅಂದಾಜು ಮಾಡಲು ಸೂಪರ್-ಬಹುಪದೀಯ ಸಂಖ್ಯೆಯ ಮೌಲ್ಯದ ಪ್ರಶ್ನೆಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ. ಏಕಮನಸ್ಸಿನ ಏಜೆಂಟ್ ಒಬ್ಬ ಏಕಮನಸ್ಸಿನ ಏಜೆಂಟ್ ಒಂದು ನಿರ್ದಿಷ್ಟ ವಸ್ತುಗಳ ಗುಂಪನ್ನು ಮಾತ್ರ ಬಯಸುತ್ತಾನೆ. ಪ್ರತಿ ಏಕಮನಸ್ಸಿನ ಏಜೆಂಟ್ಗೆ, ಡಿಮಾಂಡೆಡ್ ಸೆಟ್ ಡಿ ಮತ್ತು ಮೌಲ್ಯ ವಿಐ> 0 ಇರುತ್ತದೆ. ಅಂದರೆ, ಅವರ ಬಂಡಲ್ ತಮ್ಮ ಬೇಡಿಕೆಯ ಸೆಟ್ ಅನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಏಜೆಂಟ್ ಸ್ಥಿರ ಧನಾತ್ಮಕ ಉಪಯುಕ್ತತೆಯನ್ನು ಪಡೆಯುತ್ತಾನೆ. ಏಕಮನಸ್ಸಿನ ಏಜೆಂಟ್ಗಳೊಂದಿಗೆ ಕಲ್ಯಾಣವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವುದು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಸಮಸ್ಯೆಯು ಸೆಟ್ ಪ್ಯಾಕಿಂಗ್ಗೆ ಸಮನಾಗಿರುತ್ತದೆ, ಇದನ್ನು ಎನ್ಪಿ ಹಾರ್ಡ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇದಲ್ಲದೆ, ಇದನ್ನು ಯಾವುದೇ ಸ್ಥಿರ ಅಂಶದೊಳಗೆ ಅಂದಾಜು ಮಾಡಲಾಗುವುದಿಲ್ಲ (ಸಬ್ ಮಾಡ್ಯುಲರ್ ಏಜೆಂಟ್ಗಳಿಗೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ). ಅತ್ಯಂತ ಪ್ರಸಿದ್ಧವಾದ ಅಲ್ಗಾರಿದಮ್ ಇದನ್ನು ಒಂದು ಅಂಶದೊಳಗೆ ಅಂದಾಜು ಮಾಡುತ್ತದೆ. ಏಜೆಂಟ್ಗಳು ಅನಿಯಂತ್ರಿತ ಮೊನೊಟೋನ್ ಉಪಯುಕ್ತತೆ ಕಾರ್ಯಗಳನ್ನು (ಪೂರಕ ವಸ್ತುಗಳನ್ನು ಒಳಗೊಂಡಂತೆ) ಹೊಂದಿರುವಾಗ, ಯಾವುದೇ ಅಂಶದೊಳಗೆ ಕಲ್ಯಾಣ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯನ್ನು ಅಂದಾಜು ಮಾಡುವುದು ಕಷ್ಟ. ಆದಾಗ್ಯೂ, ರಾಜ್ಯ ಬಾಹ್ಯಾಕಾಶ ಹುಡುಕಾಟವನ್ನು ಆಧರಿಸಿದ ಕ್ರಮಾವಳಿಗಳಿವೆ, ಅದು ಆಚರಣೆಯಲ್ಲಿ ಉತ್ತಮವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಯುಟಿಲಿಟಿ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆ ಸಮಸ್ಯೆಯ ಉಲ್ಲೇಖಗಳು ಆಪ್ಟಿಮೈಸೇಶನ್ ಕ್ರಮಾವಳಿಗಳು ಮತ್ತು ವಿಧಾನಗಳನ್ನು ಸಹ ನೋಡಿ.