Proposals for Laurea theses

Equilibrium computation

Title: algorithms for infinite signaling games

Description: Signaling games constitute a specific class of extensive-form games with imperfect information. Every player receives a signal specifying her type. A very important class of these games is when the space of signal is continuous. The work aims at designing efficient algorithms to find equilibria for these games.

Title: algorithms for multi-objective games

Description: When agents have multiple objectives, a game is said multi-objective. Solving these games means finding the Pareto frontier of the equilibria. The work aims at designing efficient algorithms to find them.

Title: decomposition techniques for linear-complementarity problems in two-player games

Description: Column-generation and cut-generation, as well as oracle-based algorithm, are well known techniques to solve large linear mathematical programming problems. These techniques have not been explored in the case of linear complementarity mathematical programming problems. The work aims at exploring the use of these techniques for solving two-player games in strategic and extensive form.

Title: strong Nash equilibrium computation

Description: A strong Nash equilibrium is a strategy profile form which no coalition of players has incentives to deviate. Thus, the strong Nash equilibrium is more robust than a simple Nash equilibrium, that is robust with respect to only single-player deviation. The work aims at designing algorithms to find strong Nash equilibria.

Title: equilibrium computation in graphical games

Description: Graphical games constitute a recent compact representation of games that plays an important role in the study of the complexity of solving games. The exploitation of the graphical structure of the games can allow one to design efficient algorithms. The work aims at incorporating the graphical structure of the games into the well known algorithms to compute equilibria.

Title: equilibrium computation in Bayesian games

Description: Bayesian games are games in which agents have uncertainty over the parameters (payoffs) of the opponents. A Bayesian game is casted to an extensive-form game by using the Harsanyi’s transformation. Computing a Bayes-Nash equilibrium is hard due to the exponential structure of the game. The work aims at developing efficient algorithms for this class of games.

Title: algorithms for multi leader - multi follower scenarios

Description: Leader-follower games are characterized by one or more leaders that commit to a strategy and one or more followers that act as best response. The literature has developed a number of algorithm to find a leader-follower equilibrium when there is a single leader and a single follower. The work aims at developing efficient algorithms when multiple leaders and multiple followers are present.

(Automated) Mechanism design

Title: mechanism design for bilateral bargaining

Description: The bargaining problem is one of the most common negotiation where a buyer and a seller try to reach an agreement over a contract. Bargaining has been extensively studied as a two-player extensive-form game. While with complete information the solution is easy, when information is uncertain computing a solution is hard. The aim of the work is the design of a multi-step mechanism for bargaining with uncertainty.

Title: revenue sharing in federated online advertising

Description: Online advertising is a prominent application scenario for computer science. Currently, the online advertising market is based on an oligopoly and the entrance of new actors is hard. The federation of small actors can lead to form actors that can entrance the market. A prominent problem concerns the sharing of the revenue within the federation.

Title: dynamic mechanism design with interdependencies

Description: A very interesting situation is when a mechanism is played dynamically and the type of the players change with time. The design of mechanisms for these situations is very challenging. While mechanisms are known for situations without interdependencies, when interdependencies are present no result is known.

Security games

Title: security games for wireless sensor networks

Description: Game theory has recently received a lot of attention to study security situations. A few works have studied security with wireless sensor networks. The work aims at developing game theoretic models and algorithms for security problems.

Title: security games for active cameras

Description: In a security problem, cameras can be used to monitor a number of areas. While it is possible to use a large number of cameras, it is very difficult for a human operator to take all the cameras monitored. In this scenario, game theory can be used to control the camera to show to the human operator.

Title: hiding games with populations of individuals

Description: An interesting security situation is characterized by an individual that wants to hide in some locations where other individuals can appear and a detector that wants to find the individual. This is a two-player general-sum game can be studied according to different perspective.