Counterfactual regret minimization (CFR), and the newest variant CFR+, have been a central component in several recent milestones in solving imperfect-information extensive-form games. Bowling et al. used CFR+ to near-optimally solve heads-up limit Texas hold’em. CFR variants, along with other scalability techniques, have been succesfully used to create AIs that beat professional poker players at the larger game of heads-up no-limit Texas hold’em.

As a generic term, correlated equilibrium denotes a family of solution concepts whereby a mediator that can recommend behavior, but not enforce it, complements the interaction of rational agents. Before the game starts, the mediator--also called a correlation device--samples a tuple of normal-form plans (one for each player) from a publicly known correlated distribution. The mediator then proceeds to privately ask each player whether they would like to commit to playing according to the plan that was sampled for them. Being part of an equilibrium, the correlated distribution must be such that no player can benefit from not following the recommendations, assuming all other players follow. Coarse correlated equilibrium differs from correlated equilibrium in that players must decide whether or not to commit to playing according to the recommendations of the mediator before observing such recommendations.

Extensive-form games are a classical model of strategic interaction of rational agents, with a rich variety of important applications. Nash Equilibria (NEs), despite being the most celebrated solution concept in game theory, can be unsatisfactory if used to plan a strategy when playing against imperfectly-rational players in extensive-form games. This poses a problem, e.g., when designing an artificial intelligence bot playing against humans, as NEs may be unable to capitalize on opponents' mistakes in branches of the game tree that are not reached along the equilibrium path. Extensive-form perfect equilibria (EFPEs) are refinements of NEs. They benefit form the same strong theoretical guarantees of NEs, yet exhibit a better behavior that can often make a big difference in practice. In 2017, we proved that finding EFPEs in two-player games has—in theory—the same cost (in terms of computational complexity) as finding any unrefined Nash equilibrium, solving a long-standing theoretical problem and showing that EFPEs can have concrete potential. In follow-up work, we further reduced the gap between theory and practice by providing approximation methods and well-engineered exact methods for computing EFPEs. Unfortunately, the practical applicability of EPFEs today still lags behind theory. I propose to continue investigating theoretical and practical solutions that can push a wider adoption of EFPEs, hopefully to the point where there will be no reason not to prefer them over NEs.

In recent years, computational studies on imperfect-information games have largely focused on two-player zero- sum games. In this specific setting, AI techniques have achieved remarkable results, such as defeating top human specialist professionals in heads-up no-limit Texas hold’em poker. Fewer results are known for settings with more than two players. Yet, many strategic interactions provide players with incentives to team up. In some cases, players may have a similar goal and may be willing to coordinate and share their final reward. Consider, as an illustration, the case of a poker game with three or more players, where all but one of them collude against an identified target player and will share the winnings after the game. In other settings, players might be forced to cooperate by the nature of the interaction itself. This is the case, for instance, in the card-playing phase of Bridge, where a team of two players, called the “defenders”, plays against a third player, the “declarer”. Situations of a team ganging up on a player are, of course, ubiquitous in many non-recreational applications as well, such as war where the colluders do not have time or means of communicating during battle, collusion in bidding, where communication during the auction is illegal, coordinated swindling in public, and so on.

Internet advertising constitutes a large market, that in the 2016 fiscal year totaled $72.5 billion worth of revenue in the US alone. Therefore, studying and reducing economic inefficiency in this market has the potential of significantly increasing revenues and social welfare at the same time. I propose applying algorithmic game theory, mechanism design and optimization techniques to achieve this goal. In the past, I have focused on studying and suggesting good mechanisms in the context of sponsored search auctions, i.e., ad auctions in which advertisers bid to have their ads displayed in some slot alongside search results. In the future, I am interested in exploring more expressive models, including ad selling subject to contextual graphs and optimization in the presence of multiple slates. I am also interested in related practically-relevant advertising scenarios, such as mobile advertising. Finally, I'm extremely interested in budgeted ad auctions, where agents subject to budget constraints repeatedly bid for having their ads shown to users.

A kidney exchange is a centrally-administered barter market where patients swap their willing yet incompatible donors. Modern kidney exchanges use 2-cycles, 3-cycles, and chains initiated by non-directed donors (altruists who are willing to give a kidney to anyone) as the means for swapping. We propose significant generalizations to kidney exchange. We allow more than one donor to donate in exchange for their desired patient receiving a kidney. We also allow for the possibility of a donor willing to donate if any of a number of patients receive kidneys. Furthermore, we combine these notions and generalize them. The generalization is to exchange among organ clubs, where a club is willing to donate organs outside the club if and only if the club receives organs from outside the club according to given specifications. Forms of organ clubs already exist — under an arrangement where one gets to be in the club as a potential recipient if one is willing to donate one's organs to the club upon death. Our approach can be used as an inter-club exchange mechanism that increases systemwide good (and can also be applied to live donation).