Open Collections

Computing solution concepts in games with integer decisions

University of British Columbia

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 encode sets of pure equilibria and bilevel op- timal solutions, which are viewed as lattice point sets. This encoding then yields efficient algorithms to count, enumerate and optimize over our sets of interest.

Text

2010-07-15

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/26492

Business Administration

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/