A Shapley Value Index for Market Basket Analysis: Efficient Computation Using an Harsanyi Dividend Representation

Jayden Fitzsimon, Shrikant Agrawal, Kirti Khade, Evan Shellshear (), Jonathon Allport () and Archie C. Chapman ()
Additional contact information
Jayden Fitzsimon: School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, Queensland, Australia
Shrikant Agrawal: School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, Queensland, Australia
Kirti Khade: School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, Queensland, Australia
Evan Shellshear: ��Biarri, Brisbane, Queensland, Australia
Jonathon Allport: ��Biarri, Brisbane, Queensland, Australia
Archie C. Chapman: School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane, Queensland, Australia

International Game Theory Review (IGTR), 2022, vol. 24, issue 04, 1-29

Abstract: Market basket analysis (MBA) aims to discover purchasing patterns and item associations from customer transaction data. A major drawback of current techniques for MBA is a lack of quantitative metrics to measure the real value associated with basket items. This paper addresses this gap by deriving a practical game-theoretic measure for MBA based on the Shapley value of cooperative games, which we call Shapley value index for MBA (SIMBA). The SIMBA of an item represents the average revenue it earns, including its influence on the revenue earned from sales of other items. A significant challenge when applying Shapley value-inspired approaches in practical domains is the exponential complexity of Shapley value computation. However, for the MBA domain, we show that SIMBA admits a scalable exact computation method that does not require sampling or other approximations. Specifically, a characteristic function for the MBA game is constructed so that the transaction dataset input corresponds to the game’s Harsanyi dividends. The relationship between Harsanyi dividends and the Shapley value is then exploited to efficiently compute SIMBA. This approach scales linearly in the number of transactions, making SIMBA a feasible approach for quantitative MBA. SIMBA can be used to screen conventional MBA techniques, such as association rules, to identify significant rules based on the items’ cross-selling capacity. This combination of existing MBA methods and SIMBA will generate rules based not only on frequency of co-occurrence, but also on the significance of the items. We demonstrate the working of the algorithm by analyzing openly available transaction data from an online retail store. To the best of our knowledge, this is the first time Shapley value is used in this way to solve market basket analyses of a practical size.

Keywords: Market basket analysis; cooperative game theory; Shapley value; operations management; cost benefit analysis; deterministic demand (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198922500153
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:igtrxx:v:24:y:2022:i:04:n:s0219198922500153

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198922500153

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().