This thesis is a collection of solutions to a number of optimization problems pertaining to low-power very large-scale integration (VLSI) design. The most interesting aspect of this thesis is the application of economic game theory in the areas of high-level synthesis, gate sizing, and voltage scaling problems, which is the first such application of game theory in these areas.

Game theory has found applications in other areas of computer engineering, especially in networking. Various papers, by Columbia University professors, in the early 1990s, solved various nonlinear optimization problems arising in network capacity allocation and bandwidth allocation problems using game theoretic formulations, treating multi-objective optimization problems as Nash equilibrium finding problems. Work on various other resource allocation problems in distributed computing systems has also been formulated in game theoretic frameworks. Outside the von Neumann-Morgenstern game theory setting, if one considers two-person logical games, various applications in computational logic and finite model theory relating complexity classes to fragments of logic have been done by theoretical computer scientists and logicians. In the field of process algebra, the verification of finite and infinite state systems, a game between a prover and disprover has been used to couch the problems of verification as winning strategy finding problems. In the area of cryptological protocols, prover-disprover models have been used to bring out the inherent competitive nature of the problems being solved.

Economic game theory--made popular in the field of economics, policy decision, and so on by von Neumann and Morgenstern, and later made more generally interesting by Nash, Selten, and others--is quite different from logical games, in the sense that there are real values, real functions, and hence notions of optimization, real analysis, topology, and mathematical programming involved.

In my view, game theory does not necessarily reduce the complexity of problems, nor does it provide new heuristics that could not be otherwise found. What game theory does is bring out the underlying nature of the problems. For example, in behavioral synthesis, if one is trying to use existing cells from a cell library, and alternatives exist in the library, and hence the algorithm needs to decide between multiple competing cells, any of which can be used to implement certain functions, one is confronted with choices and trade-offs. The inherent nature of the problem is that of competition among multiple possible choices, with trade-offs associated with each choice combination. Seeing this makes the formulation of the problem and creating heuristics more intuitive. There lies the innovation and contribution of this thesis.

Certain parts of the thesis could be better written or explained, and more intuition behind bringing in specific game theoretic models for specific problems could be described. But, in general, this is a fairly well-written thesis, and for anyone who is interested in applying economic game theory to understanding a certain problem domain, this thesis can serve as an illustrative example.