Computing solution concepts in games with integer decisions
department or school: Business, Sauder School of
data provider: DSpace
degree campus: UBCV
creator: Ryan, Christopher Thomas
issued: 2010-07-15T20:22:24Z
issued: 2010
related degree: Doctor of Philosophy - PhD
degree grantor: University of British Columbia
description: Computing solution concepts in games is an important endeavor in the field of algorithmic game theory. This thesis explores two contexts – simultaneous games and sequential games – for computing solution concepts in games where some or all of the decisions of players can be modeled as integer vectors. In the case of simultaneous games, the problem of computing pure strategy in Nash equilibrium (pure NE) is considered in two classes of compactly represented games; that is, games where the set of players, actions or utilities are expressed compactly by an input smaller than the standard normal form representation. The first class considered is integer programming games where actions are sets of integer points and utilities have a special difference of piecewise linear convex structure. The second class considered is symmetric games with general piecewise linear utilities. Both classes can be highly expressive of general normal form games, but can also be highly compact. The main results are polynomial-time algorithms for counting and finding pure NE when certain parameters are fixed and where the input is a description of the piecewise linear utilities. In both cases this can yield improved efficiency over known algorithms. In the case of sequential games, the problem of finding optimal “optimistic solutions” to bilevel integer programs are explored. In particular by using recent results from parametric integer programming, a polynomial-time (in fixed dimension) algorithm is derived. Existence results for optima in a more general setting involving a multilinear lower level objective representing leader-controlled units costs are also stated using a decomposition of the original ii problem into a finite set of simpler subproblems. This decomposition theorem is derived from an algebraic theory of integer programming using Gr ̈obner bases. Another contribution of this work is the use of a theory of encoding lattice points in polytopes as rational generating functions to …
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/26492
note: Computing solution concepts in games with integer decisions by Christopher Thomas Ryan B.A., The University of British Columbia, 2005 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES (Business Adminstration) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) July, 2010 c© Christopher Thomas Ryan 2010 Abstract Computing solution concepts in games is an important endeavor in the field of algorithmic game theory. This thesis explores two contexts – simultaneous games and sequential games – for computing solution concepts in games where some or all of the decisions of players can be modeled as integer vectors. In the case of simultaneous games, the problem of computing pure strategy in Nash equilibrium (pure NE) is considered in two classes of compactly represented games ; that is, games where the set of players, actions or utilities are expressed compactly by an input smaller than the standard normal form representation. The first class considered is integer programming games where actions are sets of integer points and utilities have a special difference of piecewise linear convex structure. The second class considered is symmetric games with general piecewise linear utilities. Both classes can be highly expressive of general normal form games, but can also be highly compact. The main results are polynomial-time algorithms for counting and finding pure NE when certain parameters are fixed and where the input is a description of the piecewise linear utilities. In both cases this can yield improved efficiency over known algorithms. In the case of sequential games, the problem of finding optimal “optimistic solutions” to bilevel integer programs are explored. In particular by using recent results from parametric integer programming, a polynomial-time (in fixed dimension) algorithm is derived. Existence results for optima in a more general setting involving a multilinear lower level objecti…
has type: Thesis/Dissertation
date issued: 2010-11
is shown at: 10.14288/1.0071057
language: eng
degree discipline: Business Administration
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/26492