2016. július 19. írta: Kóczy László

NEXT 2.5

Ehud Kalai Budapesti látogatásához kapcsolódóan 2016 július 20.-án egy kisebb workshop lesz az Intézet szemináriumi termében (1112 Budapest, Budaörsi út 45., VIII. emelet 807.), nevezzük NEXT 2.5-nek. A workshop angol nyelvű, ingyenesen látogatható.

Programme:

1030 László Á. Kóczy: Intro/The recursive core under risk-based behavioural expectations

1100 Péter Biró: TBA

1130 Tamás Solymosi: On computing the per-capita nucleolus in balanced games

1200 Balázs Sziklai: Resource-monotonicity and Population-monotonicity in Cake-cutting

1230 Lunch break

1400 Ehud Kalai: Learning and Stability in Big Uncertain Games (co-authored with Eran Shmaya)

1500 Break

1530 Appointments with Prof. Kalai

Abstracts:

Learning and Stability in Big Uncertain Games
Ehud Kalai and Eran Shmaya

Economists, political scientists, computer scientists and others often study repeated strategic interaction which is imperfectly observed and with uncertainties about fundamentals and player types. Rigorous analysis of such games is difficult, but when the number of players is large, situations referred to as big games in this presentation, game theory offers useful tools for such analysis.

We analyze issues of predictability and stability in big games. What are the implications of predictability and stability (or lack of such) in various environments? In what type of big games may we expect predictability and stability? Can policy measures be used to increase the levels of predictability and stability in big games? Etc.

The recursive core under risk-based behavioural expectations
László Á. Kóczy

In partition function form games the value of a coalition depends on the entire partition. As a result, a deviating coalition can only form expectations regarding its post-deviation payoff as the latter is a function of the induced residual partition. Existing literature approached the problem from the side of conservativism, assuming the worst often completely ignoring the interests of the residual players. We borrow the idea of risk from the finance literature and compare the risk of staying with the original partition with the risk of deviating. Employing this idea to the core leads to a new concept that we call the risk-based core. We introduce this concept and discuss its properties.

On computing the per-capita nucleolus in balanced games
Tamás Solymosi

The nucleolus lexicographically maximizes the nondecreasingly ordered vector of the coalitional satisfactions (the difference between the payoff to and the value of the coalition) over the set of imputations. This satisfaction measure, however, does not take into account neither the size, nor the value (or any other characteristic that maybe important for an application) of the coalitions. Various weighted nucleoli (based on weighted satisfaction measures) were considered by several authors, but mostly from an axiomatization point of view.
We focus on the per-capita nucleolus (defined in the same way as the nucleolus, but based on the per-capita satisfaction) from a computability perspective. We show that if the core of the game is not empty, coalitions which are not anti-essential (which can be weakly minorized by a partition) in the dual game can be ignored in the computation of the per-capita nucleolus. We demonstrate that in specific well-known classes of balanced games (standard tree games, assignment games) this implies a polynomial time computability of the per-capita (and other properly weighted versions of the) nucleolus.

Resource-monotonicity and Population-monotonicity in Cake-cutting

Balázs Sziklai

We study the monotonicity properties of solutions in the classic problem of fair cake-cutting - dividing a heterogeneous resource among agents with different preferences. Resource- and population-monotonicity relate to scenarios where the cake, or the number of participants who divide the cake, changes. It is required that the utility of all participants change in the same direction: either all of them are better-off (if there is more to share) or all are worse-off (if there is less to share).

We formally introduce these concepts to the cake-cutting setting and study several division rules. We prove that the Nash-optimal rule, which maximizes the product of utilities, is Pareto-optimal, envy-free, resource-monotonic and population-monotonic. We derive this result in two ways: once directly, and once by showing that the Nash-optimal rule is equivalent to the rule of competitive-equilibrium-from-equal-incomes. Moreover, we prove that it is the only rule among a natural family of welfare-maximizing rules that is both proportional and resource-monotonic. In contrast, other members of this family, like the utilitarian and leximin rules, are either not proportional or not resource-monotonic.

Kalai előadását az MTA-KRTK, a Játékelméleti kutatócsoport és a Nemzeti Kutatási, Fejlesztési és Innovációs Hivatal K-109354 számú OTKA pályázata támogatta.