July  2022, 9(3): 267-282. doi: 10.3934/jdg.2022013

Relative entropy and envy-free allocation

1. 

Department of Business Disciplines, McNeese State University, Lake Charles, LA 70607, USA

2. 

Department of Management, University of Louisiana at Lafayette, Lafayette, LA 70503, USA

3. 

Department of Mathematical Sciences, McNeese State University, Lake Charles, LA 70607, USA

* Corresponding author: Lonnie Turpin, Jr

Received  September 2021 Revised  March 2022 Published  July 2022 Early access  June 2022

In this brief work, we study a basic environment consisting of a single receiver taking actions based on information (called signals) from multiple senders. The receiver is a rational Bayesian who uses optimization as a mechanism to convert the signals to actions. The conversions are gambles as the actions must be taken before signal reception. Formal comparisons of differences between the solution sets of both prior and posterior optimization frameworks and their respective probability distributions are given. The difference in probability distributions (denoted by relative entropy) presents a useful tool for modifying the receiver's level of risk. We then construct a simple scenario where the receiver acts as a proxy in a Shapely-Shubik-style game with two agents focusing on different objectives under a common risk level. Acting on their behalf, an envy-free allocation mechanism is presented to simultaneously satisfy each using the asymmetric assignment model when findings show the objectives require identical actions.

Citation: Lonnie Turpin, Jr., Kelli Bruchhaus, Keith Credo, Gerard Ornas, Jr.. Relative entropy and envy-free allocation. Journal of Dynamics and Games, 2022, 9 (3) : 267-282. doi: 10.3934/jdg.2022013
References:
[1]

R. Adler and R. Benbunan-Fich, Juggling on a high wire: multitasking effects on performance, International Journal of Human-Computer Studies, 70 (2012), 156-168. 

[2]

M. Basseville, Distance measures for signal processing and pattern recognition, Signal Processing, 18 (1989), 349-369.  doi: 10.1016/0165-1684(89)90079-0.

[3]

D. P. Bertsekas and D. A. Castanon, A forward/reverse auction algorithm for asymmetric assignment problems, Comput. Optim. Appl., 1 (1992), 277-297.  doi: 10.1007/BF00249638.

[4]

A. Bhattacharyya, On a measure of divergence between two multinomial populations, Sankhyā: The Indian Journal of Statistics, 7 (1946), 401-406. 

[5] K. Borch, The Economics of Uncertainty, Princeton University Press, New Jersey, 1968. 
[6]

S. ChoiS. Cha and C. Tappert, A survey of binary similarity and distance measures, Journal of Systemics, Cybernetics and Informatics, 8 (2010), 43-48. 

[7] T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, New Jersey, 2006. 
[8]

C. DaskalakisI. Diakonikolas and R. A. Servedio, Learning Poisson binomial distributions, Algorithmica, 72 (2015), 316-357.  doi: 10.1007/s00453-015-9971-3.

[9]

R. W. Hamming, Error detecting and error correcting codes, Bell System Tech. J., 29 (1950), 147-160.  doi: 10.1002/j.1538-7305.1950.tb00463.x.

[10]

L. Hansen and T. Sargent, Robust control and model uncertainty, The American Economic Review, 91 (2001), 60-66. 

[11]

D. Hickson, Decision-making at the top of organizations, Annual Review of Sociology, 13 (1987), 165-192. 

[12]

R. Kass and L. Wasserman, The selection of prior distributions by formal rules, Journal of the American Statistical Association, 91 (1996), 1343-1370. 

[13]

M. KearnsY. MansourD. RonR. RubinfeldR. Schapire and L. Sellie, On the learnability of discrete distributions, Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, (1994), 273-282. 

[14]

S. Kosub, A note on the triangle inequality for the Jaccard distance, Pattern Recognition Letters, 120 (2019), 36-38. 

[15]

S. Kullback and R. A. Leibler, On information and sufficiency, Ann. Math. Statistics, 22 (1951), 79-86.  doi: 10.1214/aoms/1177729694.

[16] R. Marris, The Economic Theory of 'Managerial' Capitalism, Palgrave Macmillan, London, 1964. 
[17]

A. Metrick and B. Polak, Fictitious play in $2 \times 2$ games: A geometric proof of convergence, Economic Theory, 4 (1994), 923-933.  doi: 10.1007/BF01213819.

[18] H. Moulin, Cooperative Microeconomics: A Game-Theoretic Introduction, Princeton University Press, New Jersey, 1995. 
[19]

T. NguyenA. Peivandi and R. Vohra, Assignment problems with complementarities, J. Econom. Theory, 165 (2016), 209-241.  doi: 10.1016/j.jet.2016.04.006.

[20]

R. Rosenberg, Profit constrained revenue maximization: Note, American Economic Review, 61 (1971), 208-209. 

[21]

L. S. Shapley and M. Shubik, The assignment game Ⅰ: The core, Internat. J. Game Theory, 1 (1972), 111-130.  doi: 10.1007/BF01753437.

[22]

T. Strzalecki, Axiomatic foundations of multiplier preferences, Econometrica, 79 (2011), 47-73.  doi: 10.3982/ECTA8155.

[23]

F. Topsøe, Some inequalities for information divergence and related measures of discrimination, IEEE Trans. Inform. Theory, 46 (2000), 1602-1609.  doi: 10.1109/18.850703.

[24]

H. Tuy, Monotonic optimization: Problems and solution approaches, SIAM J. Optim., 11 (2000), 464-494.  doi: 10.1137/S1052623499359828.

[25]

G. Yarrow, Managerial utility maximization under uncertainty, Economica, 40 (1973), 155-173. 

show all references

References:
[1]

R. Adler and R. Benbunan-Fich, Juggling on a high wire: multitasking effects on performance, International Journal of Human-Computer Studies, 70 (2012), 156-168. 

[2]

M. Basseville, Distance measures for signal processing and pattern recognition, Signal Processing, 18 (1989), 349-369.  doi: 10.1016/0165-1684(89)90079-0.

[3]

D. P. Bertsekas and D. A. Castanon, A forward/reverse auction algorithm for asymmetric assignment problems, Comput. Optim. Appl., 1 (1992), 277-297.  doi: 10.1007/BF00249638.

[4]

A. Bhattacharyya, On a measure of divergence between two multinomial populations, Sankhyā: The Indian Journal of Statistics, 7 (1946), 401-406. 

[5] K. Borch, The Economics of Uncertainty, Princeton University Press, New Jersey, 1968. 
[6]

S. ChoiS. Cha and C. Tappert, A survey of binary similarity and distance measures, Journal of Systemics, Cybernetics and Informatics, 8 (2010), 43-48. 

[7] T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley & Sons, New Jersey, 2006. 
[8]

C. DaskalakisI. Diakonikolas and R. A. Servedio, Learning Poisson binomial distributions, Algorithmica, 72 (2015), 316-357.  doi: 10.1007/s00453-015-9971-3.

[9]

R. W. Hamming, Error detecting and error correcting codes, Bell System Tech. J., 29 (1950), 147-160.  doi: 10.1002/j.1538-7305.1950.tb00463.x.

[10]

L. Hansen and T. Sargent, Robust control and model uncertainty, The American Economic Review, 91 (2001), 60-66. 

[11]

D. Hickson, Decision-making at the top of organizations, Annual Review of Sociology, 13 (1987), 165-192. 

[12]

R. Kass and L. Wasserman, The selection of prior distributions by formal rules, Journal of the American Statistical Association, 91 (1996), 1343-1370. 

[13]

M. KearnsY. MansourD. RonR. RubinfeldR. Schapire and L. Sellie, On the learnability of discrete distributions, Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, (1994), 273-282. 

[14]

S. Kosub, A note on the triangle inequality for the Jaccard distance, Pattern Recognition Letters, 120 (2019), 36-38. 

[15]

S. Kullback and R. A. Leibler, On information and sufficiency, Ann. Math. Statistics, 22 (1951), 79-86.  doi: 10.1214/aoms/1177729694.

[16] R. Marris, The Economic Theory of 'Managerial' Capitalism, Palgrave Macmillan, London, 1964. 
[17]

A. Metrick and B. Polak, Fictitious play in $2 \times 2$ games: A geometric proof of convergence, Economic Theory, 4 (1994), 923-933.  doi: 10.1007/BF01213819.

[18] H. Moulin, Cooperative Microeconomics: A Game-Theoretic Introduction, Princeton University Press, New Jersey, 1995. 
[19]

T. NguyenA. Peivandi and R. Vohra, Assignment problems with complementarities, J. Econom. Theory, 165 (2016), 209-241.  doi: 10.1016/j.jet.2016.04.006.

[20]

R. Rosenberg, Profit constrained revenue maximization: Note, American Economic Review, 61 (1971), 208-209. 

[21]

L. S. Shapley and M. Shubik, The assignment game Ⅰ: The core, Internat. J. Game Theory, 1 (1972), 111-130.  doi: 10.1007/BF01753437.

[22]

T. Strzalecki, Axiomatic foundations of multiplier preferences, Econometrica, 79 (2011), 47-73.  doi: 10.3982/ECTA8155.

[23]

F. Topsøe, Some inequalities for information divergence and related measures of discrimination, IEEE Trans. Inform. Theory, 46 (2000), 1602-1609.  doi: 10.1109/18.850703.

[24]

H. Tuy, Monotonic optimization: Problems and solution approaches, SIAM J. Optim., 11 (2000), 464-494.  doi: 10.1137/S1052623499359828.

[25]

G. Yarrow, Managerial utility maximization under uncertainty, Economica, 40 (1973), 155-173. 

[1]

Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial and Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211

[2]

Luiza H. F. Andrade, Rui F. Vigelis, Charles C. Cavalcante. A generalized quantum relative entropy. Advances in Mathematics of Communications, 2020, 14 (3) : 413-422. doi: 10.3934/amc.2020063

[3]

Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215

[4]

Bettina Klaus, Frédéric Payot. Paths to stability in the assignment problem. Journal of Dynamics and Games, 2015, 2 (3&4) : 257-287. doi: 10.3934/jdg.2015004

[5]

Shuang Zhao. Resource allocation flowshop scheduling with learning effect and slack due window assignment. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2817-2835. doi: 10.3934/jimo.2020096

[6]

Qinglan Xia, Shaofeng Xu. On the ramified optimal allocation problem. Networks and Heterogeneous Media, 2013, 8 (2) : 591-624. doi: 10.3934/nhm.2013.8.591

[7]

Xiaomin Zhou. Relative entropy dimension of topological dynamical systems. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6631-6642. doi: 10.3934/dcds.2019288

[8]

José Antonio Carrillo, Yingping Peng, Aneta Wróblewska-Kamińska. Relative entropy method for the relaxation limit of hydrodynamic models. Networks and Heterogeneous Media, 2020, 15 (3) : 369-387. doi: 10.3934/nhm.2020023

[9]

Richard Sharp. Distortion and entropy for automorphisms of free groups. Discrete and Continuous Dynamical Systems, 2010, 26 (1) : 347-363. doi: 10.3934/dcds.2010.26.347

[10]

Christopher Garcia. The synchronized multi-assignment orienteering problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022018

[11]

Jean Dolbeault, Giuseppe Toscani. Fast diffusion equations: Matching large time asymptotics by relative entropy methods. Kinetic and Related Models, 2011, 4 (3) : 701-716. doi: 10.3934/krm.2011.4.701

[12]

Denis Serre, Alexis F. Vasseur. The relative entropy method for the stability of intermediate shock waves; the rich case. Discrete and Continuous Dynamical Systems, 2016, 36 (8) : 4569-4577. doi: 10.3934/dcds.2016.36.4569

[13]

Jiahua Zhang, Shu-Cherng Fang, Yifan Xu, Ziteng Wang. A cooperative game with envy. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2049-2066. doi: 10.3934/jimo.2017031

[14]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[15]

Yong Ji, Ercai Chen, Yunping Wang, Cao Zhao. Bowen entropy for fixed-point free flows. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6231-6239. doi: 10.3934/dcds.2019271

[16]

Yujun Ju, Dongkui Ma, Yupan Wang. Topological entropy of free semigroup actions for noncompact sets. Discrete and Continuous Dynamical Systems, 2019, 39 (2) : 995-1017. doi: 10.3934/dcds.2019041

[17]

Ming Chen, Chongchao Huang. A power penalty method for the general traffic assignment problem with elastic demand. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1019-1030. doi: 10.3934/jimo.2014.10.1019

[18]

Chia-Chun Hsu, Hsun-Jung Cho, Shu-Cherng Fang. Solving routing and wavelength assignment problem with maximum edge-disjoint paths. Journal of Industrial and Management Optimization, 2017, 13 (2) : 1065-1084. doi: 10.3934/jimo.2016062

[19]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041

[20]

R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial and Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173

 Impact Factor: 

Metrics

  • PDF downloads (102)
  • HTML views (59)
  • Cited by (0)

[Back to Top]