{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/16836"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/16836","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"On the saddle-point solution and the large-coalition behavior of fingerprinting games","abstract":"We study a fingerprinting game in which the number of colluders and the collusion channel are 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 maximin games with mutual information as their payoff functions. 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 zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is $k$ and the fingerprinting alphabet is binary, we show that the capacity is in $\\Theta(1/k^2)$. Furthermore, we prove rigorously that the asymptotic capacity is $1/(k^2 2 \\ln2)$ and we confirm our earlier conjecture that Tardos' choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotic behavior, numerical solutions to the game for small $k$ are also presented.","abstract_html":"We study a fingerprinting game in which the number of colluders and the collusion channel are 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 maximin games with mutual information as their payoff functions. 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 zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is $k$ and the fingerprinting alphabet is binary, we show that the capacity is in <span class=\"etd-inline-math\">\\Theta(1/k<sup>2</sup>)</span>. Furthermore, we prove rigorously that the asymptotic capacity is <span class=\"etd-inline-math\">1/(k<sup>2</sup> 2 \\ln2)</span> and we confirm our earlier conjecture that Tardos&#x27; choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotic behavior, numerical solutions to the game for small $k$ are also presented.","abstract_has_math":true,"creators":["Huang, Yen-Wei"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Moulin, Pierre"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-08-20T17:59:20Z","date_published":"2010-08-20T17:59:20Z","updated_at":"2026-07-22T22:25:09Z","subjects":["fingerprinting","traitor tracing","capacity","game theory","minimax theorem","Jeffreys' prior","saddle-point problems"],"languages":["en"],"rights":["Copyright 2010 Yen-Wei Huang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/16836","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Moulin, Pierre"]},{"key":"dc:creator","label":"Author","values":["Huang, Yen-Wei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-08-20T17:59:20Z","2010-08"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["fingerprinting","traitor tracing","capacity","game theory","minimax theorem","Jeffreys' prior","saddle-point problems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2010 Yen-Wei Huang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/16836"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We study a fingerprinting game in which the number of colluders and the collusion channel are 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 maximin games with mutual information as their payoff functions. 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 zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is $k$ and the fingerprinting alphabet is binary, we show that the capacity is in $\\Theta(1/k^2)$. Furthermore, we prove rigorously that the asymptotic capacity is $1/(k^2 2 \\ln2)$ and we confirm our earlier conjecture that Tardos' choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotic behavior, numerical solutions to the game for small $k$ are also presented.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-07-09T16:19:36Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Huang_Yen-Wei.pdf: 680249 bytes, checksum: 48d2ca4c5b13ebb3cf2928e7570208ae (MD5)","Made available in DSpace on 2010-08-20T17:59:20Z (GMT). No. of bitstreams: 2 Huang_Yen-Wei.pdf: 680249 bytes, checksum: 48d2ca4c5b13ebb3cf2928e7570208ae (MD5) license.txt: 4058 bytes, checksum: 8266c2887bd0e2a92c5fd8dc5ad64fc3 (MD5)"]},{"key":"dc:title","label":"Title","values":["On the saddle-point solution and the large-coalition behavior of fingerprinting games"]}]}],"canonical_facts":{"dc:contributor":["Moulin, Pierre"],"dc:creator":["Huang, Yen-Wei"],"dc:date":["2010-08-20T17:59:20Z","2010-08"],"dc:description":["We study a fingerprinting game in which the number of colluders and the collusion channel are 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 maximin games with mutual information as their payoff functions. 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 zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is $k$ and the fingerprinting alphabet is binary, we show that the capacity is in $\\Theta(1/k^2)$. Furthermore, we prove rigorously that the asymptotic capacity is $1/(k^2 2 \\ln2)$ and we confirm our earlier conjecture that Tardos' choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotic behavior, numerical solutions to the game for small $k$ are also presented.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2010-07-09T16:19:36Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Huang_Yen-Wei.pdf: 680249 bytes, checksum: 48d2ca4c5b13ebb3cf2928e7570208ae (MD5)","Made available in DSpace on 2010-08-20T17:59:20Z (GMT). No. of bitstreams: 2 Huang_Yen-Wei.pdf: 680249 bytes, checksum: 48d2ca4c5b13ebb3cf2928e7570208ae (MD5) license.txt: 4058 bytes, checksum: 8266c2887bd0e2a92c5fd8dc5ad64fc3 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/16836"],"dc:language":["en"],"dc:rights":["Copyright 2010 Yen-Wei Huang"],"dc:subject":["fingerprinting","traitor tracing","capacity","game theory","minimax theorem","Jeffreys' prior","saddle-point problems"],"dc:title":["On the saddle-point solution and the large-coalition behavior of fingerprinting games"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:09Z"}