Minimal Regret Walras Equilibria for Combinatorial Markets

We consider combinatorial multi-item markets and propose the notion of a ∆-regret Walras equilibrium, consisting of an allocation and item prices such that prices clear the market, the allocation is capacity-feasible, and the players’ strategies lead to a total regret of at most ∆. Regret is the sum of the players’ utility gaps relative to … Read more

Branch-and-Cut for Computing Approximate Equilibria of Mixed-Integer Generalized Nash Games

Generalized Nash equilibrium problems with mixed-integer variables constitute an important class of games in which each player solves a mixed-integer optimization problem, where both the objective and the feasible set is parameterized by the rivals’ strategies. However, such games are known for failing to admit exact equilibria and also the assumption of all players being … Read more

A guided tour through the zoo of paired optimization problems

Many mathematical models base on the coupling of two or more optimization problems. This paper surveys possibilities to couple two optimization problems and discusses how solutions of the different models are interrelated with each other. The considered pairs stem from the fields of standard and generalized Nash equilibrium problems, optimistic and pessimistic bilevel problems, saddle … Read more

Inspection Games with Incomplete Information and Heterogeneous Resources

We study a two-player zero-sum inspection game with incomplete information, where an inspector deploys resources to maximize the expected damage value of detected illegal items hidden by an adversary across capacitated locations. Inspection and illegal resources differ in their detection capabilities and damage values. Both players face uncertainty regarding each other’s available resources, modeled via … Read more

Collection points placement in urban delivery: A game-theoretic analysis of public and competitive strategies

Collection point networks are rapidly expanding as delivery companies and public authorities promote their implementation to consolidate deliveries and reduce urban congestion. However, rather than catering to public interest by maximizing accessibility, the placement of collection points remains primarily driven by competition among delivery companies, which seek to maximize their market share. This paper thus … Read more

Cooperative vs Noncooperative Scenarios in multi-objective Potential games: the multi-portfolio context

We focus on multi-agent, multi-objective problems, particularly on those where the objectives admit a potential structure. We show that the solution to the potential multi-objective problem is always a noncooperative optimum for the multi-agent setting. Furthermore, we identify a class of problems for which every noncooperative solution can be computed via the potential problem. We … Read more

Random-Restart Best-Response Dynamics for Large-Scale Integer Programming Games and Their Applications

This paper presents scalable algorithms for computing pure Nash equilibria (PNEs) in large-scale integer programming games (IPGs), where existing exact methods typically handle only small numbers of players. Motivated by a county-level aquatic invasive species (AIS) prevention problem with 84 decision makers, we develop and analyze random-restart best-response dynamics (RR-BRD), a randomized search framework for … Read more

On Local Search in Bilevel Mixed-Integer Linear Programming

Two-level hierarchical decision-making problems, where a leader’s choice influences a follower’s action, arise across key business and public-sector domains, from market design and pricing to defense. These problems are typically modeled as bilevel programs and are known to be notoriously hard to solve at scale. In single-level combinatorial optimization, especially for challenging instances, local search … Read more

Asymptotically Fair and Truthful Allocation of Public Goods

We study the fair and truthful allocation of m divisible public items among n agents, each with distinct preferences for the items. To aggregate agents’ preferences fairly, we focus on finding a core solution. For divisible items, a core solution always exists and can be calculated by maximizing the Nash welfare objective. However, such a … Read more

Integer-splittable Bin Packing Games

We study weighted, capacitated cost-sharing games on parallel-link networks, also known as bin packing games. We focus on an integer-splittable variant in which items of varying sizes can be divided into integer units and assigned to bins with heterogeneous capacities and costs. Although this setting has practical relevance, it remains largely unexplored in the context … Read more