Benefits of Cooperation in Multiplayer Coupon Collectors' Games

Introduction

The classical Coupon Collector's Game is a process in which a player randomly receives coupons corresponding to one out of possible labels and continues playing until she collects a coupon for each possible label (see, e.g., Rosén, 1970).

Coupon Collector's Problems (CCPs) deal with the statistical characterization of what happens in a Coupon Collector's Game and, even in their simplest form, are the object of many classical and recent investigations. The reason for this interest is twofold. On one side they offer challenging questions in the field of mathematical statistics (see, e.g., Papanicolaou, Kokolakis, & Boneh, 1998, Adler & Ross, 2001, Adlet, Oren, & Ross, 2003, Myers & Wilf, 2004, Neal, 2008). On the other side they enjoy a plethora of applications mostly derived from general Bayesian capture-recapture method Robert (2001) specialized to the most diverse fields such as: counting of biological species or phenomena (see, e.g. McCready & Schwertman, 2001, and Poon, Davis, & Chao, 2005) IP tracking and Internet characterization (see, e.g., Ma, 2006 and Kundu, Pal, Basu, & Das, 2009), recognition of the author of a textual documents Robert (2001) as well as many other information processing/managing tasks (see, e.g., Flajolet, Gardy, & Thimonier, 1992, Boneh & Hofri, 1997, Bach, 1998, and Deb, Medard, & Choute, 2006).

Despite this large availability of theoretical and practical results, little is present in the Literature about CCPs with more than one player (see Adlet, Oren, and Ross (2003) and Neal (2008) for some early treatment). In particular, what is never addressed is the case in which all players aim at completing their collection while accepting to exchange coupons with other players.

Yet, Cooperative Multiplayer CCPs (CM-CCPs) are promising models for the behaviour and performance of mechanisms for resource harvesting and sharing, but also knowledge dissemination in social infrastructure as well as reliable content distribution in peer-to-peer organizations to name a few.

The general problem is that of using resources in un-known, un-planned and un-supervised environments. Such an environment can be coped with by means of a resource management that hinges on two key steps: resources harvesting and resource negotiation/exchanging. Though resource harvesting can be a trivial, even randomized task. Negotiation and exchanging needs intelligence and cooperation. Intelligence is needed to administer the trade-off between resources acquisition and release, and balance local and global profit, present and perspective gains. Cooperation is needed to release a resource when this can be reasonably expected to favor global performance.

Within that general framework, consider the example of the distribution of DRM-protected multimedia content to a group of subscribers. The complete content is made of individually protected and distinguishable pieces, that can be unlocked by only one (not pre-determined) final user. The provider pushes the pieces (possibly packed in envelopes containing more than one piece) into an anycast routing network that delivers them to subscribers. Due to unknown internal network mechanisms users receive random pieces at random times, retain and unlock what they miss to complete the content, and offer other pieces to other users through a multicast routing. Other subscribers request and possibly obtain offered pieces by unicast routing. Note that the network used by the content provider is not necessarily the same as the one used for content exchange between players, thus leading to a noteworthy increase in service deployment flexibility.