{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:52:02Z","timestamp":1760403122189,"version":"build-2065373602"},"reference-count":51,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,1,11]],"date-time":"2022-01-11T00:00:00Z","timestamp":1641859200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This paper studies how to attain fairness in communication for omniscience that models the multi-terminal compress sensing problem and the coded cooperative data exchange problem where a set of users exchange their observations of a discrete multiple random source to attain omniscience\u2014the state that all users recover the entire source. The optimal rate region containing all source coding rate vectors that achieve omniscience with the minimum sum rate is shown to coincide with the core (the solution set) of a coalitional game. Two game-theoretic fairness solutions are studied: the Shapley value and the egalitarian solution. It is shown that the Shapley value assigns each user the source coding rate measured by their remaining information of the multiple source given the common randomness that is shared by all users, while the egalitarian solution simply distributes the rates as evenly as possible in the core. To avoid the exponentially growing complexity of obtaining the Shapley value, a polynomial-time approximation method is proposed which utilizes the fact that the Shapley value is the mean value over all extreme points in the core. In addition, a steepest descent algorithm is proposed that converges in polynomial time on the fractional egalitarian solution in the core, which can be implemented by network coding schemes. Finally, it is shown that the game can be decomposed into subgames so that both the Shapley value and the egalitarian solution can be obtained within each subgame in a distributed manner with reduced complexity.<\/jats:p>","DOI":"10.3390\/e24010109","type":"journal-article","created":{"date-parts":[[2022,1,11]],"date-time":"2022-01-11T14:05:07Z","timestamp":1641909907000},"page":"109","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Attaining Fairness in Communication for Omniscience"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1705-7380","authenticated-orcid":false,"given":"Ni","family":"Ding","sequence":"first","affiliation":[{"name":"School of Computing and Information Systems, The University of Melbourne, Parkville, VIC 3010, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9965-9483","authenticated-orcid":false,"given":"Parastoo","family":"Sadeghi","sequence":"additional","affiliation":[{"name":"School of Engineering and Information Technology, University of New South Wales, Northcott Dr, Campbell, ACT 2612, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Smith","sequence":"additional","affiliation":[{"name":"Data61, CSIRO, Level 5\/13 Garden St, Eveleigh, NSW 2015, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thierry","family":"Rakotoarivelo","sequence":"additional","affiliation":[{"name":"Data61, CSIRO, Level 5\/13 Garden St, Eveleigh, NSW 2015, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"3047","DOI":"10.1109\/TIT.2004.838380","article-title":"Secrecy capacities for multiple terminals","volume":"50","author":"Narayan","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"4071","DOI":"10.1109\/TIT.2013.2251412","article-title":"The Infinite-Message Limit of Two-Terminal Interactive Source Coding","volume":"59","author":"Ma","year":"2013","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1109\/18.915643","article-title":"Coding for computing","volume":"47","author":"Orlitsky","year":"2001","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Zaidi, A. (2015, January 11\u201315). On two terminal interactive source coding for function computation with remote sources. Proceedings of the 2015 IEEE Information Theory Workshop-Fall (ITW), Jeju Island, Korea.","DOI":"10.1109\/ITWF.2015.7360784"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"El Rouayheb, S., Sprintson, A., and Sadeghi, P. (2010, January 6\u20138). On coding for cooperative data exchange. Proceedings of the 2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo), Cairo, Egypt.","DOI":"10.1109\/ITWKSPS.2010.5503135"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Courtade, T., and Wesel, R. (October, January 29). Efficient universal recovery in broadcast networks. Proceedings of the 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2010.5707096"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Courtade, T., Xie, B., and Wesel, R. (November, January 31). Optimal exchange of packets for universal recovery in broadcast networks. Proceedings of the 2010-Milcom 2010 Military Communications Conference, San Jose, CA, USA.","DOI":"10.1109\/MILCOM.2010.5680380"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1919","DOI":"10.1109\/TIT.2017.2761390","article-title":"Determining Optimal Rates for Communication for Omniscience","volume":"64","author":"Ding","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1878","DOI":"10.1109\/TIT.2016.2523980","article-title":"Efficient Algorithms for the Data Exchange Problem","volume":"62","author":"Milosavljevic","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1136","DOI":"10.1109\/TIT.2013.2290993","article-title":"Coded Cooperative Data Exchange in Multihop Networks","volume":"60","author":"Courtade","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","unstructured":"Fujishige, S. (2005). Submodular Functions and Optimization, Elsevier. [2nd ed.]."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Sprintson, A., Sadeghi, P., Booker, G., and El Rouayheb, S. (2010, January 18\u201312). A randomized algorithm and performance bounds for coded cooperative data exchange. Proceedings of the 2010 IEEE International Symposium on Information Theory, Austin, TX, USA.","DOI":"10.1109\/ISIT.2010.5513313"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1109\/18.850663","article-title":"Network information flow","volume":"46","author":"Ahlswede","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"4413","DOI":"10.1109\/TIT.2006.881746","article-title":"A Random Linear Network Coding Approach to Multicast","volume":"52","author":"Ho","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"4728","DOI":"10.1109\/TIT.2021.3076967","article-title":"Improving Computational Efficiency of Communication for Omniscience and Successive Omniscience","volume":"67","author":"Ding","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Milosavljevic, N., Pawar, S., Gastpar, M., and Ramchandran, K. (2012, January 1\u20135). Efficient algorithms for the data exchange problem under fairness constraints. Proceedings of the 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/Allerton.2012.6483260"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Tajbakhsh, S., Sadeghi, P., and Shams, R. (2011, January 25\u201327). A Generalized Model for Cost and Fairness Analysis in Coded Cooperative Data Exchange. Proceedings of the 2011 International Symposium on Networking Coding, Beijing, China.","DOI":"10.1109\/ISNETCOD.2011.5979066"},{"key":"ref_18","unstructured":"Jain, R., Chiu, D.M., and Hawe, W.R. (1984). A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer System, Eastern Research Laboratory, Digital Equipment Corporation."},{"key":"ref_19","first-page":"615","article-title":"A concept of egalitarianism under participation constraints","volume":"57","author":"Dutta","year":"1989","journal-title":"Econom. J. Econom. Soc."},{"key":"ref_20","first-page":"307","article-title":"A value for n-person games","volume":"2","author":"Shapley","year":"1953","journal-title":"Contrib. Theory Games"},{"key":"ref_21","unstructured":"Chan, C. (2008). On tightness of mutual dependence upperbound for secret-key capacity of multiple terminals. arXiv."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1561\/0100000072","article-title":"Multiterminal Secrecy by Public Discussion","volume":"13","author":"Narayan","year":"2016","journal-title":"Found. Trends Commun. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1883","DOI":"10.1109\/JPROC.2015.2458316","article-title":"Multivariate Mutual Information Inspired by Secret-Key Agreement","volume":"103","author":"Chan","year":"2015","journal-title":"Proc. IEEE"},{"key":"ref_24","unstructured":"Cover, T.M., and Thomas, J.A. (2012). Elements of Information Theory, John Wiley & Sons."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Ding, N., Chan, C., Zhou, Q., Kennedy, R.A., and Sadeghi, P. (2016, January 4\u20138). A Faster Algorithm for Asymptotic Communication for Omniscience. Proceedings of the 2016 IEEE Globecom Workshops (GC Wkshps), Washington, DC, USA.","DOI":"10.1109\/GLOCOMW.2016.7848809"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1215\/S0012-7094-44-01150-6","article-title":"Dependence relations in a semi-modular lattice","volume":"11","author":"Dilworth","year":"1944","journal-title":"Duke Math. J."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Narayanan, H. (1997). Submodular Functions and Electrical Networks, Elsevier.","DOI":"10.1016\/S0167-5060(08)70678-2"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01761074","article-title":"The egalitarian solution and reduced game properties in convex games","volume":"19","author":"Dutta","year":"1990","journal-title":"Int. J. Game Theory"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Courtade, T., and Wesel, R. (2011, January 28\u201330). Weighted universal recovery, practical secrecy, and an efficient algorithm for solving both. Proceedings of the 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/Allerton.2011.6120324"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Shoham, Y., and Leyton-Brown, K. (2008). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press.","DOI":"10.1017\/CBO9780511811654"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0022-0531(69)90008-8","article-title":"On market games","volume":"1","author":"Shapley","year":"1969","journal-title":"J. Econ. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF01753431","article-title":"Cores of convex games","volume":"1","author":"Shapley","year":"1971","journal-title":"Int. J. Game Theory"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Edmonds, J. (2003). Submodular functions, matroids, and certain polyhedra. Combinatorial Optimization\u2014Eureka, You Shrink!, Springer.","DOI":"10.1007\/3-540-36478-1_2"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Sharp, A., Wexler, T., and Woods, K. (2012, January 20\u201322). Computing Shapley Value in Supermodular Coalitional Games. Proceedings of the 18th Annual International Conference (COCOON 2012), Sydney, Australia.","DOI":"10.1007\/978-3-642-32241-9_48"},{"key":"ref_35","unstructured":"Conitzer, V., and Sandholm, T. (2004, January 25\u201329). Computing Shapley Values, Manipulating Value Division Schemes, and Checking Core Membership in Multi-issue Domains. Proceedings of the 19th National Conference on Artificial Intelligence, San Jose, CA, USA."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1673","DOI":"10.1016\/j.artint.2008.05.003","article-title":"A Linear Approximation Method for the Shapley Value","volume":"172","author":"Fatima","year":"2008","journal-title":"Artif. Intell."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1007\/s003550200160","article-title":"Monotone-path Dutta-Ray solutions on convex games","volume":"19","author":"Hokari","year":"2002","journal-title":"Soc. Choice Welf."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/s001820300141","article-title":"Population monotonicity and consistency in convex games: Some logical relations","volume":"31","author":"Hokari","year":"2003","journal-title":"Int. J. Game Theory"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s13160-012-0083-z","article-title":"Equivalence of convex minimization problems over base polytopes","volume":"29","author":"Nagano","year":"2012","journal-title":"Jpn. J. Ind. Appl. Math."},{"key":"ref_40","unstructured":"Nagano, K., and Kawahara, Y. (2013). Structured convex optimization under submodular constraints. arXiv."},{"key":"ref_41","first-page":"3","article-title":"A submodular function minimization algorithm based on the minimum-norm base","volume":"7","author":"Fujishige","year":"2011","journal-title":"Pac. J. Optim."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Murota, K. (2003). Discrete Convex Analysis, SIAM.","DOI":"10.1137\/1.9780898718508"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","article-title":"Polynomial algorithms in linear programming","volume":"20","author":"Khachiyan","year":"1980","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"ref_44","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., and Schrijver, A. (2012). Geometric Algorithms and Combinatorial Optimization, Springer."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its consequences in combinatorial optimization","volume":"1","author":"Schrijver","year":"1981","journal-title":"Combinatorica"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","article-title":"Submodular function minimization","volume":"112","author":"Iwata","year":"2007","journal-title":"Math. Program."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","article-title":"A Combinatorial Strongly Polynomial Algorithm for Minimizing Submodular Functions","volume":"48","author":"Iwata","year":"2001","journal-title":"J. ACM"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s10107-007-0189-2","article-title":"A faster strongly polynomial time algorithm for submodular function minimization","volume":"118","author":"Orlin","year":"2009","journal-title":"Math. Program."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0019-9958(78)91063-X","article-title":"Polymatroidal dependence structure of a set of random variables","volume":"39","author":"Fujishige","year":"1978","journal-title":"Inf. Control"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1287\/moor.10.3.367","article-title":"The Partial Order of a Polymatroid Extreme Point","volume":"10","author":"Bixby","year":"1985","journal-title":"Math. Oper. Res."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0024-3795(91)90070-D","article-title":"The principal lattice of partitions of a submodular function","volume":"144","author":"Narayanan","year":"1991","journal-title":"Linear Algebra Appl."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/109\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:14:52Z","timestamp":1760364892000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,11]]},"references-count":51,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["e24010109"],"URL":"https:\/\/doi.org\/10.3390\/e24010109","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,1,11]]}}}