Papers

Correlated Equilibrium is a solution concept that is more general than Nash Equilibrium (NE) and can lead to outcomes with better social welfare. However, its natural extension to the sequential setting, the Extensive Form Correlated Equilibrium (EFCE), requires a quadratic amount of space to solve, even in restricted settings without randomness in nature. To alleviate these concerns, we apply subgame resolving, a technique extremely successful in finding NE in zero-sum games to solving general-sum EFCEs. Subgame resolving refines a correlation plan in an online manner: instead of solving for the full game upfront, it only solves for strategies in subgames that are reached in actual play, resulting in significant computational gains. In this paper, we (i) lay out the foundations to quantify the quality of a refined strategy, in terms of the social welfare and exploitability of correlation plans, (ii) show that EFCEs possess a sufficient amount of independence between subgames to perform resolving efficiently, and (iii) provide two algorithms for resolving, one using linear programming and the other based on regret minimization. Both methods guarantee safety, i.e., they will never be counterproductive. Our methods are the first time an online method has been applied to the correlated, general-sum setting.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 12 @ blue 6, poster session 1, poster session 12, oral session 12

We consider the problem of maximizing the Nash social welfare when allocating a set $\calG$ of indivisible goods to a set $\calN$ of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent $i \in \calN$ for every good $j \in \calG$ is $v_{ij} \in \{p,q\}$, for $p,q \in \NN$, $p \le q$. In this work, we design an algorithm to compute an optimal allocation in polynomial time if $p$ divides $q$, i.e., when $p=1$ and $q \in \NN$ after appropriate scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p \ge 3$. In terms of approximation, we present positive and negative results for general $p$ and $q$. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is \classAPX-hard, with a lower bound of $1.000015$ achieved at $p/q = 4/5$.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 12 @ blue 6, poster session 1, poster session 12, oral session 12

We study a multi-leader single-follower congestion game where multiple users (leaders) choose one resource out of a set of resources and, after observing the realized loads, an adversary (single-follower) attacks the resources with maximum loads causing additional costs for the leaders. For the resulting strategic game among the leaders, we show that pure Nash equilibria fail to exist and therefore, we consider approximate equilibria instead. As our first main result, we show that the existence of a K-approximate equilibrium can always be guaranteed, where K (approximately equal to 1.1974) is the unique solution of a cubic polynomial equation. To this end, we give a polynomial time combinatorial algorithm which computes a K-approximate equilibrium. The factor K is tight, meaning that there is an instance that does not admit an A-approximate equilibrium for any A < K. Thus A = K is the smallest possible value of A such that the existence of an A-approximate equilibrium can be guaranteed for any instance of the considered game. Secondly, we focus on approximate equilibria of a given fixed instance. We show how to compute efficiently a best approximate equilibrium, that is, with smallest possible A among all A-approximate equilibria of the given instance.

poster session 1 @ blue 6, poster session 12 @ blue 6, oral session 12 @ blue 6, poster session 1, poster session 12, oral session 12