| dc.description.abstract | Game-theoretic analysis is widely used to model outcomes of strategic interactions among multiple self-interested players. An important challenge in studying such interactions is in designing the rules of encounter which lead to socially desirable equilibrium outcomes, such as to achieve high allocative efficiency. In this thesis, my goal is to study situations which lead to efficiency/inefficiency in games and markets, as well as approaches for mitigating the inefficiency.
My first investigation is focused on security scenarios with multiple defenders, where each defender protects multiple targets. In this setting, I theoretically characterize Nash and approximate Nash equilibria, as well as their efficiency. My main finding is that the defend- ers often have the incentive to over-protect the targets, at times significantly. I also consider spear-phishing attacks and traffic control systems when there are multiple defenders, and propose algorithms to compute the equilibrium in the two domains.
Having observed an important example where equilibria can be extremely inefficient, the remainder of my thesis explores the problem of designing the rules of encounter, such as mechanisms and markets, that lead to greater efficiency. First, I consider the problem of partitioning a collection of individuals, endowed with hedonic preferences, into teams (coalitions). I study a complete information non-cooperative sequential team formation game in which players iteratively recommend teams, which are either accepted or rejected by their prospective members. I consider a class of mechanisms which implement the subgame perfect equilibrium of the corresponding team formation game. The outcomes of the mechanisms are not generally Pareto efficient, but a restricted class of the mechanisms is guaranteed to have Pareto efficient outcomes. I experimentally demonstrate that the mechanism has great efficiency and incentive properties. Besides, I also study the problem of teaming up pairs of individuals’ conventionally termed the roommates problem from an automated mechanism design (AMD) perspective. I explicitly and computationally design the mechanisms for the roommates problem to get efficiency.
Finally, I study how a free-trading secondary market can mitigate players’ demand uncertainty in the primary market, and make the outcome more efficient. The problem is motivated by the computational resource (e.g. cloud services) allocation among business units (BUs) inside Alibaba group. When players (BUs) have stochastic demand and stiff penalties if their demand cannot be fulfilled, they have the incentive to over-request resources from the primary market, which makes the outcome very inefficient. As a means to mitigate this issue, I introduce a secondary market that allows players to trade resources after demand uncertainty has been resolved. To analyze the impact of the secondary market on the player resource requesting behavior, I model the setting as a two-stage game, with the first stage identical to the newsvendor model, and the secondary market taking place in the second stage. My key finding is that social welfare is significantly higher in the equilibrium of the game with a secondary market than without. | |
