|Ph.D Student||Ashlagi Itai|
|Department||Department of Industrial Engineering and Management||Supervisors||Professor Emeritus Dov Monderer|
|Professor Moshe Tennenholtz|
|Full Thesis text|
There has been much interest in recent years in work bridging computer science and game theory. Most of this work is concerned with the analysis of multi-agent systems, where the agents are selfish, and each agent attempts to maximize his own utility or minimize his own cost. Hence, it is natural that work in multi-agent systems adopted the notion of equilibrium as the type of solution concept to be discussed, where at equilibrium each agent is optimizing versus the other agents' strategies. However, when dealing with settings of incomplete information, work in computer science has typically adopted non-Bayesian models, in which no probabilistic information about the environment is given. This is in difference to classical work in game theory and economics, where the Bayesian approach is the dominant one. In this dissertation we study games with incomplete information and without probabilistic assumptions, which are also titled: "Pre-Bayesian Games". Unfortunately, without Bayesian assumptions standard equilibrium (ex post or dominant strategy) rarely exists.
We introduce and study several approaches to addressing this fundamental problem. First, we present the study of non-Bayesian equilibrium concepts, such as safety-level equilibrium, as appropriate solutions for dealing with incomplete information in multi-agent systems. We prove the existence of such equilibria in any game with incomplete information without probabilistic assumptions, and in particular analyze concrete settings, where the related non-Bayesian equilibrium concepts lead to illuminating results. We also introduce the study of mediators for games with incomplete information; although the pre-Bayesian game under discussion does not necessary possess ex post equilibrium the mediated game is generated such that an ex post equilibrium exists in it. We show how mediators can be used in order to implement desired outcomes in position auctions, a central topic in e-commerce. Last but not least, we introduce the study of robust learning equilibrium as another powerful solution concept for repeated games with incomplete information, and proved its existence in an auction setting.