English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The search problem of computing a \textit{leader-follower equilibrium} hasbeen widely investigated in the scientific literature in, almost exclusively,the single-follower setting. Although the \textit{optimistic} and \textit{pessimistic} versions of the problem are solved with differentmethodologies, both cases allow for efficient, polynomial-time algorithms basedon linear programming. The situation is different with multiple followers,where results are only sporadic and depend strictly on the nature of thefollowers' game. In this paper, we investigate the setting of a normal-formgame with a single leader and multiple followers who, after observing theleader's commitment, play a Nash equilibrium. The corresponding search problem,both in the optimistic and pessimistic versions, is known to be not inPoly-$\textsf{APX}$ unless $\textsf{P}=\textsf{NP}$ and exact algorithms areknown only for the optimistic case. We focus on the case where the followersplay in pure strategies under the assumption of pessimism. After casting thissearch problem as a \italic{pessimistic bilevel programming problem}, we showthat, with two followers, the problem is $\textsf{NP}$-hard and, with three ormore followers, it is not in Poly-$\textsf{APX}$ unless$\textsf{P}=\textsf{NP}$. We propose a single-level mathematical programmingreformulation which calls for the maximisation of a nonconcave quadraticfunction over an unbounded nonconvex feasible region defined by linear andquadratic constraints. Since, due to admitting a supremum but not a maximum,only a restricted version of this formulation can be solved to optimality withstate-of-the-art methods, we propose an exact \textit{ad hoc} algorithm, whichwe also embed within a branch-and-bound scheme, capable of computing thesupremum of the problem.

Computing a Pessimistic Leader-Follower Equilibrium with Multiple Followers: the Mixed-Pure Case