TY - GEN
T1 - Saddle-point solution of the fingerprinting capacity game under the marking assumption
AU - Huang, Yen Wei
AU - Moulin, Pierre
PY - 2009
Y1 - 2009
N2 - We study a fingerprinting game in which the collusion channel is unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maxmin games with mutual information as the payoff function. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zerosum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is k and the fingerprint alphabet is binary, we derive equations that can numerically solve the capacity game for arbitrary k. We also provide tight upper and lower bounds on the capacity. Finally, we discuss the asymptotic behavior of the fingerprinting game for large k and practical implementation issues.
AB - We study a fingerprinting game in which the collusion channel is unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maxmin games with mutual information as the payoff function. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zerosum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is k and the fingerprint alphabet is binary, we derive equations that can numerically solve the capacity game for arbitrary k. We also provide tight upper and lower bounds on the capacity. Finally, we discuss the asymptotic behavior of the fingerprinting game for large k and practical implementation issues.
UR - http://www.scopus.com/inward/record.url?scp=70449470526&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70449470526&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2009.5205882
DO - 10.1109/ISIT.2009.5205882
M3 - Conference contribution
AN - SCOPUS:70449470526
SN - 9781424443130
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2256
EP - 2260
BT - 2009 IEEE International Symposium on Information Theory, ISIT 2009
T2 - 2009 IEEE International Symposium on Information Theory, ISIT 2009
Y2 - 28 June 2009 through 3 July 2009
ER -