Author name cluster

Ratip Emin Berker

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Computational Social Choice: Research & Development

Dorothea Baumeister
Ratip Emin Berker
Niclas Boehmer
Sylvain Bouveret
Andreas Darmann
Piotr Faliszewski
Martin Lackner
Jérôme Lang

Computational social choice (COMSOC) studies principled ways to aggregate conflicting individual preferences into collective decisions. In this paper, we call for an increased effort towards Computational Social Choice: Research & Development (COMSOC-R&D), a problem-driven research agenda that explicitly aims to design, implement, and test collective decision-making systems in the real world. We articulate the defining features of COMSOC-R&D, argue for its value, and discuss various roadblocks and possible solutions.

PDF

AAAI Conference 2026 Conference Paper

On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting

Ratip Emin Berker
Emanuel Tewolde
Vincent Conitzer
Mingyu Guo
Marijn Heule
Lirong Xia

Core stability is a natural and well-studied notion for group fairness in multi-winner voting, where the task is to select a committee from a pool of candidates. We study the setting where voters either approve or disapprove of each candidate; here, it remains a major open problem whether a core-stable committee always exists. In this work, we develop an approach based on mixed-integer linear programming for deciding whether and when core-stable committees are guaranteed to exist. In contrast to SAT-based approaches popular in computational social choice, our method can produce proofs for a specific number of candidates independent of the number of voters. In addition to these computational gains, our program lends itself to a novel duality-based reformulation of the core stability problem, from which we obtain new existence results in special cases. Further, we use our framework to reveal previously unknown relationships between core stability and other desirable properties, such as notions of priceability.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Beyond Symmetry in Repeated Games with Restarts

Henry Fleischmann
Kiriaki Fragkia
Ratip Emin Berker

Infinitely repeated games support equilibrium concepts beyond those present in one-shot games (e. g. , cooperation in the prisoner's dilemma). Nonetheless, repeated games fail to capture our real-world intuition for settings with many anonymous agents interacting in pairs. Repeated games with restarts, introduced by Berker and Conitzer, address this concern by giving players the option to restart the game with someone new whenever their partner deviates from an agreed-upon sequence of actions. In their work, they studied symmetric games with symmetric strategies. We significantly extend these results, introducing and analyzing more general notions of equilibria in asymmetric games with restarts. We characterize which goal strategies players can be incentivized to play in equilibrium, and we consider the computational problem of finding such sequences of actions with minimal cost for the agents. We show that this problem is NP-hard in general. However, when the goal sequence maximizes social welfare, we give a pseudo-polynomial time algorithm.

PDF Details DOI

ICML Conference 2025 Conference Paper

Expected Variational Inequalities

Brian Hu Zhang
Ioannis Anagnostides
Emanuel Tewolde
Ratip Emin Berker
Gabriele Farina
Vincent Conitzer
Tuomas Sandholm

Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation—which we refer to as expected variational inequalities (EVIs) —where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.

Details

AAAI Conference 2025 Conference Paper

The Value of Recall in Extensive-Form Games

Ratip Emin Berker
Emanuel Tewolde
Ioannis Anagnostides
Tuomas Sandholm
Vincent Conitzer

Imperfect-recall games—in which players may forget previously acquired information—have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR can be unbounded in general, we parameterize it in terms of various game properties, namely the structure of chance nodes and the degree of absentmindedness (the number of successive times a player enters the same information set). Further, we identify several pathologies that arise with VoR, and show how to circumvent them. We also study the complexity of computing VoR, and how to optimally apportion partial recall. Finally, we connect VoR to other previously studied concepts in game theory, including the price of anarchy. We use that connection in conjunction with the celebrated smoothness framework to characterize VoR in a broad class of games.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Computing Optimal Equilibria in Repeated Games with Restarts

Ratip Emin Berker
Vincent Conitzer

Infinitely repeated games can support cooperative outcomes that are not equilibria in the one-shot game. The idea is to make sure that any gains from deviating will be offset by retaliation in future rounds. However, this model of cooperation fails in anonymous settings with many strategic agents that interact in pairs. Here, a player can defect and then avoid penalization by immediately switching partners. In this paper, we focus on a specific set of equilibria that avoids this pitfall. In them, agents follow a designated sequence of actions, and restart if their opponent ever deviates. We show that the socially-optimal sequence of actions consists of an infinitely repeating goal value, preceded by a hazing period. We introduce an equivalence relation on sequences and prove that the computational problem of finding a representative from the optimal equivalence class is (weakly) NP-hard. Nevertheless, we present a pseudo-polynomial time dynamic program for this problem, as well as an integer linear program, and show they are efficient in practice. Lastly, we introduce a fully polynomial-time approximation scheme that outputs a hazing sequence with arbitrarily small approximation ratio.

PDF Details DOI