2nd Agate Workshop 

​

1. Ron Holzman

Technion – Israel Institute of Technology, Department of Mathematics

The domain of RSD characterization by efficiency, symmetry, and strategy-proofness

Given a set of n individuals with strict preferences over m indivisible objects, the Random Serial Dictatorship (RSD) mechanism is a method for allocating at most one object to each individual in a way that is efficient, fair, and incentive-compatible. A random order of individuals is first drawn, and each individual, following this order, selects their most preferred available object. The procedure continues until either all objects have been assigned or all individuals have received an object.

RSD is widely recognized for its application in fair allocation problems involving indivisible goods. Despite its extensive use, a comprehensive axiomatic characterization has remained incomplete. For the balanced case n=m=3, Bogomolnaia and Moulin have shown that RSD is uniquely characterized by Ex-Post Efficiency, Equal Treatment of Equals, and Strategy-Proofness. The possibility of extending this characterization to larger markets had been a long-standing open question, which Basteck and Ehlers recently answered in the negative for all markets with n, m >= 5.

This work completes the picture by identifying exactly for which pairs (n, m) these three axioms uniquely characterize the RSD mechanism and for which pairs they admit multiple mechanisms. In the latter cases, we construct explicit alternatives satisfying the axioms and examine whether augmenting the set of axioms could rule out these alternatives.

Joint work with Maor Ben-Zaquen.

 

2. Martin Loebl

Agate Centre, Department of Applied Mathematics, Charles University, Prague

Multicriteria fair allocation

Fair allocation of goods to agents has been extensively studied because of its applications in socio-economic contexts. In a common setting, there are n agents and m items, and each agent has an individual valuation for every subset of items. If these valuations are monotone, an allocation that is envy-free up to one item (EF1) always exists.

However, in many situations, agents may have more than one valuation. For example, agents may be partitioned into pre-aligned groups, each of which receives a common bundle of items. This occurs when a resort distributes attraction packages to client couples, or when a recommendation platform allocates ad slots to satisfy both visibility and marketing goals. In such situations, it is natural to assume that at most one valuation per agent is detailed, while the remaining valuations are of rational inattention: they only declare acceptable outcomes and are therefore binary.

To deal with these and other scenarios, we study a multi-criteria fair allocation framework, generalizing standard fair allocation to settings where agents have several public additive valuations, which are binary when explicitly assumed, and an individual valuation satisfying only mild assumptions, called private.

For integers γ, δ ≥ 0, an allocation is envy-free-up-to-γ-public-and-δ-private-goods (EF-(γ, δ)) if no agent envies another with respect to any public (respectively, her private) valuation after deleting at most γ (respectively, δ) goods from the other agent’s bundle.

Individual binary valuations are represented by the value hypergraph, where each hyperedge represents the items accepted by a particular agent. We introduce the Gap parameter and show that, for strongly monotone private valuations, there exist EF-(γ, 1) allocations where γ is twice the Gap of the value hypergraph. We then focus on multi-criteria fair allocations whose value hypergraph has Gap at most two.

We show that such hypergraphs form a significant family and obtain EF-(4, 1) allocations for this general family. We also identify a subfamily, called binary single-peaked, that generalizes the extensively studied single-peaked preferences on a circle property from computational social choice theory. For binary single-peaked instances, an EF-(2, 1) multi-criteria allocation can be found efficiently.

 

3. Miguel Couceiro

University of Lisbon, Instituto Superior Técnico

When Symptoms Form Coalitions: Shapley Regression for Interpretable Rare Disease Diagnosis

Rare diseases pose a “small data, high complexity” problem: cohorts are tiny and imbalanced, while symptoms rarely act in isolation. Logistic regression learns stably from few patients but assumes each symptom contributes additively. Neural networks and boosted trees can capture interactions, but they overfit small cohorts and remain opaque.

In this talk we will present a game-theoretic extension of logistic regression that we call Shapley regression (SR). The linear predictor is replaced by a k-additive Choquet integral with respect to a cooperative game. In the Shapley basis, the model’s coefficients are the Shapley values and pairwise interaction indices themselves, so synergy and redundancy between symptoms can be read off directly. The model is still a convex logistic regression on an expanded basis, and it trains with standard solvers on a CPU. We will discuss when this expanded basis can be learned from few samples:

• No regularisation: VC-type bounds grow with the number of coalitions.

• ℓ1 regularisation: The dependence on that number becomes logarithmic.

• ℓ2 regularisation: Algorithmic-stability bounds also cap the variability of every interaction index, so the explanations are as stable as the predictions.

We will also discuss outcomes of an empirical study on synthetic data with planted interactions and on eight public datasets, which revealed that (i) 2-additive models match higher-order ones, (ii) ℓ1 selects the relevant interactions, and ℓ2 improves robustness to noise, and (iii) the learned indices recover the planted structure.

Finally, we will show preliminary results of SR applied to Activated PI3Kδ Syndrome (APDS), a rare immunodeficiency. This framework not only confirmed known APDS-associated phenotypes, as reported in Orphanet, but also enabled a systematic analysis of how phenotypes jointly contribute through interactions rather than in isolation. This interaction-focused analysis provides a complementary perspective on symptom co-occurrence patterns not captured by traditional models and has the potential to improve our understanding of disease mechanisms and clinical manifestations.

 

4. Angelo Fanelli

LAMSADE, CNRS, Université Paris-Dauphine

Computing Better Approximate Nash Equilibria in Potential Games

Potential games are a fundamental class of games with applications in algorithmic game theory, multi-agent systems, and distributed optimization. Although pure Nash equilibria are guaranteed to exist, computing them is computationally intractable for many natural subclasses. This has motivated extensive research on efficient algorithms for computing approximate equilibria.

In this talk, we focus on payoff-maximization potential games, for which strong approximation guarantees are known only for restricted subclasses. We investigate the limitations of existing algorithms based on unilateral improvement moves, showing that these approaches may fail to provide any finite approximation guarantee even for simple potential games.

To overcome this limitation, we introduce a general algorithmic framework based on coordinated moves by small groups of players. The approximation guarantee and the number of improvement moves are controlled by two natural game parameters, the stretch and the spread. We also establish explicit bounds for games with bounded interaction degree and show how our framework generalizes previous results for constraint satisfaction games.

 

5. Ole Jann

CERGE-EI, Charles University, Prague

Optimal Discussion Design

If we have a group of people with different information and different preferences, how should they optimally discuss in groups? I will show how game-theoretic models of communication (models of "cheap talk") can turn this into a geometric optimization problem. I will present some results, give some examples of interesting effects, and describe open questions.

 

6. Michel Grabisch

Agate Centre, Department of Applied Mathematics, Charles University, Prague & Université Paris 1 Panthéon-Sorbonne

On cooperative games with a singleton core

By the Bondareva–Shapley theorem, cooperative games with a nonempty core are precisely the balanced games. The cone of balanced games is characterized by inequalities indexed by minimal balanced collections, which are in bijection with its facets. We show that the proportion of facets such that all games in them have a singleton core (i.e., a core reduced to a single point) tends to 1 as the number of players increases. We show that this result extends to faces. As a consequence, under a reasonable homogeneity assumption on the random sampling scheme, we show that the Euclidean projection of a randomly generated non-balanced game onto the cone of balanced games has a singleton core with probability tending to 1. Moreover, a simulation study shows that this convergence is very fast.