Félix Quinton

Idir Hamaz

Laurent Houssin

Algorithms for the flexible cyclic jobshop problem

This paper considers the cyclic jobshop problem in a flexible context. The aim is to find the minimum cycle time of a periodic schedule. The flexibility feature comes from the ability of the machines or robots to perform several kinds of tasks. Hence, the scheduling problem does not only concern starting time of tasks but also on which machines the tasks will be performed. We propose an exact method to solve this problem and two heuristics.

I. INTRODUCTION

In automation systems, a robotic cell for instance, actions are mainly cyclic. Once an occurrence of each task is planed and the cycle time is determined, the schedule is completely defined. Each occurrence is then performed periodically. Numerous papers consider the scheduling problem of a robotic cells in a cyclic manner (Crama [4], Yan [START_REF] Yan | An algorithm for optimal cyclic scheduling in a robotic cell with flexible processing times[END_REF], Bożejko [START_REF] Bożejko | Cyclic scheduling of a robotic cell[END_REF]).

In scheduling theory, cyclic jobshop scheduling and flexible jobshop scheduling are long studied NP-hard problems (Hanen [START_REF] Hanen | Study of a NP-hard cyclic scheduling problem: The recurrent jobshop[END_REF], Brucker [START_REF] Brucker | jobshop Problems with Flexible Machines[END_REF], Levner [START_REF] Levner | Complexity of cyclic scheduling problems: A state-of-the-art survey[END_REF]) apart from each other.

However few papers tackle the flexible cyclic scheduling problem despite the capabilities of robots to perform several types of task. Because of the highly combinatorial nature of flexible scheduling problems (Xia [START_REF] Xia | An effective hybrid optimization approach for multi-objective flexible jobshop scheduling problems[END_REF]), research focused on genetic algorithm to solve the flexible cyclic scheduling problem (Jalilvand [START_REF] Jalilvand-Nejad | A mathematical model and genetic algorithm to cyclic flexible job shop scheduling problem[END_REF], Bożejko [START_REF] Bożejko | A fine-grained parallel algorithm for the cyclic flexible job shop problem[END_REF]).

This paper is organized as follows : in Section II. we describe the basic cyclic scheduling problem. Section III. describes the cyclic jobshop scheduling problem in which we introduce the notion of robots and resource constraint. In Section IV. we introduce the flexible cyclic jobshop problem and the notion of flexibility which means that a robot can perform several different tasks, and propose a mathematical model for this problem. In Section V. we propose two heuristic procedures to tackle long solving time for large instances. Finally, we present numerical instances in Section VI.

II. Basic cyclic scheduling problem

The basic cyclic scheduling problem (BCSP) is an extension of the basic scheduling problem where a schedule of elementary tasks i ∈ T = {1, ..., n} is infinitely repeated. For each task i ∈ T , we are given its execution time p i and we denote by t i (k) the starting time of occurrence k of task i ∈ T .

I. Hamaz and L. Houssin are with CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France Univ de Toulouse, UPS, LAAS, F-31400 Toulouse, France laurent.houssin@laas.fr Elementary tasks are connected by precedence constraints. A precedence constraint (i, j, p i , H ij ), where H ij is called the height of the precedence constraint and represents the occurrence shift between tasks i and j, state that :

t j (k + H ij ) ≥ p i + t i (k)
Let us denote t i = t i (0), i ∈ T . In this study, we are interested in periodic schedules, which are such that there exists a cycle time α satisfying t i (k) = αk + t i .

The objective considered in this study is the minimization of the cycle time α which is the time elapsed between two occurrences of the task.

A BCSP can be represented on a graph where the set of edges E represent the precedence constraints and vertices represent elementary tasks. The edges are weighted and the weight of a given edge represent the execution time of the task at its origin and the height of the precedence constraint.

There are two methods to solve the BCSP. The first is based on graph and consist to find the maximum mean cycle in the graph.

The second is to use mathematical programming. The BCSP can be expressed as a linear programming problem as follows. min α

s.t. α ≥ p i , ∀i ∈ T (1a) t j + αH i,j ≥ t i + p i , ∀(i, j) ∈ E (1b) t i ≥ 0, ∀i ∈ T (1c)
Constraints (1a) correspond to non-reentrance constraints which ensure that two occurrences of the same elementary task do not overlap. Constraints (1b) set the precedence constraints.

Example 1: Table I reports the data of a BCSP instance with 7 elementary tasks. The graph representing this example is presented in Fig. 2, where the red dotted edges are ignored. After solving this BCSP, we find an optimal cycle time of 9. The solution for the BCSP instance is given in Fig. 1 in the form of a Gantt diagram : III. Cyclic jobshop scheduling problem In the cyclic jobshop scheduling problem (CJSP), each elementary task i ∈ T is assigned to a robot r i ∈ R = {1, ..., R}, with R < n.

In consequence, the lack of resource induces some disjunction constraints. For a pair of tasks (i, j) ∈ T 2 , i = j such that r i = r j , an occurrence of tasks i and an occurrence of j, cannot be executed at the same time. Denote by D = {(i, j)|R(i) ∩ R(j) = ∅} the set of pair of tasks in disjunction.

More precisely, this disjunction leads to a pair of constraints :

t j (k + K ij ) ≥ t i (k) + p i t i (k + K ji ) ≥ t j (k) + p j
Where K ij (resp. K ji ) is an occurrence shift between task i and j (resp. j and i), and K ij + K ji = 1 as showed by Hanen [START_REF] Hanen | Study of a NP-hard cyclic scheduling problem: The recurrent jobshop[END_REF]. Note that in this problem the variables are α, (t) i∈T , and (K) (i,j)∈D .

A job is composed by elementary tasks and precedence constraints between these tasks.

A feature of the CJSP is the Work In Process (WIP). It corresponds to the maximum number of occurrences of a job processed simultaneously.

The CJSP can be resolved using a Branch-and-Bound procedure (Houssin [START_REF] Levner | Complexity of cyclic scheduling problems: A state-of-the-art survey[END_REF], Hanen [START_REF] Hanen | Study of a NP-hard cyclic scheduling problem: The recurrent jobshop[END_REF]) or using mathematical programming. The CJSP can be represented as a Mixed Interger Non Linear Programming problem (MINLP) as follows :

min α s.t. α ≥ p i , ∀i ∈ T (2a) t j + αH i,j ≥ t i + p i , ∀(i, j) ∈ E (2b) t j + αK(i, j) ≥ t i + p i , ∀(i, j) ∈ D (2c) K(i, j) + K(j, i) = 1, ∀(i, j) ∈ D (2d) K(i, j) ∈ Z, ∀(i, j) ∈ D (2e) t i ≥ 0, ∀i ∈ T (2f)
Constraints (2a) are the non-reentrance constraints and constraints (2b) are the precedence constraints. Constraints (2c) are the disjunction constraints defined above, and constraints (2d) state for the usual CJSP property previously enunciated.

However, non linear programming is very unpractical. Consequently, we want to linearize the model. Hanen [START_REF] Hanen | Study of a NP-hard cyclic scheduling problem: The recurrent jobshop[END_REF] proposes to define the variable τ = 1 α and for all i ∈ T , the variable u i = ti α . Then the CJSP can be written as follows (Hanen [1]):

max τ s.t. τ ≤ 1 p i , ∀i ∈ T (3a) u j + H i,j ≥ u i + τ p i , ∀(i, j) ∈ E (3b) u j + K(i, j) ≥ u i + τ p i , ∀(i, j) ∈ D (3c) K(i, j) + K(j, i) = 1, ∀(i, j) ∈ D (3d) K(i, j) ∈ Z, ∀(i, j) ∈ D (3e) u i ≥ 0, ∀i ∈ T (3f)
Example 2: in Table II, we have updated Example 1 so that it fits the CJSP with 4 robots. The graph in Fig. 2 shows the problem with only the disjunctive constraints for robot M 3 displayed for cleanliness purposes. Solving this CJSP, we find an optimal cycle time α = 13.

M 1 M 3 M 1 M 2 M 4 M 3
The solution for this CJSP is given in Fig. 3 flexible. This means that for each task i ∈ T , we have a set R(i) ⊂ R of robots on which task i can be assigned.

In consequence, the assignment of a task i to a robot r ∈ R(i) is a decision variable. Each assignment of a task i ∈ T to a robot r ∈ R(i) is associated with a given execution time p ir .

Also, because we do not know a priori on which robot each task will be assigned, we do not know the set D of pairs of tasks which are connected by a disjunctive constraint.

Example 3: in Table III, we have updated Example 2 so that it fits the FCJSP. Each task can be assigned to a subset of 3 out of 4 robots. Note that the new possibilities come with a higher execution time.

A. Linear model

In this section, we propose a mixed integer linear programming (MILP) formulation for the FCJSP. Let R(i, j) = R(i) ∩ R(j), ∀i, j ∈ T the robots available both for tasks i and j. Recall that E is the set of precedence constraints and that D is the set of disjunctive constraints.

We also define some decision variables for the assignation of a task i ∈ T to a robot r ∈ R(i) :

∀i = {1, ..., n}, ∀r ∈ R(i), m i,r =
1 if task i is assigned to robot r 0 sinon The MILP for the FCJSP can be formulated as :

max τ s.t. τ ≤ 1 p i,r + (1 -m i,r )P 1 , ∀i ∈ T, ∀r ∈ R(i) (4) u j + H i,j ≥ u i + p i,r (τ -(1 -m i,r )), ∀(i, j) ∈ E, ∀r ∈ R(i) (5)
u j + K i,j ≥ u i + p i,r (τ -(2 -m i,r -m j,r )), ∀(i, j) ∈ E, ∀r ∈ R(i, j) (6)
r∈r(i) m i,r = 1, ∀i ∈ T (7) K(i, j) + K(j, i) = 1, ∀(i, j) ∈ D (8) K(i, j) ∈ Z, ∀(i, j) ∈ D ( 9
)
u i ≥ 0, ∀i ∈ T ( 10
)
m i,r ∈ {0, 1}, ∀i ∈ T ∀r ∈ R(i) (11)
Constraints (4) correspond to non-reentrance constraints. They ensure that two occurrences of the same elementary task do not overlap. The P 1 term allows us to deactivate the constraints for which task i is not affected to robot r. Let us set P 1 = 1 min i∈T ,r∈R(i) pi,r . Constraints (5) set the precedence constraints, i.e. the order in which tasks have to be executed. Those constraints must be activated only if task i is assigned to robot r, because we use the term p i,r . All constraints in [START_REF] Yan | An algorithm for optimal cyclic scheduling in a robotic cell with flexible processing times[END_REF] such that m i,r = 0 are dominated by the constraints in [START_REF] Yan | An algorithm for optimal cyclic scheduling in a robotic cell with flexible processing times[END_REF] such that m i,r = 1 because p i,r (τ -1) < 0 < p i,r τ , and thus are deactivated.

Constraints (6) represents the disjunctive constraints, ensuring that two tasks are not executed at the same time period on the same robot. We want those constraints to be activated only when tasks i and j are assigned to the same robot r. Let r ∈ R(i, j) a robot on which both tasks i and j can be executed, then if task i or task j is not assigned to r, we have τ -(2 -m i,r -m j,r ) < 0, which deactivate the corresponding disjunctive constraint. By the same mechanism as previously, constraints where m i,r = 0 or m j,r = 0 are dominated by those where m i,r = m j,r = 1 and thus are deactivated.

Constraints [START_REF] Fink | A new procedure for the cyclic job shop problem[END_REF] ensure that every task i ∈ T is assigned to a robot r ∈ R(i). Constraints ( 8) are usual constraints for the CJSP, introduced by Hanen [START_REF] Hanen | Study of a NP-hard cyclic scheduling problem: The recurrent jobshop[END_REF].

Example 3.1: We have solved the Example 3. with our MILP. We have obtained a cycle time α = 10. The solution is displayed as Gantt diagram in Fig. 4.

B. Heuristic procedures

The FCJSP is a difficult problem because it is highly combinatorial. The solving time of the MILP presented in V. can become very long for large numerical instances. To tackle this issue, we have developed two heuristic procedures.

1) Reducing the R(i) sets: a first approach is to reduce the flexibility of the problem, i.e. the number of robots in the set R(i), ∀i ∈ T . Define R H (i) ⊂ R(i) the set of robot on which task i ∈ T can be assigned in the heuristic procedure. The set R H (i) can be fixed as the set of R H robots with the lowest execution time for task i, with R H < R. In our numerical experimentation, we have set R H = 2, which allows us to obtain some good feasible solutions in a reasonable solving time without losing flexibility.

Example 3.2: we have solved Example 3 using this approach. We have obtained a cycle time α = 10, with a different task to machine assignment. The solution is displayed in Fig. 5 as a Gantt diagram. 2) Critical circuit heuristic: an other approach is to allow only a fraction of the tasks to be flexible. In other words, we chose a subset I ⊂ T of tasks whose assignment to robot will be a decision variable while other tasks i ∈ T \I are already assigned.

We define I as the set of tasks composing the critical circuit of our FCJSP. The critical circuit in an oriented bi-valuated graph is the circuit minimizing Hc Lc (Hanen [START_REF] Hanen | Study of a NP-hard cyclic scheduling problem: The recurrent jobshop[END_REF]), where L c is the sum of the edge's length of the circuit and H c is the sum of the edge's height of the circuit.

The heuristic procedure consists in iteratively solving the reduced problem where only the tasks composing the critical circuit are flexible until finding twice the same critical circuit. It can be written as follows :

Step 0.

Initialise by solving the CJSP generated by the previous heuristic with R H = 1.

Step 1.

Find the critical circuit using the Howard algorithm [START_REF] Gaubert | Methods and applications of (max,+) linear algebra[END_REF].

Step 2.

Solve the problem allowing only the tasks composing the critical circuit to be flexible.

Step 2.1 Find a critical circuit.

Step 2.2 If the critical circuit has not been explored already, go to 2. 3) Example 3.3: we have solved Example 3 using the critical circuit procedure. Once again, we obtained a cycle time α = 10 with a different task to machine assignment. The solution is displayed in Fig. 6. in the form of a Gantt diagramm. V. Numerical experimentation The following numerical experiments has been conduced on randomly generated instances with 15, 20 and 30 tasks and 5 robots. Also, each tasks can be assigned to 3 to 5 of the robots. We fixed the time limit to 300 seconds for the MILP solving and 60 seconds for the heuristic procedures. The mean times displayed below does not account for the instances whose resolution time exceed the time limit, and the mean gaps does not account for the instances that have been solved before the time limit. Note that the gap is defined as UB-τ i τ i , where UB is the best upper bound found by the solver and τ i is the value of τ in the incumbent solution.

As we can see in Table IV, the MILP is unable to solve instances larger than 20 tasks and 4 assignment possibilities for each task.

Also, we can see through Tables V. to VII. that the "reducing R(i) sets" heuristic procedure proposed in IV.B.1. with R H = 2 is more efficient than the "critical circuit" heuristic procedure proposed in IV.B.2. on every aspect.

On very large instances, we can see in Table VI. that the "reducing R(i) sets" heuristic procedure is more efficient than the MILP.

VI. Conclusion

We have proposed a MILP for the FCJSP and two heuristic procedures that are more efficient for large instances.

Further work could be to improve our heuristic procedures and to consider the possibility of a Bender's or Danzwig-Wolfe decomposition.

Fig. 1 .

 1 Fig. 1. Solution for the CSP example

  in the form of a Gantt diagram : IV. Flexible jobshop cyclic scheduling problem The flexible cyclic jobshop scheduling problem (FCJSP) is a CJSP where the elementary tasks are

Fig. 2 .Fig. 3 .

 23 Fig. 2.Associated graph to the CJSP instance described in example 2

Fig. 4 .

 4 Fig. 4. Solution for the FCJSP example

Fig. 5 .

 5 Fig.5. Solution given by the "reduce R(i)" heuristic for the FCJSP example

Time

Fig. 6 .

 6 Fig. 6. Solution given by the "critical circuit" heuristic for the FCJSP example Time 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

TABLE VII

 VII Mean gap between the heuristic solution and the MILP incumbent when the MILP incumbent > the heuristic solution

	Instance parameters	Reduce R(i)	Critical circuit
		heuristic	heuristic
	15 tasks | 3 robots	4.33%	11.39%
	15 tasks | 4 robots	7.05%	15.70%
	15 tasks | 5 robots	undefined	13.95%
	20 tasks | 3 robots	4.69%	11.36%
	20 tasks | 4 robots	10%	12.61%
	20 tasks | 5 robots	undefined	22.11%
	30 tasks | 3 robots	3.46%	11.11%
	30 tasks | 4 robots	undefined	10.26%
	30 tasks | 5 robots	undefined	32.52%


Brendan John

Pallavi Raiturkar

Olivier Le Meur

Eakta Jain

A Benchmark of Four Methods for Generating 360 • Saliency Maps from Eye Tracking Data

Keywords: Saliency, Visualization, Eye movements in VR, 360 images

Modeling and visualization of user attention in Virtual Reality is important for many applications, such as gaze prediction, robotics, retargeting, video compression, and rendering. Several methods have been proposed to model eye tracking data as saliency maps. We benchmark the performance of four such methods for 360 • images. We provide a comprehensive analysis and implementations of these methods to assist researchers and practitioners. Finally, we make recommendations based on our benchmark analyses and the ease of implementation.

I. INTRODUCTION

With the explosive growth of commercial VR and AR systems, there is increased access to innovative 3D experiences. In particular, 360 • images and videos are being used for entertainment, storytelling, and advertising. Content creators are actively working out techniques and building tools to guide user attention in these new media. A critical enabler for these efforts is measuring and visualizing eye tracking data. Eye trackers built into VR headsets serve as a reliable tool to understand how attention is allocated in 3D environments.

The study of attention and eye movements in 2D content is well established. Saliency maps highlight regions that attract the most visual attention and have applications in predicting gaze [START_REF] Cerf | Predicting human gaze using low-level saliency combined with face detection[END_REF], compression [START_REF] Guo | A novel multiresolution spatiotemporal saliency detection model and its applications in image and video compression[END_REF], and selective rendering [START_REF] Longhurst | A gpu based saliency map for high-fidelity selective rendering[END_REF] to name a few. In 360 • images, the user is surrounded by a photorealistic virtual scene. Because only a fraction of the scene is viewed at once, the allocation of visual attention is different than 2D content. Moreover, due to the spherical nature of 360 • content, novel saliency map generation methods are required.

To generate 2D saliency maps, eye tracking data is processed to identify fixations. Fixations are aggregated in a map that is convolved with a 2D Gaussian kernel. For 2D displays the number of pixels per visual degree is assumed to be the same in horizontal and vertical directions, so an isotropic Gaussian is used. The Kent distribution is an analog to a 2D Gaussian on the surface of a 3D sphere [START_REF] Kent | The fisher-bingham distribution on the sphere[END_REF]. 360 • images encode spherical data, and the natural extension is to process them using such a distribution. However, computing a Kent based saliency map is slow due to a spatially varying kernel. Fortunately, several approximate alternatives exist.

In this paper, we benchmark four alternative methods for generating 360 • saliency maps. We report accuracy and runtime for each algorithm, and present pseudocode to implement them. Based on these analyses and ease of implementation, we identify the most favorable approach.

II. BACKGROUND

Saliency maps aggregate data from multiple observers into a representative map of human attention. Typically, saliency maps are generated by summing fixations from each observer into a discrete fixation map,

F i (x) = M k=1 δ(x -x i k ), (1)
where M is the number of fixations by the i th observer, x represents two dimensional pixel coordinates in the image, and x i k represents the coordinates of the k th fixation [START_REF] Meur | Methods for comparing scanpaths and saliency maps: strengths and weaknesses[END_REF]. δ is the Dirac function, which evaluates to 1 at δ(1), and 0 everywhere else. All maps from N observers are averaged to produce a unique representative map,

F (x) = 1 N N i=1 F i (x) (2)
This fixation map is convolved with a 2D Gaussian kernel to produce a continuous map highlighting salient regions instead of individual pixels. The Gaussian kernel accounts for noise in measurement, such as calibration error, as well as falloff in visual acuity outside the foveal region. The standard deviation parameter, σ, is typically set between 1 • and 5 • visual angle due to the size of the foveal region and eye tracker error [START_REF] Duchowski | Eye tracking methodology[END_REF]. For 360 • content, saliency researchers need to translate existing 2D methodologies to immersive 3D environments. 2D metrics are well understood [START_REF] Meur | Methods for comparing scanpaths and saliency maps: strengths and weaknesses[END_REF], but they must be reconsidered for 360 • saliency maps and scanpaths. As saliency prediction models adapt to 360 • [7]- [START_REF] Gutiérrez | Toolbox and dataset for the development of saliency and scanpath models for omnidirectional/360 still images[END_REF], there is a need for a standardized method to evaluate them against ground truth. Several eyetracking datasets are available for 360 • images and video, with their own method for generating saliency maps [START_REF] Sitzmann | Saliency in vr: How do people explore virtual environments?[END_REF]- [START_REF] David | A dataset of head and eye movements for 360 videos[END_REF].

III. METHODS TO GENERATE SALIENCY MAPS IN 360 •

Four methods of generating 360 • saliency maps have been proposed recently: applying a Gaussian kernel to fixations on the viewport and projecting the resulting maps onto the surface of the viewing sphere [START_REF] Rai | A dataset of head and eye movements for 360 degree images[END_REF], applying a Gaussian kernel to the face of a cubemap [START_REF] Maugey | Saliency-based navigation in omnidirectional image[END_REF], modifying the Gaussian kernel based on row [START_REF] Upenik | A simple method to obtain visual attention data in head mounted virtual reality[END_REF], and simply applying an isotropic Gaussian kernel on the equirectangular image [START_REF] Sitzmann | Saliency in vr: How do people explore virtual environments?[END_REF]. These methods have been proposed in separate publications, with algorithmic details scattered between supplementary materials, or as part of datasets. Here, we collect these alternatives in one place, clarify algorithmic details, and benchmark their performance using a Kent distribution based method as ground truth. We briefly summarize and present pseudocode for the Kent based method, and the four approximate methods. For each method the output is a saliency map, S, that is then normalized such that all of the values sum to one. A square kernel is used for ease of implementation, with kernel size set to 12 times the number of pixels per degree rounded up to an odd number. This size is larger than usual to ensure that all non-zero values are included. Helper functions are defined in the Appendix.

Kent Distribution: The Kent distribution is an isotropic bivariate normal distribution defined on the surface of a three dimensional unit sphere [START_REF] Kent | The fisher-bingham distribution on the sphere[END_REF]. While the complete 5 parameter distribution is anisotropic, we use the simplified isotropic form. The probability density function f is defined as

f ( x, κ, γ) = κe κ γ• x 4πsinh(κ) , (3)
where x ∈ R 3 is an input vector representing a point on the sphere. The parameter κ > 0 represents the concentration of the probability density function. The parameter γ ∈ R 3 is the mean direction of the distribution, around which points are normally distributed. Pixels in the equirectangular image x, y map to azimuth and elevation angles θ, φ. These angles are converted from spherical coordinates to a 3D vector in cartesian coordinates x. We compute the kernel weights by inputting the pixel neighborhood N (x, y, kernel size) as vectors into f , where γ is a vector that represents the current pixel. Due to unequal sampling of the sphere in equirectangular images, the kernel must be recomputed for each row. Input to this method is a fixation map F , and parameter κ. S ← zeros(num rows, num cols)

3:
for r = 1 to num rows do Parallelizable loop 4:

φ ← π|r/num rows -0.5|

5: θ ← 0 θ is constant 6: c = num cols/2 c is constant 7: γ ← sph2cart(θ, φ , 1) 8:
K ← f (N (c, r, kernel size), κ, γ)

N ormalize K Kernel weights sum to 1 10:

S row ← F K Optimized to only output row r 11:

S(r) = S row
In a MATLAB implementation we found that using a κ value of 707 or higher produces a result too large to fit in a 64 bit floating point number. Typical values of κ will be larger than this for modeling 1 • or less of visual angle in saliency map generation. HPF 1 for high precision floating point numbers is needed, which increases the amount of time needed to perform the operations invoked by f . The following methods either approximate the Kent distribution (modified Gaussian), or operate outside the spherical domain.

Isotropic Gaussian Method: For 2D map generation a spatially invariant kernel is used, filtering the image in seconds. 1 https://www.mathworks.com/matlabcentral/fileexchange/36534-hpf-a-bigdecimal-class While quick, this computation does not account for distortions in the equirectangular image. Input to this method are a fixation map F , and standard deviation σ. G σ ← 1d gaussian(σ, kernel size) [START_REF] Upenik | A simple method to obtain visual attention data in head mounted virtual reality[END_REF] introduce a modified Gaussian kernel that accounts for equirectangular distortions near the poles. A scale factor of 1 cosφ is computed for each elevation angle φ, to stretch an isotropic Gaussian kernel horizontally. A bivariate Gaussian kernel is computed for each row as the matrix product

3: K ← G σ • G T σ 4: S ← F K indicates 2D convolution Modified Gaussian Method: Upenik & Ebrahimi
K = G σy • G T σx , (4)
where G σy is a column vector representing a 1D Gaussian with standard deviation σ y in pixels, and G T σx is a row vector representing a 1D Gaussian where σ x = σy cosφ . This method applies a different filter at each row, requiring many 2D convolutions. This method has a similar runtime and structure to the Kent distribution, but is much easier to implement. φ ← π|r/num rows -0.5|

5:

G σy ← 1d gaussian(σ, kernel size)

G σx ← 1d gaussian(σ/cosφ, kernel size)

7: K ← G σy • G T σx 8:
S row ← F K Optimized to only output row r 9:

S(r) = S row

Cubemap Method: Cubemaps reduce image distortions by projecting the spherical image onto cube faces representing perspective views from within the sphere. This format allows each face to be filtered with an isotropic Gaussian, but introduces discontinuities at the borders. To reduce this effect, cubes at two orientations are aligned and combined in equirectangular format to generate one representative map for the image. Weights W 1 and W 2 are applied with an elementwise multiplication to reduce the contribution of pixels near the edges of each face, as described by [START_REF] Maugey | Saliency-based navigation in omnidirectional image[END_REF]. Transforming high resolution images between formats is time consuming, and the method does not completely remove border discontinuities.

F rot ← rotatesphereXY Z(F, pi 4 , 0, pi 4 ) 3:
G σ ← 1d gaussian(σ, kernel size)

4: K ← G σ • G T σ 5: Cube 1 ← equirect2cube(F ) K 6: Cube 2 ← equirect2cube(F rot ) K 7:
S 1 ← cube2equirect(Cube 1 )

8:

S 2 ← cube2equirect(Cube 2 )

9:

S ← W 1 . * S 1 + W 2 . * S 2 Viewport Method: 360 • content is realized as a projection of the spherical image onto a viewport determined by the observer's head orientation. A Gaussian kernel can then be applied directly within the viewport, and projected back onto the equirectangular image [START_REF] Rai | A dataset of head and eye movements for 360 degree images[END_REF]. These values are summed across the equirectangular saliency map for each fixation. This method's runtime scales with the number of fixations. It can produce projection errors due to interpolation. The process of projecting each viewport onto the image generally has the longest runtime with high resolution images, and requires the HMD's horizontal and vertical field of view, f ov x and f ov y . Input for this method is a list of fixations in HMD screen space, head rotation, and the horizontal and vertical standard deviations of the 2D Gaussian in pixels, σ x and σ y . G σy ← 1d gaussian(σ y , kernel size)

9:

G σx ← 1d gaussian(σ x , kernel size)

10: K ← G σy • G σx 11: S viewport ← viewport K 12:
S equirect ← vp2sphere(S viewport , R, f ov x , f ov y )

13:

S += S equirect

IV. BENCHMARK METHODOLOGY & RESULTS

We benchmark the isotropic Gaussian, Viewport, Cubemap, and modified Gaussian saliency map methods to evaluate accuracy and performance. The Kent based method serves as ground truth, taking hours to compute for each image at full resolution. The modified Gaussian method also has a long runtime as it performs a convolution at each row. Instead, we first reduce the resolution of the image to 5% it's original size using MATLAB's imresize, then apply the modified Gaussian method. The result is then returned to the original resolution using bicubic interpolation. 5% scale was selected to generate a map in several seconds, with less than 2% deviation from the full resolution output. While saliency map generation is typically an offline process, our goal is to select a method that is efficient to ease analysis for researchers, and for real time applications such as 360 • video streaming to many clients.

We use publicly available data and metrics for evaluation [START_REF] Rai | A dataset of head and eye movements for 360 degree images[END_REF]. The dataset contains 40 images, each with fixations from at least 40 different observers classified using velocity thresholding. The image resolution ranged from 5376x2688 to 18332x9166. For our benchmark the saliency maps for each method are compared with the Kent based maps, and results are averaged across all images. Head orientation data was not provided with the dataset, meaning we had to use the provided maps instead of generating our own for the Viewport method. The parameter σ=3.34 • was used for each method to match the dataset. The parameter κ=430 was found to match σ=3.34 • by comparing the mean and standard deviation of points generated on a sphere using the Kent distribution, and points from a projected 2D Gaussian. We have not yet derived a closed form relation between the two parameters. Results were The serialized code was used for the benchmark.

The saliency map metrics Correlation Coefficient (CC), KL Divergence (KLD), and RMSE were used to measure similarity between each of these maps and the Kent method map for all images [START_REF] Meur | Methods for comparing scanpaths and saliency maps: strengths and weaknesses[END_REF]. CC ranges from 0 to 1, with high values indicating better performance. KLD represents divergence between two probability distributions, meaning lower values are considered a good score. Similarly, a low RMSE indicates a better approximation. Table I shows the computed metrics averaged across each image in the dataset. The modified Gaussian at 5% scale has the highest CC value, lowest KLD, and lowest RMSE indicating it had the highest similarity to the Kent saliency maps. In addition to high accuracy, the modified Gaussian at 5% is also efficient with an average runtime of 5.16 seconds.

The Viewport method maps provided with the dataset have no runtime, as they were read from file. We found that these maps scored lowest of all evaluated methods. An explanation for this could be that an isotropic Gaussian was used within the viewport when generating saliency maps. The viewport size is based on the Oculus DK2 screen and field of view, which is 1920x1080 and 94 • x105 • , meaning the number of pixels per degree is different in horizontal and vertical directions. To avoid this limitation, we use pixels per degree in the horizontal and vertical directions and apply an anisotropic Gaussian.

To evaluate the effect of an anisotropic Gaussian kernel, we implemented the Viewport method to process our own data. We conducted an IRB approved experiment on 22 participants with a similar protocol to [START_REF] Rai | A dataset of head and eye movements for 360 degree images[END_REF], using the same VR eye tracking equipment and images. We computed Kent and Viewport saliency maps for each image and evaluate them in the same manner, shown in Table I. We produced more accurate results, raising CC scores from 0.41 to 0.93, and reducing RMSE from 0.15 to 0.04 across the same images. This effect can be observed visually, as Figure 1 compares heat maps from both Viewport and Kent method outputs.

V. DISCUSSION

We found that a subsampled version of the modified Gaussian method is sufficient for generating accurate 360 • saliency maps efficiently. While a sub-sampled Kent method could also be used, the parameter κ is not as intuitive as σ, which directly comes from pixels per visual degree. The method is also simpler to implement without using projections or high precision floating point libraries that impact performance.

The Viewport method has the longest average runtime of 1031 seconds, and unlike other methods depends on the number of fixations. Using the viewport requires the HMD field of view, which varies based on depth [START_REF] Kreylos | Optical properties of current vr hmds[END_REF]. Methods that operate in the equirectangular or spherical domain do not depend on the HMD field of view, and thus are preferred.

VI. CONCLUSION

Saliency maps for 2D, such as saliency maps on images and webpages, are well established both in terms of methods to generate saliency maps from eye tracking data, and to generate computational saliency maps from image features. Generalizing this body of knowledge to VR is an active area of research. We have focused on 360 • images, a special case in VR where the entire scene is at the same depth. We argue that while the Kent distribution provides a natural generalization of the 2D Gaussian kernel in this context, it is not a very practical method for 360 • saliency map generation. Based on our benchmark results and ease of implementation, we recommend use of the modified Gaussian at 5% scale. Our analysis is based on CPU performance, and in the future can be implemented on highly parallelizable systems like a GPU. Both the Kent and modified Gaussian methods are amenable to parallel implementations. We provide pseudocode and implementations2 of these methods to facilitate further research in evaluating saliency models.

1 :

 1 procedure KENT(F ,κ) 2:

1 :

 1 procedure ISOTROPIC(F,σ) 2:

1 : 3 :

 13 procedure MODIFIEDGAUSSIAN(F ,σ) 2: S ← zeros(num rows, num cols) for r = 1 to num rows do Parallelizable loop 4:

1 :

 1 procedure CUBEMAP(F ,σ) 2:

1 : 3 :

 13 procedure VIEWPORT(FIXATIONS,ROTATIONS,σ x ,σ y ) 2:S ← zeros(num rows, num cols)for i = 1 to M f ixations do 4:viewport ← zeros(viewport size)

Fig. 1 :

 1 Fig. 1: Cropped region of Kent and Viewport saliency heat maps provided with [12] and computed from our own data collection. Red indicates large saliency values, and blue indicates low values. Our implementation of the Viewport method better overlaps with the Kent output as it does not highlight uncolored regions (Top row, middle/bottom of motorcycle).

TABLE I :

 I Computed metrics for each method compared with ground truth Kent saliency maps. We implemented the Viewport method for use with our own dataset.

	generated on a PC with an 8 core AMD FX-8350 processor,
	and MATLAB R2017a. MATLAB routines for these methods
	have been made publicly available, including a parallelized
	implementation of the Kent and Modified Gaussian method.

https://jainlab.cise.ufl.edu/publications.html#AIVR2018 APPENDIX

1d gaussian(σ, kernel size): Returns a column vector of length kernel size from a Gaussian distribution with µ = 0 and standard deviation σ.

sph2cart(θ, φ, r): Returns a 3D vector x in cartesian coordinates from input spherical coordinates.

N (x, y, kernel size): Transforms a set of pixels centered at x, y into cartesian vectors. Each pixel is mapped to azimuth and elevation angles θ, φ then converted to cartesian.

rotatesphereXY Z(Equirect, X rot , Y rot , Z rot ): The input sphere is rotated by the input angles and returned.

equirect2cube(Equirect): The input equirectangular image is converted to a cubemap and returned.

cube2equirect(C): The input cubemap is converted to a equirectangular image and returned.

vp2sphere(V P, R, f ov x , f ov y ): The viewport image V P is projected onto an equirectangular image of a specific size based on head orientation R, and HMD field of view.


Stéphane Le Roux

Discrete Non Neterminism and Nash Equilibria for Strategy-Based Games

Keywords: Abstract strategic games, Nash equilibrium, discrete non-determinism, discrete equilibrium, constructive, fixed-point, multi-strategic games

Several notions of game enjoy a Nash-like notion of equilibrium without guarantee of existence. There are different ways of weakening a definition of Nash-like equilibrium in order to guarantee the existence of a weakened equilibrium. Nash's approach to the problem for strategic games is probabilistic, i.e. continuous, and static. CP and BR approaches for CP and BR games are discrete and dynamic. This paper proposes an approach that lies between those two different approaches: a discrete and static approach. multi strategic games are introduced as a formalism that is able to express both sequential and simultaneous decision-making, which promises a good modelling power. multi strategic games are a generalisation of strategic games and sequential graph games that still enjoys a Cartesian product structure, i.e. where agent actually choose their strategies. A pre-fixed point result allows guaranteeing existence of discrete and non deterministic equilibria. On the one hand, these equilibria can be computed with polynomial (low) complexity. On the other hand, they are effective in terms of recommendation, as shown by a numerical example.

Introduction

Not all strategic games have a (pure) Nash equilibrium. On the one hand, Nash's probabilistic approach copes with this existence problem with an ad hoc solution: Nash's solution is dedicated to a setting with real-valued payoff functions. On the other hand, CP and BR games propose an abstract and general approach that is applicable to many types of game. Both approaches generalise the notion of Nash equilibrium and guarantee the existence of a weakened Nash equilibrium. There are two main differences between the two approaches though. First, Nash's approach considers finite objects and yields continuous objects, whereas the CP and BR approach preserves finiteness. Second, Nash's approach is static, whereas the CP and BR approach is dynamic: Nash's approach is static because a probabilistic Nash equilibrium can be interpreted as a probabilistic status quo that is (pure) Nash equilibrium of a probabilised game. The Cartesian product structure enables a static approach. CP and BR approach is dynamic because a CP or BR equilibrium can be interpreted as a limit set of states that are tied together by explicit forces. It may be interesting to mix features from both approaches, and to present for instance a discrete and static notion of equilibrium. Actually, such an approach was already adopted in [START_REF] Le | Non-determinism and Nash equilibria for sequential game over partial order[END_REF], whose purpose was to provide sequential tree games with a notion of discrete non deterministic equilibrium. This approach assumed partially ordered payoffs, and simple "backward induction" guarantees existence of non deterministic subgame perfect equilibrium. This result is superseded by [START_REF] Le | Acyclicity of preferences, Nash equilibria, and subgame perfect equilibria: a formal and constructive equivalence[END_REF] which adopts a completely different approach, but the discrete non determinism spirit can be further exploited.

Contribution

This paper introduces the concept of abstract strategic games, which corresponds to traditional strategic games where real-valued payoff functions have been replaced with abstract objects called outcomes. In addition, the usual total order over the reals has been replaced with binary relations, one per agent, that account for agent's preferences over the outcomes. Abstract strategic games thus generalise strategic games like abstract sequential tree games generalise sequential tree games. A notion of Nash equilibrium is defined, but not all abstract strategic games have a Nash equilibrium since traditional strategic games already lack this property.

Like Nash did for traditional strategic games, an attempt is made to introduce probabilities into these new games. However, it is mostly a failure because there does not seem to exist any extension of a poset to its barycentres that is relevant to the purpose. So, instead of saying that "an agent chooses a given strategy with some probability", this paper proposes to say that "the agent may choose the strategy", without further specification.

The discrete non determinism proposed above is implemented in the notion of non deterministic best response (ndbr ) multi strategic game. As hinted by the terminology, the best response approach is preferred over the convertibility preference approach for this specific purpose. (Note that discrete non determinism for abstract strategic games can be implemented in a formalism that is more specific and simpler than ndbr multi strategic games, but this general formalism will serve further purposes.) This paper defines the notion of ndbr equilibrium in these games, and a pre-fixed point result helps prove a sufficient condition for every ndbr multi strategic game to have an ndbr equilibrium. An embedding of abstract strategic games into ndbr multi strategic games provides abstract strategic games with a notion of non deterministic (nd ) equilibrium that generalises the notion of Nash equilibrium. Since every abstract strategic game has an nd equilibrium (under some condition), the discrete non deterministic approach succeeds where the probabilistic approach fails, i.e. is irrelevant. This new approach lies between Nash's approach, which is continuous and static, and the abstract approaches of CP and BR games, which are discrete and dynamic. Indeed, this notion of nd equilibrium is discrete and static. It is deemed static because it makes use of the Cartesian product structure, which allows interpreting an equilibrium as a "static state of the game".

This paper also defines the notion of multi strategic game that is very similar to the notion of ndbr multi strategic game, while slightly less abstract. multi strategic games are actually a generalisation of both abstract strategic games and sequential graph games. Informally, they are games where a strategic game takes place at each node of a graph. (A different approach to "games network" can be found in [START_REF] Manceny | Réseaux de jeux. Une extension de la théorie des jeux pour la modélisation des interactions locales[END_REF]) They can thus model within a single game both sequential and simultaneous decision-making mechanisms. An embedding of multi strategic games into ndbr multi strategic games provides multi strategic games with a notion of non deterministic (nd ) equilibrium. In addition, a numerical example shows that the constructive proof of nd equilibrium existence can serve as a recommmendation to agents on how to play, while the notion of Nash equilibrium, as its stands, cannot lead to any kind of recommendation.

Contents

Section 2 defines abstract strategic games and their abstract Nash equilibria. Section 3 considers probabilities to relax the definition of Nash equilibrium in abstract strategic games, and concludes that discrete non determinism is required. Section 4 proves a pre-fixed point result. Section 5 introduces the non deterministic best response multi strategic games and their non deterministic best response equilibria. Then it gives a sufficient condition for these games to have such an equilibrium. Section 6 embeds abstract strategic games into ndbr multi strategic games, and thus provides a notion of (existing) non deterministic equilibrium for abstract strategic games. It also gives a few examples. Section 7 defines multi strategic games and embeds them into ndbr multi strategic games, and thus provides a notion of non deterministic equilibrium for multi strategic games.

Abstract Strategic Games

This section defines abstract strategic games and their abstract Nash equilibria. Two embeddings show that abstract strategic games can be seen as either CP games or BR games when preferences are acyclic.

Informally, abstract strategic games are traditional strategic games where real-valued payoff functions have been replaced with abstract objects named outcomes. In addition for each agent, one binary relation over outcomes accounts for the preference of the agent for some outcomes over some others.

Definition 1 (Abstract strategic games) Abstract strategic games are 4tuples A, S, P, (⊳ a ) a∈A where:

-A is a non-empty set of agents, -S = a∈A S a is the Cartesian product of non-empty sets of individual strategies, -P : S → Oc is a function mapping strategy profiles to outcomes.

-⊳ a is a binary relation over outcomes, and oc ⊳ a oc ′ says that agent a prefers oc ′ over oc.

The example below shows a traditional strategic game on the left-hand side, and an abstract strategic game on the right-hand side.

h 1 h 2 v 1 0 2 1 1 v 2 0 1 2 0 h 1 h 2 v 1 oc 1 oc 2 v 2 oc 3 oc 4
For a given game, each agent can compare strategy profiles by comparing their outcomes using the function P . Notation 1 Let A, S, P, (⊳ a ) a∈A be an abstract strategic game and let s and s ′ be in S.

s ⊳ a s ′ ∆ = P (s) ⊳ a P (s ′ )
Happiness of an agent is defined below, in a convertibility preference style.

Definition 2 (Agent happiness) Let A, S, P, (⊳ a ) a∈A Happy(a, s)

∆ = ∀s ′ ∈ S, ¬(s ′ -a = s -a ∧ s ⊳ a s ′ )
As usual, Nash equilibrium means happiness for all agents.

Definition 3 (Nash Equilibrium)

Eq g (s) ∆ = ∀a ∈ A, Happy(a, s)
There exists a natural embedding of abstract strategic games into CP games, as described below.

Lemma 4 Let g = A, S, P, (⊳ a ) a∈A be a strategic game.

s / / a o o s ′ ∆ = s -a = s ′ -a , Then g ′ = A, S, ( / / a o o ) a∈A , (⊳ a )
a∈A is a CP game and the embedding preserves and reflects Nash equilibria. Eq g (s) ⇔ Eq g ′ (s) When agents' preferences are acyclic, there exists also a natural embedding of abstract strategic games into BR games, as described below.

Lemma 5 Let g = A, S, P, (⊳ a ) a∈A be a strategic game. Assume that the ⊳ a are acyclic.

BR a (s) ∆ = {s -a } × {s ′ ∈ S a | ∀s ′′ ∈ S a , ¬(s -a ; s ′ ⊳ a s -a ; s ′′ )}
Then g ′ = A, S, (BR a ) a∈A is a BR game and the embedding preserves and reflects Nash equilibria.

Eq g (s) ⇔ Eq g ′ (s)

3 From Continuous to Discrete non determinism

This section tries to apply Nash's probabilistic compromise to an instance of abstract strategic games. Facing a half-failure, it notices that continuous non determinism, i.e. probabilities, carry "too much" information. Indeed, only a notion of discrete non deterministic strategies is needed to characterise the probabilistic Nash equilibria of the example. These non deterministic strategies are defined as non-empty subsets of strategies. Consider the following abstract strategic game involving agents v and h. The game has no (pure) Nash equilibrium.

oc 1 ⊳ V oc 3 oc 3 ⊳ H oc 4 oc 4 ⊳ V oc 2 oc 2 ⊳ H oc 1 h 1 h 2 v 1 oc 1 oc 2 v 2 oc 3 oc 4
Mixed strategies for abstract strategic games are defined the same way they are defined for traditional strategic games, i.e. through probability distributions. Mixed strategy profiles are of the following form, where α and β are probabilities that are chosen by agent v and agent h respectively.

αβ(v 1 , h 1 ) + α(1 -β)(v 1 , h 2 ) + (1 -α)β(v 2 , h 1 ) + (1 -α)(1 -β)(v 2 , h 2 )
In the traditional setting, this yields expected payoff functions. Since payoffs and probabilities are both real numbers, the expected payoffs are also real numbers. It is therefore natural to compare them by using the usual total order over the reals, i.e. the same order that is used when comparing payoffs of pure strategy profiles. In the abstract setting though, mixing the strategies induces a new type of object, say "expected outcomes". These expected outcomes are objects of the following form, where α and β are probabilities that are chosen by agent v and agent h respectively.

αβoc 1 + α(1 -β)oc 2 + (1 -α)βoc 3 + (1 -α)(1 -β)oc 4
These new objects are not outcomes a priori, so there is no obvious way to compare them a priori. The most natural way may be the following one. When both α and β are either 0 or 1, the expected outcome looks like an outcome. For instance, if α and β equal 1, the expected outcome is as follows.

1.oc 1 + 0.oc 2 + 0.oc 3 + 0.oc 4

Along the two preference relations that are defined in the strategic game above, it is possible to define preferences among these four specific expected outcomes. For instance, oc 1 ⊳ v oc 3 yields the following.

1.oc 1 + 0.oc 2 + 0.oc 3 + 0.oc 4 ⊳ v 0.oc 1 + 0.oc 2 + 1.oc 3 + 0.oc 4 When either α or β is either 0 or 1, the new preference relations can be extended naturally, i.e. consistently with the original preferences. Informally, if agent v prefers oc 3 over oc 1 then, by extension, he will prefer mixed outcomes giving more weight to oc 3 than to oc 1 . For instance, if α ′ < α then the preference of agent v is extended as follows.

αoc 1 + 0.oc 2 + (1 -α)oc 3 + 0.oc 4 ⊳ v α ′ oc 1 + 0.oc 2 + (1 -α ′ )oc 3 + 0.oc 4
However, extending non-trivially the preferences to all expected outcomes would require an artificial choice. Indeed, consider the following two expected outcomes obtained by α = 1 2 and β = 1 2 for the first one, and by α = 1 2 and β = 1 3 for the second one. In the strategic game above, these expected outcomes correspond to mixed strategy profiles that agent h can convert to each other. On the one hand, the weights attributed to oc 1 and oc 2 are better in the first expected outcome, according to h. On the other hand, the weights attributed to oc 3 and oc 4 are better in the second expected outcome, according to h. These two arguments sound "contradictory". Moreover, there is nothing in the original preference relation that suggests to give priority to one argument over the other. So it is reasonable to say that h prefers neither of these expected outcomes. Thus are defined the extensions of the preference relations. This completes the definition of the (probabilistic) abstract strategic game derived from the finite abstract strategic game example above. In such a setting, the probabilistic Nash equilibria are the mixed strategy profiles

αβ(v 1 , h 1 )+α(1-β)(v 1 , h2)+(1-α)β(v 2 , h 1 )+(1-α)(1-β)(v 2 , h 2 ),
where 0 < α < 1 and 0 < β < 1. Therefore almost all mixed strategy profiles are probabilistic Nash equilibria, which does not seem not be a desirable property.

In the probabilistic setting, a strategy of an agent is said to be "used" if the agent gives a non-zero probability to this strategy. With this terminology, the above remark can be rephrased as follows. In the above strategic game with its above probabilistic extension, a mixed strategy profile is a probabilistic Nash equilibrium iff both agents use both their strategies. This suggests that, in abstract strategic games, the actual values of the probabilities are irrelevant to the Nash equilibrium predicate. Only their being zero or not is relevant. This motivates the definition of discrete non deterministic strategies that only says which strategies are used. Note that an agent must use at least one strategy, like in the probabilistic (and the pure) setting. For each agent, a discrete non deterministic strategy can therefore be seen as a non-empty subset of the set of its strategies.

A Simple Pre-Fixed Point Result

This section proves a pre-fixed-point result, i.e. the existence of a y such that y F (y) for all F and that comply with given constraints.

Meet semi-lattices are defined below like in the literature. They are posets that guarantee existence of greatest lower bound of any two elements. The terminology of "meet" seems to come from the set-theoretic intersection.

Definition 6 (Meet semi-lattice) A meet semi-lattice is a partially ordered set (S, ), i.e. the binary relation is reflexive and transitive, such that any sets with two elements has a greatest lower bound. Defined as a specific type of posets, meet semi-lattices have algebraic properties. (Actually, meet semi-lattices are sometimes defined as algebraic structures from where an ordering is derived.) Definition 7 In a partially ordered set, a greatest lower bound of two elements is unique, which induces the binary operator "greatest lower bound". This operator is commutative and associative, which enables the definition of the greatest lower bound of any non-empty finite subset of S. Let us call inf this greatest lower bound function.

Given a function from a meet semi-lattice to itself, a meeting point is an element of the lattice such that every decreasing sequence that starts with the meeting point is not too much "scattered" by the function. This is accurately described below.

Definition 8 Let (S, ) be a meet semi-lattice with least element m, and let inf be the infimum function corresponding to . Let F be a function from S to itself and let x be in S. Assume that for all x 1 . . .

x n such that m = x 1 • • • x n x, we have inf (F (x 1 ), . . . , F (x n ), x) = m. If x = m then x is said to be a F -meeting point,

and one writes M F (x).

The F -meeting point predicate is preserved by the greatest lower bound operator used with the image of the point by F , as stated below.

Lemma 9 Let (S, ) be a meet semi-lattice with least element m; let inf be the infimum function corresponding to ; and let F be a function from S to itself. The following formula holds.

M F (x) ⇒ M F • inf (x, F (x))

Proof

Assume M F (x), so x and m are different. By reflexivity x x, so inf (x,

F (x)) = m by definition of meeting point. Assume m = x 1 • • • x n inf (x, F (x)), so m = x 1 • • • x n x x since inf (x, F (x)) x by definition of inf . So inf (F (x 1 ), . . . , F (x n ), F (x), x) = m since x is a F - meeting point. Therefore inf (F (x 1 ), . . . , F (x n ), inf (F (x), x)) = m,
by associativity of the greatest lower bound operator underlying the infimum function inf . So inf (x, F (x)) is a F -meeting point.

The F -meeting point predicate preservation can be combined with the assumption that there exists no infinite strictly decreasing sequence. In this case, iteration of lemma 9 yields a non-trivial pre fixed point of F .

Lemma 10 Let (S, ) be a meet semi-lattice with least element m, and assume that is well-founded. Let F be a function from S to itself. If there exists a Fmeeting point, then there exists a F pre fixed point different from m, i.e. there exists y = m such that y F (y).

Proof

Assume M F (x 0 ). An infinite sequence of elements of S is built as follows. It starts with x 0 , and it is gradually defined by induction. Assume x n , . . . , x 0 such that M F (x n ), and

x k+1 = inf (x k , F (x k )) for all 0 ≤ k < n. Let x n+1 = inf (x n , F (x n ))
. By Lemma 9, M F (x n+1 ). By well-foundness assumption, there exists n such that x n+1 = x n , which means that x n = inf (x n , F (x n )), so x n F (x n ). Moreover, M F (x n ) by construction of the sequence, so x n = m.

Non deterministic best Response multi Strategic Games

Using the concept of discrete non deterministic strategy, this section defines non deterministic best response multi strategic games and their non deterministic Nash equilibria. This section also proves a sufficient condition for non deterministic Nash equilibrium existence in every non deterministic best response sequential graph game. These results will be used to guarantee existence of non deterministic equilibrium for abstract strategic games and sequential graph game.

Informally, non deterministic best response multi strategic games involve agents who play on several (abstractions of) strategic games at the same time. Agents' strategies are non deterministic, i.e. on each game each agent has to choose one or more (pure) strategies among his available strategies. When all the opponents of an agent have chosen their non deterministic strategies on all games, a function tells agent a what his non deterministic best responses are. These games are formally defined below.

Definition 11 (Non deterministic best response multi strategic games)

An ndbr multi strategic game is pair (S i a ) i∈I a∈A , (BR a ) a∈A complying with the following.

-I is a non-empty set of indices and A is a non-empty set of agents.

-For all a in A, BR a is a function from Σ -a to Σ a , where Σ = a∈A Σ a and Σ a = i∈I P(S i a )-{∅} and

Σ -a = a ′ ∈A-{a} Σ a ′ .
Elements of Σ a are called nd strategies for a, and elements of Σ are called nd strategy profiles.

Informally, an agent is happy with an nd strategy profile if its own nd strategy is included in its best responses against other agents' nd strategies. Agents' happiness is formally defined as follows.

Definition 12 (Happiness) Let g = (S i a ) i∈I a∈A , (BR a ) a∈A be an ndbr multi strategic game, and let σ be in Σ.

Happy(σ, a)

∆ = σ a ⊆ BR a (σ -a )
As usual, (non deterministic) Nash equilibrium amounts to happiness for all agents.

Definition 13 (Non deterministic Nash equilibrium) Let g be an ndbr multi strategic game, g = (S i a ) i∈I a∈A , (BR a ) a∈A .

Eq g (σ)

∆ = ∀a ∈ A, Happy(σ, a)
The individual best response functions can be combined into a collective best response function from the non deterministic profiles into themselves.

Definition 14 (Combined best response) Given an ndbr multi strategic game with (BR a ) a∈A a family of agent best responses. The combined best response is a function from Σ to itself defined as follows.

BR(σ)

∆ = a∈A BR a (σ -a )
Through the combined best response function, the non deterministic Nash equilibria are characterised below as nd profiles included in their images by the combined best response.

Lemma 15 An ndbr equilibrium for g = (S i a ) i∈I a∈A , (BR a ) a∈A is characterised as follows.

Eq g (σ) ⇔ σ ⊆ BR(σ)

Like in BR games, it is easy to define agents' strict happiness.

Definition 16 (Strict happiness) Let g = (S i a ) i∈I a∈A , (BR a ) a∈A be an ndbr multi strategic game, and let σ be in Σ.

Happy + (σ, a) ∆ = σ a = BR a (σ -a )
Then, (non deterministic) strict Nash equilibrium is defined as strict happiness for all agents.

Definition 17 (Non deterministic strict Nash equilibrium) Let g be an ndbr multi strategic game, g = (S i a ) i∈I a∈A , (BR a ) a∈A , and let σ be in Σ.

Eq + g (σ)

∆ = ∀a ∈ A, Happy + (σ, a)
The following embedding of non deterministic best response multi strategic games into BR games preserves an reflects equilibria.

Lemma 18 Let g = (S i a ) i∈I a∈A , (BR a ) a∈A be an ndbr multi strategic game. Define BR ′ a with a Cartesian product below, for σ ∈ Σ.

BR ′ a (σ) ∆ = {σ -a } × i∈I P(BR i a (σ -a )) -{∅} Where BR i a (σ -a ) is the i-projection of BR a (σ -a ).
Then the object g ′ defined by g ′ = A, Σ, (BR ′ a ) a∈A is a BR game and Nash equilibria correspond as follows.

Eq g ′ (σ) ⇔ Eq g (σ)

Proof

Let σ be in Σ = a∈A i∈I (P(S i a ) -{∅}). The following chain of equivalences proves the claim.

Eq g ′ (σ) ⇔ ∀a, σ ∈ BR ′ a (σ) ⇔ ∀a, σ ∈ {σ -a } × i∈I P(BR i a (σ -a )) -{∅} ⇔ ∀a, σ a ∈ i∈I P(BR i a (σ -a )) -{∅} ⇔ ∀a, σ a ⊆ BR a (σ -a ) ⇔ Eq g (σ)
The remainder of the section invokes the fixed-point results of section 4, but prior to that, a meet lattice needs to be identified.

Lemma 19 Given an ndbr multi strategic game (S i a ) i∈I a∈A , (BR a ) a∈A , the poset (Σ ∪ {∅}, ⊆) is a meet semi-lattice with least element ∅.

A first equilibrium existence result is given below.

Lemma 20 Given an ndbr multi strategic game (S i a ) i∈I a∈A , (BR a ) a∈A , if there exists a BR-meeting point, then there exists a non deterministic Nash equilibrium.

Proof

By lemma 10, if there exists a BR-meeting point, then there exists a non-empty pre fixed point σ for BR, i.e. there exists σ = ∅ such that σ ⊆ BR(σ).

It is an ndbr equilibrium by definition.

The main equilibrium existence result is stated below.

Lemma 21 Consider an ndbr multi strategic game (S i a ) i∈I a∈A , (BR a ) a∈A . Let σ be in Σ. Assume that for all agents a, for all γ 1 . . .

γ n in Σ -a , if γ n ⊆ • • • ⊆ γ 1 ⊆ σ -a then ∩ 1≤k≤n BR a (γ k ) ∩ σ a = ∅.
In this case, the game has an ndbr equilibrium.

Proof By lemma 20, it suffices to show that there exists a BR-meeting point. Let us prove that σ is such a meeting point. First of all, σ is non-empty since it belongs to Σ. Second, assume σ

1 . . . σ n in Σ such that σ 1 ⊆ • • • ⊆ σ n ⊆ σ. So for all agents a, σ 1 -a ⊆ • • • ⊆ σ n -a ⊆ σ -a .
By assumption, ∩ 1≤k≤n BR a (σ k -a )∩σ a = ∅, which amounts to (∩ 1≤k≤n BR(σ k ) ∩ σ) a = ∅. Since this holds for all a, we have

∩ 1≤k≤n BR(σ k ) ∩ σ = ∅. Therefore σ is a BR-meeting point.
Equilibria are preserved when "increasing" the best response functions, as stated below.

Lemma 22 Let g = (S i a ) i∈I a∈A , (BR a ) a∈A and g ′ = (S i a ) i∈I a∈A , (BR ′ a ) a∈A be two ndbr multi strategic games such that for all a in A, for all γ in Σ -a , BR a (γ) ⊆ BR ′ a (γ). In this case, the following implication holds.

Eq g (σ) ⇒ Eq g ′ (σ) Proof
Since for all a in A, for all γ in Σ -a , BR a (γ) ⊆ BR ′ a (γ), it follows that for all σ in Σ, BR(σ) ⊆ BR ′ (σ). So, σ ⊆ BR(σ) implies σ ⊆ BR ′ (σ).

Discrete and Static Compromising Equilibrium for

Abstract Strategic Games Subsection 6.1 embeds abstract strategic games into ndbr multi strategic games, and thus provides a notion of non deterministic Nash equilibrium for abstract strategic games. Finally it proves equilibrium existence for all abstract strategic games. Subsection 6.2 gives an example of such non deterministic Nash equilibrium on a strategic game with real-valued payoff functions. The building of the equilibrium is described step by step. Subsection 6.3 suggests by a numerical example that the constructive proof of existence of such an equilibrium yields a notion of recommendation that is better on average than playing randomly.

non deterministic Equilibrium Existence

The following definition extends orders over functions' codomains to orders over (restrictions of) functions.

Definition 23 Let f and f ′ be functions of type A → B, and let A ′ be a subset of A. Let ≺ be an irreflexive binary relation over B, and let be its reflexive closure.

f A ′ f ′ ∆ = ∀x ∈ A ′ , f (x) f ′ (x) f ≺ A ′ f ′ ∆ = f A ′ f ′ ∧ ∃x ∈ A ′ , f (x) ≺ f ′ (x) One simply writes f ≺ f ′ instead of f ≺ A f ′ .
For example if the two functions are represented by vectors of naturals with the usual total order, then (1, 1) < (1, 2), (0, 2) < (1, 2) and (0, 1) < (1, 2).

The extension above preserves strict partial orders, as stated below.

Lemma 24 If ≺ is a strict partial order over B, then the derived ≺ A over functions of type A → B is also a strict partial order.

Given finitely many functions of the same type, given an order on the codomain, given finitely many subsets of the domain that are totally ordered by inclusion, one of these functions is maximal for the extension order with respect to each of the subsets. This is proved by the following.

Lemma 25 Let E be a finite set of functions of type A → B. Let ≺ be an irreflexive and transitive binary relation over B, and let be its reflexive closure. For any ∅ = A 0 ⊆ • • • ⊆ A n ⊆ A there exists an f in E that is maximal with respect to all the extended orders from ≺ A0 to ≺ An .

Proof

By induction on n. First case, n = 0. There exists an f in E that is maximal, i.e. have no successor, with respect to ≺ A0 since ≺ A0 is a partial order. Second case, assume that the claim holds for n and let

∅ = A 0 ⊆ • • • ⊆ A n+1 be subsets of A. Let f in E be maximal with respect to all the ≺ A0 • • • ≺ An . Let f ′ be maximal with respect to ≺ An+1 among the functions in E that coincide with f on A n . Since ∅ = A 0 ⊆ • • • ⊆ A n , the function f ′ is maximal in E with respect to all the ≺ A0 • • • ≺ An . Let f ′′ in E be such that f ′ An+1 f ′′ . So f ′ An f ′′ since A n ⊆ A n+1
. Therefore f ′ and f ′′ coincide on A n by maximality of f ′ with respect to ≺ An . Since f and f ′ coincide on A n , the functions f and f ′′ also coincide on A n . Therefore ¬(f ′ ≺ An+1 f ′′ ) by definition of f ′ , which shows that f ′ is also maximal with respect to ≺ An+1 .

Below, an ndbr multi strategic game is built from an abstract strategic game. This ndbr multi strategic game always has an ndbr equilibrium. In the notation s ⊳ γ a s ′ below, the strategies s and s ′ are seen as functions from S a to the outcomes.

Lemma 26 Let g = A, S, P, (⊳ a ) a∈A be an abstract strategic game. Assume that the ⊳ a are strict partial orders, i.e. irreflexive and transitive. For each agent a and each γ in Σ -a , the following defines a subset of S a .

BR a (γ) ∆ = {s ∈ S a | ∀s ′ ∈ S a , ¬(s ⊳ S-a a s ′ ) ∧ ∀s ′ ∈ S a , ¬(s ⊳ γ a s ′ ) ∧ ∃c ∈ γ, ∀s ′ ∈ S a , ¬(s ⊳ {c} a s ′ ) }
The object (S a ) a∈A , (BR a ) a∈A is an ndbr multi strategic game, and it has an ndbr equilibrium.

Proof

Let a be an agent. First note that, through the function P , every strategy s in S a can be seen as a function from S -a to the outcomes Oc. Let γ 1 ⊆ • • • ⊆ γ n be in Σ -a and let c be in γ 1 . According to lemma 25, there exists an s in S a that is maximal with respect to ⊳ {c} a , ⊳ γ1 a , . . . , ⊳ γn a , ⊳ S-a a

. By definition of BR a (third conjunct), this strategy s is in all the BR a (γ 1 ), . . . , BR a (γ n ). First, this shows that BR a returns non-empty sets, so (S a ) a∈A , (BR a ) a∈A is indeed an ndbr multi strategic game. Second, this game has an ndbr equilibrium by lemma 21.

The ndbr equilibrium for the derived ndbr multi strategic game is called a non deterministic equilibrium for the original abstract strategic game. Other similar definitions are possible for non deterministic equilibrium. Especially definitions more generous than the one in lemma 26, which guarantee the existence of a non deterministic equilibrium, according to lemma 22. This yields the following lemma.

Lemma 27 Let g = A, S, P, (⊳ a ) a∈A be a strategic game. Assume that the ⊳ a are strict partial orders, i.e. irreflexive and transitive. For each agent a and each γ in Σ -a , the following defines three subsets of S a .

BR 1 a (γ) ∆ = {s ∈ S a | ∀s ′ ∈ S a , ¬(s ⊳ S-a a s ′ )} BR 2 a (γ) ∆ = {s ∈ S a | ∀s ′ ∈ S a , ¬(s ⊳ γ a s ′ )} BR 3 a (γ) ∆ = {s ∈ S a | ∃c ∈ γ, ∀s ′ ∈ S a , ¬(s ⊳ {c} a s ′ )} BR 4 a (γ) ∆ = {s ∈ S a | ∀s ′ ∈ S a , ∃c ∈ γ, ¬(s ⊳ {c} a s ′ )}
The object A, S, (BR i a ) a∈A , for i between 1 and 4, is an ndbr multi strategic game, and it has an ndbr equilibrium.

The first three BR i a above correspond tho the three conjuncts of the BR a of lemma 26, and BR 4 a is even more generous than BR 2 a . Note that BR 2 and BR 4 somewhat relate to the notions of dominated strategy, studied in [START_REF] Gale | A theory of n-person games games with perfect information[END_REF] and [START_REF] Duncan | Games and Decisions[END_REF], and rationalizability, studied in [START_REF] Bernheim | Rationalizable strategic behavior[END_REF] and [START_REF] Dg Pearce | Rationalizable strategic behavior and the problem of perfection[END_REF]. These notions are more recently discussed in [START_REF] Hillas | Foundations of strategic equilibrium[END_REF], for instance. (These notions are also related to "backward induction", but this thesis does not further explore the matter.)

The rest of the subsection discusses a few properties of these equilibria.

Definition 28 (Cartesian union) Let i∈ I A i be a cartesian product. The Cartesian union is defined as follows within i∈ I A i .

p i (D) ∆ = {x i | x ∈ D} B ∪ × C ∆ = i∈ I p i (B) ∪ p i (C)
Where p i is the projection on A i .

The equilibria related to BR 1 define a simple structure, as stated below.

Lemma 29 The ndbr equilibria related to BR 1 are the elements of Σ that are included in a∈A {s ∈ S a | ∀s ′ ∈ S a , ¬(s ⊳ S-a a s ′ )}.

Proof For all σ in Σ, BR 1

(σ) = a∈A {s ∈ S a | ∀s ′ ∈ S a , ¬(s ⊳ S-a a s ′ )}.
The following lemma states that the ndbr equilibria related to BR 3 define a Cartesian union lattice.

Lemma 30 Let g = A, S, P, (⊳ a ) a∈A be a strategic game. Assume that the ⊳ a are strict partial orders, i.e. irreflexive and transitive. If equilibrium is defined through BR 3 then the following holds.

Eq g (σ) ∧ Eq g (σ ′ ) ⇒ Eq g (σ ∪ × σ ′ ) Proof It suffices to prove that σ ∪ × σ ′ ⊆ BR 3 (σ ∪ × σ ′ ). Let s be in σ ∪ × σ ′ .
If s is in σ then it is also in BR 3 (σ) by equilibrium assumption. So for every agent a, there exists c in σ -a (so c is also in σ -a ∪ × σ ′ -a ) such that for all s ′ in S a , neg(s

⊳ {c} a s ′ ). Therefore s is in BR 3 (σ ∪ × σ ′ ). Same scenario if s is in σ ′ . So σ ∪ × σ ′ ⊆ BR 3 (σ ∪ × σ ′ ).
The following lemma states that the ndbr equilibria related to BR 4 define a Cartesian union lattice.

Lemma 31 Let g = A, S, P, (⊳ a ) a∈A be a strategic game. Assume that the ⊳ a are strict partial orders, i.e. irreflexive and transitive. If equilibrium is defined through BR 4 then the following holds.

Eq g (σ) ∧ Eq g (σ ′ ) ⇒ Eq g (σ ∪ × σ ′ ) Proof It suffices to prove that σ ∪ × σ ′ ⊆ BR 4 (σ ∪ × σ ′ ). Let s be in σ ∪ × σ ′ .
If s is in σ then it is also in BR 4 (σ) by equilibrium assumption. So for all s ′ in S a , there exists c in σ -a such that ¬(s ⊳ {c} a s ′ ), and each of these c also belongs to σ -a ∪ × σ ′ -a . Therefore s is in BR 4 (σ

∪ × σ ′ ). Same scenario if s is in σ ′ . So σ ∪ × σ ′ ⊆ BR 4 (σ ∪ × σ ′ ).

Example

The proof of existence of an ndbr equilibrium is constructive, so it provides for free an algorithm that computes such an equilibrium. The time complexity of the algorithm is polynomial with respect to the number of strategy profiles |S| (when each agent has at least two available strategies). Indeed informally, each call to BR dismisses at least one strategy of one agent, so it dismisses at least one profile. Therefore BR is called at most |S| times. Each use of BR invokes all the BR a , which needs (at most) to consider each agent strategy and decide whether or not this strategy is a best response. So there are at most |S| such decisions. Such a decision requires at most 3 × |S| calls to a ⊳ a . Therefore the time complexity of finding an equilibrium is at most cubic in the number of profiles |S|. This is a very rough approximation whose only purpose is to show that complexity is polynomial.

The example below is a strategic game with natural-valued payoff functions. Preference between naturals invokes the usual total order over the naturals. Let us apply the equilibrium algorithm to the game.

h 1 h 2 h 3 h 4 h 5 v 1 0 0 3 2 2 2 2 1 3 0 v 2 3 3 0 2 0 0 2 1 3 2 v 3 2 2 1 0 0 1 3 1 0 2 v 4 1 0 1 2 1 2 1 2 1 0 v 5 2 0 1 0 0 0 0 1 0 0
Informally, V may "play" either v 1 or v 2 or v 3 or v 4 or v 5 . In that context, column h 5 is smaller than h 1 according to agent H, so h 5 is not a best response of agent H. In the same way row v 5 is smaller than row v 3 . In addition, row v 4 is not a best response of agent V because for each column h i , row v 4 is smaller than some other row. Therefore, the combined best responses for the whole game are rows v 1 to v 3 and columns h 1 to h 4 , as shown below.

h 1 h 2 h 3 h 4 v 1 0 0 3 2 2 2 2 1 v 2 3 3 0 2 0 0 2 1 v 3 2 2 1 0 0 1 3 1
Now, agent V may play either v 1 or v 2 or v 3 . Column h 4 is not a best response of agent H because for each row v 1 to v 3 , column h 4 is smaller than some other column. So the game "shrinks" again as show below.

h 1 h 2 h 3 v 1 0 0 3 2 2 2 v 2 3 3 0 2 0 0 v 3 2 2 1 0 0 1
In the same way, for columns h 1 to h 3 , row v 3 is smaller than some other row.

h 1 h 2 h 3 v 1 0 0 3 2 2 2 v 2 3 3 0 2 0 0
Column h 3 is smaller than column h 2 . This yield the following irreducible game.

h 1 h 2 v 1 0 0 3 2 v 2 3 3 0 2 Therefore {v 1 , v 2 }×{h 1 , h 2 }
is a non deterministic equilibrium for the original game.

Comparisons

Consider the following class of games G, where * can take two values, namely 1 and -1, and where the preferences are along the usual order -1 < 1.

h 1 h 2 v 1 * * * * v 2 * * * *
For each agent, the arithmetic mean of its payoff over the four payoff functions of all games in the class is 0, by a "simple symmetry". However for each agent, the arithmetic mean of its payoff over the payoff functions inside the ndbr equilibrium of all games in the class is 3/8.

Lemma 32 For a game g in G, let eq(g) be the ndbr equilibrium built by the proof of lemma 26.

1 |G| × g∈G 1 |e(g)| × s∈eq(g) P (s, v) = 3 8

Proof

In the games of class G, considering only the payoffs of one agent yields matrices like below. The first row displays the matrices whose two rows are equivalent to agent v (the agent choosing the row of the matrix). The second row displays the matrices whose two rows are not equivalent to agent v. The figure on the top of matrices represent how many actual matrices they represent up to rotation.

1 2 2 1 1 1 1 1 1 -1 1 -1 1 -1 -1 1 -1 -1 -1 -1 4 2 4 1 1 1 -1 1 1 -1 -1 1 -1 -1 -1
The payoff that is induced by the first matrix is 1: whatever may be the matrix of agent h, agent v gets 1. In the same way, the fourth matrix induces -1. Now assume that the payoff matrix of agent v is the second one. When the payoff matrix of agent h ranges over the matrices above, eq(g) will involve sometimes only the left-hand side, sometimes only the right-hand side and sometimes (the same number of times by symmetry), and sometimes both. So on average, the third matrix yields payoff 0. Same scenario for the third matrix.

The payoff that is induced by the sixth matrix is 1. The fifth matrix induces payoff 1 too, because an equilibrium involves only the first row whatever the matrix of agent h is. As to the seventh matrix it induces payoff 0 "by symmetry", because an equilibrium involves only the first row whatever the matrix of agent h is. Therefore the arithmetic mean is 1+4+2-1 16 = 3 8 .

The rest of the subsection establishes a connection between the non deterministic equilibria of abstract strategic games and the or-best response strict equilibria of abstract strategic games seen as BR games.

Lemma 33 Let g = A, S, P, (⊳ a ) a∈A be an abstract strategic game. Assume that the ⊳ a are strict partial orders, i.e. irreflexive and transitive. For each agent a and each γ in Σ -a , the following defines a subset of S a .

BR 3 a (γ) ∆ = {s ∈ S a | ∃c ∈ γ, ∀s ′ ∈ S a , ¬(s ⊳ {c} a s ′ )}
The object g 3 = A, S, (BR 3 a ) a∈A is an ndbr multi strategic game. For each agent a and each s in S, the following defines a non-empty subset of S, more specifically an element of Σ.

BR ′ a (s) ∆ = {s -a } × {s ′ ∈ S a | ∀s ′′ ∈ S a , ¬(s ′ ⊳ {s-a} a s ′′ )}
The object g ′ = A, S, (BR ′ a ) a∈A is a BR game. Then the following holds.

Eq + g ′ (C) ⇒ Eq g (p(C))
Where p(C) = a∈A p a (C) is the smallest (for set inclusion) ndbr multi strategy profile including C.

Proof

By lemma 27, g 3 is an ndbr multi strategic game, and by lemma 5, g ′ is a BR game. By assumption and by definition of or-best response strict equilibrium, C = BR ′∪ (C). One must show that p(C) ⊆ BR 3 (p(C)). Let s be in p(C). It suffices to prove that s a is in BR 3 a (p -a (C)) for all a. Let a be an agent. By definition of p, s a is in p a (C), and by definition of p a there exists c in S -a such that c; s a is in C. Such a c is in p -a (C). Let s 1 → a s 2 stand for s 2 ∈ BR ′ a (s 1 ) and → stand for ∪ a∈A → a . Case split on whether or not c; s a → a c; s a . If c; s a → a c; s a then, by definition, ¬s a ⊳ {c} a s ′ ) for all s ′ in S a , so s a is in BR 3 a (p -a (C)). Now assume that c; s a → a c; s a . By definition, BR ′ a returns non-empty sets, so c; s a → a c; s ′ a for some s ′ a = s a . Recall that C is a → strongly connected component, so c; s ′ a → + c; s a , where → + is the transitive closure of →. This decomposes in c; s ′ a → + c ′ ; s ′′ a → a c ′ ; s a → + c; s a for some c ′ and s ′′ a . More specifically, c ′ ; s ′′ a → a c ′ ; s a , with c ′ in p -a (C). This implies that s a is in BR 3 a (p -a (C)). The ndbr equilibrium given by the implication Eq + g ′ (C) ⇒ Eq g (p(C)) above is not always strict. More specifically, the following example shows that Eq + g ′ (C) ∧ ¬Eq + g (p(C)) for some or-best response equilibrium C. The example involves three agents each of whose converts along one dimension of the cube. Outcomes are payoff functions. The three nodes linked by doublelines constitute an or-best response strict equilibrium. The projection of the equilibrium is made of the four upper nodes, and the combined best response to this is the whole cube due to the two right-hand nodes in the back.

1, 1, 1 0, 0, 0 1, 1, 1 1, 1, 1 0, 0, 0 1, 1, 1 0, 0, 0 0, 0, 0

Discrete and Static Compromising Equilibrium for multi Strategic Games

This section defines multi strategic games and their non deterministic strategy profiles. Then, it defines a notion of preference among sequences of sets of outcomes, which yields a notion of (global) nd equilibrium. An embedding of these multi strategic games into the ndbr multi strategic games shows that multi strategic games always have an nd equilibrium. Since sequential graph games can be embedded into multi strategic games, this also provides sequential graph games with a notion of nd equilibrium that enjoys guarantee of existence. More subtle notions of equilibrium could be defined, which would yield stronger results. However, the notion that is defined here intends to be a simple one. In addition, the section discusses a relevant embedding of strategic games into multi strategic games. multi strategic games have a graph-like structure. At each node of the game, all agents play a strategic game to choose the outcome as well as the move to the next node. Another strategic game corresponds to this next node. So, a play in a multi strategic game is an infinite sequence of local plays in strategic games followed by outcomes. The notion of multi strategic game is defined below.

Definition 34 (multi strategic game) A multi strategic game is a pair S, (P n ) n∈V that complies with the following.

-S = n∈V a∈A S n a , where V is a non-empty set of indices, A is a nonempty set of agents, and S n a is a non-empty set of strategies. -P n is of type S n → OC × V , where Oc is a non-empty set of outcomes.

The agents' (pure) strategies are the elements of S a = n∈V S n a and the (pure) strategy profiles are the elements of S.

The following example depicts a multi strategic game that involves two agents, say vertical and horizontal. At each node vertical chooses the row and horizontal chooses the column. The game involves natural-valued payoff functions. The first figure corresponds to agent vertical and the second figure to agent horizontal. At a node, if a payoff function is enclosed in a small box with an arrow pointing from the bow to another node, it means that the corresponding strategy profile leads to this other node. If a payoff function is not enclosed in a small box, it means that the corresponding strategy profile leads to the same node. For instance below, If the play start at the top-left node and if the agents choose the top-left profile, then both agents get payoff 2 and the same strategic game is played again. Whereas if the agents choose the top-right profile, vertical gets payoff 2 and horizontal gets payoff 1, and the agents have to play in the top-right node. Starting from every node, a strategy profile induces infinite sequences of outcomes. It is therefore possible to define local/global equilibria for multi strategic games in the same way that they are defined for sequential graph games. Then, it is possible to embed sequential graph games into multi strategic games in a way that preserves and reflects local/global equilibria. (The embedding consists in seeing a node of a sequential graph game as a 1-agent strategic game.)

It is possible to embed strategic games into multi strategic games such that Nash equilibria correspond to local/global equilibria. (The embedding consists in seeing a strategic game as a one-node multi strategic game looping on itself).

However, since not all strategic games have a Nash equilibrium, not all multi strategic games have a local/global equilibrium. That is why non determinism comes into play. = a∈A Σ n a be the set of local nd strategy profiles at node n. For σ in Σ, the objects σ a , σ n , and σ n a correspond to the projections of σ on Σ a , Σ n , and Σ n a . Consider an nd strategy profile. At a given node, the outcome and the next node that are prescribed by the profile may be undetermined, because of non determinism. However, the outcome is element of a determined set of outcomes and the next node is element of a determined set of nodes. The same phenomenon arises at each possible next nodes. Therefore, any path starting from a node and non deterministically following the prescription of the nd strategy profile yields a sequence whose kth element is element of a determined set of outcomes. These sets are defined below.

Definition 36 (Induced sequence of sets of outcomes) Let g = S, (P n ) n∈V be a multi strategic game and let σ be in Σ. The induced sequence seq(σ, n) is an infinite sequence of non-empty subsets of outcomes.

seq(σ, n)

∆ = f st • P n (σ n ) • seq(σ, snd • P n (σ n ))
Where f (Z) = ∪ x∈Z f (x) for any f : X → Y and Z ⊆ X, and the projection operations are defined such that f st((x, y)) = x and snd((x, y)) = y.

Inclusion of nd strategy profiles implies component-wise inclusion of their sequences of sets of outcomes, as stated below.

Lemma 37 Let g = S, (P n ) n∈V be a multi strategic game.

σ ⊆ σ ′ ⇒ ∀n ∈ V, ∀k ∈ N, seq(σ, n)(k) ⊆ seq(σ ′ , n)(k)
For every agent, a preference binary relation over outcomes can be extended to a preference over sequences of sets of outcomes, as defined below. This extended preference amounts to component-wise preference for all sets in the sequence. However, there are other "natural" ways of extending preference over outcomes to preference over sequences of sets of outcomes (using limit sets or lexicographic ordering, for instance). So, what follows is only an example.

Definition 38 (Preference over sequences) Let ≺ be a binary relation over a set E. It can be extended to non-empty subsets of E as follows.

X ≺ set Y ∆ = ∀x ∈ X, ∀y ∈ Y, x ≺ y
This can be extended to sequences of non-empty subsets of E. Below, α and β are sequences of non-empty subsets of E.

α ≺ f ct β ∆ = ∀k ∈ N, α(k) ≺ set β(k)
The definition of ≺ set implies the following result.

Lemma 39 ∅ = X ′ ⊆ X ∧ ∅ = Y ′ ⊆ Y ∧ X ≺ set Y ⇒ X ′ ≺ set Y ′
Next lemma states that the preference extension ≺ f ct preserves an ordering property.

Lemma 40 If ≺ is a strict partial order then ≺ f ct is also a strict partial order.

The following result shows a preservation property involving ≺ f ct and strategy inclusion.

Lemma 41 Let g = S, (P n ) n∈V be a sequential graph game. Assume that γ ⊆ δ are both in Σ -a . Then the following holds.

seq(δ; σ a , n) ⊳ f ct a seq(δ; σ ′ a , n) ⇒ seq(γ; σ a , n) ⊳ f ct a seq(γ; σ ′ a , n) Proof By assumption and definition, seq(δ; σ a , n)(k) ⊳ set a seq(δ; σ ′ a , n)(k) for all k in N. Since γ ⊆ δ, lemma 37 implies that seq(γ; σ a , n)(k) ⊆ seq(δ; σ a , n)(k) and seq(γ; σ ′ a , n)(k) ⊆ seq(δ; σ ′ a , n)(k)
. Since these sets are all non-empty and by lemma 39, seq(γ; σ a , n)(k) ⊳ set a seq(γ; σ ′ a , n)(k) for all k.

Below, multi strategic game are embedded into ndbr multi strategic games. The corresponding ndbr multi strategic games always has an ndbr equilibrium, which is interpreted as multi strategic games always having an nd equilibrium. However, the embedding is not the only relevant one. It is intended to be a simple one. More subtle embeddings can yield to stronger results of nd equilibrium existence.

Lemma 42 Let g = S, (P n ) n∈V be a multi strategic game. For each agent a, assume that his preference over outcomes ⊳ a are strict partial orders, i.e. irreflexive and transitive. For each agent a and each γ in Σ -a , the following defines an element of Σ a .

BR a (γ) ∆ = i∈I BR n a (γ)
Where

BR n a (γ) ∆ = {s n | s ∈ S a ∧ ∀s ′ ∈ S a , ¬(seq(γ; s, n) ⊳ f ct a seq(γ; s ′ , n))}
The object (S n a ) n∈V a∈A , (BR a ) a∈A is an ndbr multi strategic game, and it has an ndbr equilibrium. Proof First prove that BR n a (γ) is non-empty: the set of the seq(γ; s, n), when s ranges over S a , is finite and non-empty. So at least one of the seq(γ; s, n) is maximal with respect to ⊳ f ct a which is a strict partial order by lemma 40. Second, assume that γ ⊆ δ for γ and δ in Σ -a and prove BR n a (γ) ⊆ BR n a (δ): let c be in BR n a (γ). By definition, c = s n for some strategy s in S a such that ¬(seq(γ; s, n) ⊳ f ct a seq(γ; s ′ , n)) for all s ′ in S a . So ¬(seq(δ; s, n) ⊳ f ct a seq(δ; s ′ , n)) for all s ′ in S a , by contraposition of lemma 41. So c belongs to BR n a (δ). Therefore, the ndbr multi strategic game has an ndbr equilibrium by lemma 21.

In the lemma above, the definition of BR says that at a given node and in a given context (other agents have chosen their nd strategies), an agent dismisses any of its options that induces a sequence worse than a sequence induced by some other option. Since the result above is constructive, it provides an algorithm for finding an nd equilibrium. An example is given below. The game involves two agents, namely vertical and horizontal. Agent vertical chooses the rows and is rewarded with the first figures given by the payoff functions. In the beginning, all agents consider all of their options. At the bottom node, only agent horizontal has an actual decision to take. If he chooses right, he gets an infinite sequence of 0. (vertical gets an infinite sequence of 3, but horizontal does not take it into account.) If he chooses left, he gets an infinite sequence of (non-zero) positive numbers whatever vertical's strategy may be, which is better than 0 at any stage of the sequence. So horizontal dismisses his right strategy at the bottom node, as depicted below. Since sequential graph games can be embedded into multi strategic games, lemma 26 also provides a notion of global nd equilibrium for sequential graph games, with the guarantee of equilibrium existence. However, it is also possible to define more subtle notions of equilibrium with this guarantee.

Conclusion

This paper introduces the notion of abstract strategic game, which is a natural and minimalist abstraction of traditional strategic games with real-valued payoff functions. It also defines the notion of multi strategic game which is a generalisation of both abstract strategic games and sequential graph multi strategic games can therefore model decision-making problems that are modelled by either strategic games or sequential graph/tree games. Since these new games can express both sequential and simultaneous decision-making within the same game, they can also model more complex decision-making problems. The paper also defines non deterministic best response multi strategic games. While somewhat more abstract, they are structurally similar to multi strategic games: Cartesian product and graph-like structure. Via a pre-fixed point result that is also proved in the paper, existence of ndbr equilibrium is guaranteed for ndbr multi strategic games (under some sufficient condition). Instantiating this result with (more) concrete best response functions provides different notions of non deterministic equilibrium for multi strategic games. A few examples show the effectiveness of the approach, in terms of numerical result as well as algorithmic complexity (polynomial and low). This approach is discrete and static, so it lies between Nash's probabilistic approach and the CP an BR approach.

  Definition 35 (non deterministic strategies and profiles) Let S, (P n ) n∈V be a multi strategic game. Let Σ n a ∆ = P(S n a ) -{∅} be the set of local nd strategies of agent a at node n. Let Σ a ∆ = n∈V Σ n a be the set of nd strategies of agent a (accounting for choices at all nodes). Let Σ ∆ = a∈A Σ a be the set of nd strategy profiles. Also, let Σ n ∆

  vertical considers the top-left node. If he chooses his bottom strategy, the induced sequence involves only 0 and 1. If he choose his top strategy, the induced sequence involves only numbers that are equal to or greater than 2, which is better. So vertical dismisses his top strategy at the top-left node node, as depicted below. horizontal considers the top-right node. If he chooses his left strategy, the induced sequence involves only 1 and 2. If he choose his right strategy, the induced sequence involves only 3 and 4, which is better. So agent horizontal dismisses his left strategy at the top-right node, as depicted below. vertical dismisses one of his strategy at the top-right node, which yields the global nd equilibrium below. Said otherwise, for each agent, fore each node, the agent cannot get better sequence by changing his strategy.