{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/14023"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/14023","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"Computing Winning Strategies for Poset Games","abstract":"<p>The problem of computing winning strategies in games has yielded many important results with applications in fields such as computer science, economics, and mathematics. For example, \"Online\" games, where the input is received on the fly are used to model process scheduling and paging algorithms. The concept of Nash Equilibrium has implications in economic theory, and Ehrenfeuct-Frass games are used to check whether two structures are isomorphic.</p> <p>In this thesis we are concerned with Partially-Ordered Set (Poset) games. We present two new methods for proving that computing winning strategies for the game of Chomp is in PSPACE. \\Ne also present the idea of \"Game Completeness\", and give an overview of efforts to translate any poset game into an equivalent configuration of Chomp. Finally, we show how Skelley's bounded arithmetic theory W<sup>1</sup><sub>1</sub> can be applied to Chomp, and the consequences of expressing the existence of a winning strategy for the first player in Chomp in simpler arithmetic theories. In short, the contributions of this thesis are as follows:</p> <p>1. A new method for showing poset games in PSPACE, via a polynomial-time (logarithmic-space) reduction to the game of Geography.</p> <p>2. Attempts at a reduction from Geography to poset games, and implications to whether poset games are PSPACE-complete.</p> <p>3. A bounded-arithmetic formulation of the existence of a winning strategy for the first player in Chomp.</p> <p>4. A definition of the concept of Game Completeness, and a translation from treelike poset games to a modified version of Chomp.</p>","abstract_html":"&lt;p&gt;The problem of computing winning strategies in games has yielded many important results with applications in fields such as computer science, economics, and mathematics. For example, &quot;Online&quot; games, where the input is received on the fly are used to model process scheduling and paging algorithms. The concept of Nash Equilibrium has implications in economic theory, and Ehrenfeuct-Frass games are used to check whether two structures are isomorphic.&lt;/p&gt; &lt;p&gt;In this thesis we are concerned with Partially-Ordered Set (Poset) games. We present two new methods for proving that computing winning strategies for the game of Chomp is in PSPACE. \\Ne also present the idea of &quot;Game Completeness&quot;, and give an overview of efforts to translate any poset game into an equivalent configuration of Chomp. Finally, we show how Skelley&#x27;s bounded arithmetic theory W&lt;sup&gt;1&lt;/sup&gt;&lt;sub&gt;1&lt;/sub&gt; can be applied to Chomp, and the consequences of expressing the existence of a winning strategy for the first player in Chomp in simpler arithmetic theories. In short, the contributions of this thesis are as follows:&lt;/p&gt; &lt;p&gt;1. A new method for showing poset games in PSPACE, via a polynomial-time (logarithmic-space) reduction to the game of Geography.&lt;/p&gt; &lt;p&gt;2. Attempts at a reduction from Geography to poset games, and implications to whether poset games are PSPACE-complete.&lt;/p&gt; &lt;p&gt;3. A bounded-arithmetic formulation of the existence of a winning strategy for the first player in Chomp.&lt;/p&gt; &lt;p&gt;4. A definition of the concept of Game Completeness, and a translation from treelike poset games to a modified version of Chomp.&lt;/p&gt;","abstract_has_math":false,"creators":["Wilson, Craig"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computing and Software","school":null,"contributors":[],"advisors":["Soltys, Michael"],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008-03-31","date_published":"2008-03-31","updated_at":"2026-11-18T19:32:40Z","subjects":["Computing and Software"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/12561"],"render_values":[{"text":"https://doi.org/10.71548/12561","href":"https://doi.org/10.71548/12561","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/8853","9934","5352488"],"render_values":[{"text":"opendissertations/8853","href":null,"code":true},{"text":"9934","href":null,"code":true},{"text":"5352488","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/14023","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/14023","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F14023","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Soltys, Michael"]},{"key":"dc:contributor.department","label":"Department","values":["Computing and Software"]},{"key":"dc:creator","label":"Author","values":["Wilson, Craig"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-06-18T17:06:03Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-06-18T17:06:03Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2014-03-18"]},{"key":"dc:date.issued","label":"Date","values":["2008-03-31"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computing and Software"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/8853","9934","5352488"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/14023","https://doi.org/10.71548/12561"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["<p>The problem of computing winning strategies in games has yielded many important results with applications in fields such as computer science, economics, and mathematics. For example, \"Online\" games, where the input is received on the fly are used to model process scheduling and paging algorithms. The concept of Nash Equilibrium has implications in economic theory, and Ehrenfeuct-Frass games are used to check whether two structures are isomorphic.</p> <p>In this thesis we are concerned with Partially-Ordered Set (Poset) games. We present two new methods for proving that computing winning strategies for the game of Chomp is in PSPACE. \\Ne also present the idea of \"Game Completeness\", and give an overview of efforts to translate any poset game into an equivalent configuration of Chomp. Finally, we show how Skelley's bounded arithmetic theory W<sup>1</sup><sub>1</sub> can be applied to Chomp, and the consequences of expressing the existence of a winning strategy for the first player in Chomp in simpler arithmetic theories. In short, the contributions of this thesis are as follows:</p> <p>1. A new method for showing poset games in PSPACE, via a polynomial-time (logarithmic-space) reduction to the game of Geography.</p> <p>2. Attempts at a reduction from Geography to poset games, and implications to whether poset games are PSPACE-complete.</p> <p>3. A bounded-arithmetic formulation of the existence of a winning strategy for the first player in Chomp.</p> <p>4. A definition of the concept of Game Completeness, and a translation from treelike poset games to a modified version of Chomp.</p>"]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Applied Science (MASc)"]},{"key":"dc:title","label":"Title","values":["Computing Winning Strategies for Poset Games"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Soltys, Michael"],"dc:contributor.department":["Computing and Software"],"dc:creator":["Wilson, Craig"],"dc:date.accessioned":["2014-06-18T17:06:03Z"],"dc:date.available":["2014-06-18T17:06:03Z"],"dc:date.created":["2014-03-18"],"dc:date.issued":["2008-03-31"],"dc:description.abstract":["<p>The problem of computing winning strategies in games has yielded many important results with applications in fields such as computer science, economics, and mathematics. For example, \"Online\" games, where the input is received on the fly are used to model process scheduling and paging algorithms. The concept of Nash Equilibrium has implications in economic theory, and Ehrenfeuct-Frass games are used to check whether two structures are isomorphic.</p> <p>In this thesis we are concerned with Partially-Ordered Set (Poset) games. We present two new methods for proving that computing winning strategies for the game of Chomp is in PSPACE. \\Ne also present the idea of \"Game Completeness\", and give an overview of efforts to translate any poset game into an equivalent configuration of Chomp. Finally, we show how Skelley's bounded arithmetic theory W<sup>1</sup><sub>1</sub> can be applied to Chomp, and the consequences of expressing the existence of a winning strategy for the first player in Chomp in simpler arithmetic theories. In short, the contributions of this thesis are as follows:</p> <p>1. A new method for showing poset games in PSPACE, via a polynomial-time (logarithmic-space) reduction to the game of Geography.</p> <p>2. Attempts at a reduction from Geography to poset games, and implications to whether poset games are PSPACE-complete.</p> <p>3. A bounded-arithmetic formulation of the existence of a winning strategy for the first player in Chomp.</p> <p>4. A definition of the concept of Game Completeness, and a translation from treelike poset games to a modified version of Chomp.</p>"],"dc:description.degree":["Master of Applied Science (MASc)"],"dc:identifier.other":["opendissertations/8853","9934","5352488"],"dc:identifier.uri":["http://hdl.handle.net/11375/14023","https://doi.org/10.71548/12561"],"dc:subject":["Computing and Software"],"dc:title":["Computing Winning Strategies for Poset Games"],"dc:type":["thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:32:40Z"}