A quest for a fair schedule: The Young Physicists' Tournament

The Young Physicists Tournament is an established team-oriented scientific competition between high school students from 37 countries on 5 continents. The competition consists of scientific discussions called Fights. Three or four teams participate in each Fight, each of whom presents a problem while rotating the roles of Presenter, Opponent, Reviewer, and Observer among them. The rules of a few countries require that each team announce in advance 3 problems they will present at the national tournament. The task of the organizers is to choose the composition of Fights in such a way that each team presents each of its chosen problems exactly once and within a single Fight no problem is presented more than once. Besides formalizing these feasibility conditions, in this paper we formulate several additional fairness conditions for tournament schedules. We show that the fulfillment of some of them can be ensured by constructing suitable edge colorings in bipartite graphs. To find fair schedules, we propose integer linear programs and test them on real as well as randomly generated data.


Introduction
Teams of high school students have been competing annually at the International Young Physicists Tournament (IYPT for short), sometimes referred to as Physics World Cup, since 1988. Each year the international jury publishes a set of 17 problems. In the preparation phase that takes several months, teams can use any resources they can find to solve the problems theoretically and/or experimentally and to prepare a carefully polished presentation of the results they obtain. The competition culminates in regional, national, and international tournaments that are organized in several rounds of small scientific workshops, called Fights. During a Fight, students practice how to lead scientific discussion, ask questions and evaluate the work of their opponents by taking the roles of the Presenter, the Opponent, and the Reviewer. Detailed information about the exact rules, schedule, past problems, etc., can be found on the international webpage http://iypt.org and on the webpages of national committees.
In the international finals, a team can be challenged to present a solution of any of the 17 published problems, but for their national and regional tournaments, each of the participating 37 countries can set the rules on their own. In several countries (Austria, Germany, Slovakia, Switzerland), a local tournament consists of three rounds and each team presents exactly 3 problems that were chosen by it in advance.
In Austria, the Opponent may challenge the Reporter on any of its chosen 3 problems that the Reporter team has not presented before. If possible, the Opponent must challenge a problem which has not already been presented in the same Fight. In other countries a schedule of Fights is prepared by the organizers who sometimes try to fulfill some additional criteria with this schedule. The German rules say explicitly that the schedule has to take into account the following criteria, with decreasing priority: (1) no two teams from the same school (center) compete within one Fight, (2) no team has the same Opponent more than once, (3) when possible, each team competes with 6 different teams in its 3 Fights in the tournament.
These rules demonstrate that besides guaranteeing the fulfillment of the necessary criteria, the organizers strive to create comparable conditions for all the participants, so as they feel that the competition is fair. The first aim of this paper is to formally define the necessary (feasibility) constraints for schedules of an IYPT tournament. Then we formulate several fairness conditions, proposed by the organizers of local tournaments. On the theoretical side, we draw a connection between feasible and fair schedules and edge colorings of graphs. On the practical side and to construct fair schedules we propose integer linear programs and test them on real and randomly generated data.

Related work
Scheduling problems appear in real life, often connected with the construction of timetables at schools or schedules of sports matches. They are also a popular research topic in Mathematics and Computer Science. Many variants of scheduling problems are difficult to solve in practice even for small instances.
Fairness in connection with scheduling appears in different contexts. Here we review progress on the study of fair schedules in the three most relevant fields to our study: work shifts, timetables, and sports tournaments. Finally, we argue why student competitions should become a fourth point on the list of practical scenarios where the computation of a fair schedule is essential.
Work shifts. The shift scheduling problem involves determining the number of employees to be assigned to each shift and specifying the timing of their relief and breaks, while minimizing the total staffing cost and the number of employees needed (Edie, 1954;Aykin, 1996). Recent advances on the topic move into the direction of fairness. Stolletz & Brunner (2012) minimize the paid out hours under the restrictions given by the labor agreement, and, subject to this, they also integrate the preferences of laborers and fairness aspects into the scheduling model. Bruni & Detti (2014) construct a flexible MIP framework to satisfy all service requirements and contractual agreements, while respecting workers preferences about workload balancing.

Timetables.
A widespread application of timetable design is creating a timetable for students and teachers in a school, so that it satisfies as many wishes as possible while guaranteeing that all demands regarding subjects, rooms, and working hours are satisfied. The EURO Working Group on Automated Timetabling (2019) maintains a constantly updated list of research papers on educational timetabling. Automated timetabling has various applications outside schools as well (Schaerf, 1999). In a recent paper, Vangerven et al.
(2018) construct a schedule for a conference with parallel sessions that, based on preferences of participants, maximizes total attendance and minimizes session hopping.
Sports tournaments. Fairness plays an essential role in sports tournament scheduling. In spite of the relevance of good game schedules, very few professional leagues have adopted optimization models and software to date (Rasmussen, 2008;Nurmi et al., 2010;Goossens & Spieksma, 2012). One of these exceptions is the national soccer tournament in Brazil. Urrutia & Ribeiro (2009) designed an ILP-based system, which was used for the first time in 2009 as the official scheduler to build the fixtures of the first and second divisions as well. Their solution minimizes the number of breaks and maximizes the number of games that open TV channels could broadcast. In works dealing with the scheduling of round robin tournaments, fairness criteria appear in the form of balancing the rest time after the most recent game of two opposing teams or balancing the difference between the number of games played by any two teams at any point in the schedule (Suksompong, 2016;Atan & Ç avdaroǧlu, 2018).
Student competitions. IYPT has its counterpart in mathematics, the International Tournament of Young Mathematicians (ITYM), with a similar structure of the tournament with teams playing the roles of the Reporter, Opponent and Reviewer. Another branch of student competitions organized in rounds in which teams take turns are debating tournaments (Neumann & Wiese, 2016;Bradbury et al., 2017). The World Universities Debating Championship is the world's largest debating tournament and one of the largest annual international student events in the world. At their events, the British Parliamentary format is used, in which four teams participate in each round (The World Universities Debating Championships, 2014). Two teams form the "government" and two the "opposition" in each debate room, and the order of speeches assigns a different role to each of the teams. Such competitions promote democratic education and they are shown to significantly enhance student performance in the subject, hence they are currently on the rise (Spies-Butcher, 2007;Pang et al., 2018).
Compared to sports tournaments, scheduling competitions for students is an admittedly much less profitable, but arguably more noble branch of tournament scheduling. Up to our knowledge, no formal scheduling model for organizing student competitions has been reported on yet. In this work, we make an attempt to demonstrate how students' competitions can be organized with the aid of integer programming, which not only automatizes the cumbersome task of scheduling, but also calculates a solution that is provably more fair for the participating students.

Outline
In Section 2 we outline the rules and organization of the IYPT in more detail and in Section 3 we formally introduce the studied problem and the related notions. Section 4 is devoted to a discussion of how the edge coloring of bipartite graphs leads to a feasible simple schedule and to schedules that give each team 3 different order positions in its 3 Fights.
We formulate several fairness criteria for schedules; as far as we know, fairness criteria similar to ours have not been considered before in scheduling problems. In Section 5 we formulate integer linear programs to find fair schedules fulfilling alternative-weaker and stronger-forms of fairness. Then, in Section 6 we report on the results we obtained when the designed ILPs were applied to real data: we used the application sets from regional tournaments in Slovakia in recent years. We also randomly generated sets of applications that have some features similar to the expected situations and performed numerical tests on these random data.

Background
According to the rules of the Austrian, German, Slovak, and Swiss regional and national tournaments, each team applying for participation chooses a subset of exactly 3 problems from the published set of 17 problems. This subset is called the team's portfolio and it contains the 3 problems it will present at the tournament. A set of portfolios may look similar to the one presented in Table 1, which is a real set of portfolios from the regional tournament Bratislava 2018. In all examples in this paper, the teams are anonymized by having been given animal names. To indicate which teams are from the same school we give them the name of the same animal and distinguish only the final digit.  The assignment of teams to rooms in the rounds comes also with the assignment of the problems from their portfolios they will be presenting. Suppose that the set of teams in a room is A, B, C and assume that these teams have been assigned problems p A , p B , and p C , respectively. In the first stage of the Fight, team A is the Reporter; it presents a report on problem p A . Team B is the Opponent.
After the presentation of the Reporter, it presents an evaluation of the presentation, stressing its pros and cons. Afterwards the third team C, the Reviewer, can ask questions to both other teams and then it presents an overview of the performance of the Opponent. The stage ends by the Reporter presenting some concluding remarks. Finally the jury may ask some short questions to all three active teams. After a short break, another stage with the same structure begins, but the roles of teams are rotated. If the total number of teams is not divisible by three or if the organizers have some other issues to deal with (e.g., there are not enough rooms on the premises where the tournament takes place, or the number of available qualified jurors is small, etc.), the number of teams in a room may be 4. In such a Fight, the 4 teams exchange their roles cyclically, with one of them playing the role of the Observer, which is the team not participating actively.
Given the set of portfolios, an important task of the organizers is to prepare a schedule of the tournament. A schedule is an assignment of teams to rooms in each round together with an assignment of problems to be presented by them, so that the following conditions are observed: (1) Each team presents exactly the 3 problems from its portfolio.
(2) No problem is presented more than once during the same Fight.
(3) In each Fight the correct number of problems is presented.
(4) In each Fight a correct ordering of Presenters is defined.
A schedule fulfilling conditions (1)-(4) is said to be feasible. In Section 4 we will see that feasible schedules are guaranteed to exist under very mild conditions. Finally, we explain the most striking fairness concern for schedules on an intuitive level and by an example. Assume that teams t i and t j are in the same Fight and team t i presents problem p. If team t j has problem p in its portfolio too, then it has either presented p before in a previous round or will present it in some later round. In the former case, team t j had prepared its own presentation for p, moreover, it has already heard the comments of its own Opponent and Reviewer on problem p, so now team t j is likely to be better prepared for the tasks of the Opponent as well as of the Reviewer. In the latter case, team t j has a chance to update its own presentation based on what it has heard during the presentation of problem p by team t i and also be better prepared for answering the challenges of its future Opponent and Reviewer on problem p. The organizers wish to avoid that such injustice happens.
We say that a feasible schedule is fair if the following condition for each pair of teams t i , t j is fulfilled: If teams t i , t j are in the same Fight at any time during the competition and team t i presents problem p in this Fight, then problem p is not in the portfolio of team t j .
In reality, it has not always been the case that the used schedules fulfilled the fairness requirements. This means that Lions had seen two problems from its portfolio, namely problems 4 and 9, before it had to present them. This is clearly unfair, as Lions had a great advantage to other teams.  For the set of portfolios in this regional tournament a fair schedule exists, and it is presented in Table 3. In 2018 the organizers were not able to find it with paper and pencil. Notice however that the schedule in Table 3 is also unbalanced in a milder way. Team Sharks1 has to oppose or review 6 different problems during the tournament, namely problems 2, 3, 7, 9, 10, and 17. By contrast, team Turtles1 opposes or reviews only four problems: 3, 4, 5, and 6. Clearly, this gives Turtles1 another form of advantage to team Sharks1. We will say that a feasible schedule is strongly fair if each team deals with each problem (in any role) during the tournament at most once.

Notation and optimality concepts
We start this section with introducing the notation used thorough this paper and formalizing the feasibility requirements for a schedule. In Section 3.1, we define three optional features of feasible schedules, which can be enforced individually and on the top of feasibility, if the decision maker finds them desirable. Then we proceed to formalize the three degrees of fairness in Section 3.2.
T = {t 1 , . . . , t n } is a set of n teams, P = {p 1 , . . . , p m } is a set of m problems. To simplify notation, problems will sometimes be denoted by integers; while capital letters A, B, C or D as notation for teams will be reserved for their specific order within a Fight. Each team t applies with a set of exactly 3 problems from set P ; these three problems will be called the portfolio of team t and denoted by P (t).
A set of portfolios is an n-tuple of portfolios (P (t 1 ), P (t 2 ), . . . , P (t n )) and it will be denoted by Π.
If S ⊆ T is given, we denote by P (S) the set of problems that appear in the portfolio of at least one team from S, thus P (S) = ∪ t∈S {p ∈ P (t)}. If p / ∈ P (t) for team t ∈ T and problem p ∈ P we say that team t avoids problem p.
There are s rooms R = {r 1 , . . . , r s }. The set of rooms is partitioned into two subsets R 3 and R 4 . If r ∈ R 3 then room r is a 3-room (i.e., exactly three teams perform a Fight in r); if r ∈ R 4 then room r is a 4-room (a Fight of 4 teams). The size of room r is denoted by size(r). Obviously, size(r) = 3 for r ∈ R 3 and size(r) = 4 if r ∈ R 4 . There are 3 rounds, and a Fight is uniquely defined by the pair (j, r), where j is one of these rounds and r is a room.
For an integer k the notation [k] represents the set {1, 2, . . . , k}. The degree of a vertex v in a graph of vertices V, we denote by G(V ) the graph induced by V , i.e., consisting of V , the edges incident to vertices in V , and their other end vertices.
Now we formally define a feasible schedule and formulate fairness conditions.
} are mappings of teams to problems, rooms and order set {A, B, C, D}, respectively, such that for round j and each pair of different teams t, t ′ ∈ T ; (iii) |{t ∈ T : ρ j (t) = r}| = size(r) for each round j and each room r ∈ R; The interpretation of the mappings in Definition 1 is such that π j (t) denotes the problem presented by team t in round j, ρ j (t) denotes the room to which team t is assigned in round j, and ω j (t) corresponds to the order of team t in round j. Condition (i) then ensures that each team presents exactly the problems from its portfolio during the tournament and condition (ii) means that in no Fight the same problem is presented more than once; condition (iii) ensures the correct number of teams for each room, i.e., this should be equal to the size of the respective room, and finally, condition (iv) makes sure that the order of teams within any Fight is correctly determined. These points are analogous to the ones listed in Section 2.

Refinement of feasible schedules
To avoid cooperation of teams from the same school, a schedule might be required to prevent that two teams from the same school participate in the same Fight. In the following definition one partition set corresponds to the set of teams from the same school.
Definition 2. Suppose that the set of teams T is partitioned into disjoint subsets T 1 , T 2 , . . . , T Λ . A schedule is non-cooperative if it is feasible and whenever t and t ′ belong to the same partition subset.
In Section 4.1 we deal with schedules that keep the composition of each room fixed in all three rounds.
Such schedules will be called simple, a property formally expressed in Definition 3. The drawback of a simple schedule is that the students can only meet and exchange ideas with a very small subset of other participants. Thus, if possible, simple schedules should be avoided in reality. In this paper we only use this concept to ensure that a feasible schedule always exists if some very mild conditions are fulfilled.
Finally, the following definition ensures that no team has the same ordering position (A, B, C, D) in two Fights it participates in.

Properties of fair schedules
The most striking problem with feasible schedules is that certain teams have considerable advantage to others, if they repeatedly encounter the problems in their own portfolio. In the following, we define 3 degrees of fairness based on restrictions applied to what presentations a team can witness. The condition that no team can see a presentation of a problem in its portfolio by some other team is captured by Definition 5.
Definition 5. A schedule is fair if it is feasible and the following condition holds for all rounds j ∈ [3]: if ρ j (t) = ρ j (t ′ ) for two different teams t, t ′ ∈ T and π j (t) = p then p / ∈ P (t ′ ).
The following definition is a weaker form of Definition 5 in that it allows a team to see a presentation of a problem in its portfolio only in the final round.
Definition 6. A schedule is weakly fair if it is feasible and condition (1) holds for rounds j = 1, 2.
To define strongly fair schedules, let us introduce the following notation. Let P (j, ρ j (t)) = {p ∈ P : there exists a team t ′ ∈ T such that ρ j (t) = ρ j (t ′ ) and π j (t ′ ) = p} be the set of problems that team t deals with in round j, in any role (Presenter, Opponent, Reviewer, or, in case of 4-rooms, an Observer).
In other words, Definition 7 means that no two problems a team t deals with during the tournament are identical. In particular, if p ∈ P (t) and team t can see the presentation of problem p in some Fight, then this implies that team t deals with p at least twice (the other occasion is when t presents p) and hence condition (2) is violated for team t. Therefore we have the following relation between fairness notions.
Observation 1. Each strongly fair schedule is fair and each fair schedule is weakly fair.

Feasible solutions via graph coloring
In this section we utilize combinatorial tools to derive positive results for feasible schedules. With the help of edge colorings and basic theorems in matching theory, we characterize the existence of simple solutions in Section 4.1, and give a constructive algorithm to compute an order fair schedule in Section 4.2.

Simple solutions
The official rules of the IYPT prefer 3-team Fights and admit 4-team Fights only if the total number of teams n is not divisible by 3. We will deal with the cases when n modulo 3 is equal to 0, 1, and 2 separately, and assume that |R 4 | = 0, 1, and 2, respectively.
For a set of portfolios Π and a subset of teams S ⊆ T we shall denote by G(S) the bipartite graph G(S) = (S ∪ P (S), E S ) such that the pair {t, p} ∈ E S if and only if t ∈ S and p ∈ P (t). Figure 1 illustrates the graph G(T ) for the instance from Table 1.
p 1 p 2 p 3 p 4 p 5 p 6 p 7 p 8 p 9 p 10 p 11 p 12 p 13 p 14 p 15 p 16 p 17  Table 1, represented by the bipartite graph G(T ) = (S ∪ P (T ), E T ). The team names are abbreviated to their first letter and team number, e.g., S1 denotes Sharks1.
Theorem 1. If the number of teams n is divisible by 3, then a simple schedule exists.
Proof. Partition the set of teams into 3-rooms arbitrarily. The only thing to ensure a feasible schedule is to decide for each room who will present which problem in which round. Fix a room r and assume that the three teams assigned to the three Fights to be performed in r are T (r) = {t 1 , t 2 , t 3 }. Notice that in the bipartite graph G(T (r)) the maximum degree of a vertex is ∆(G(T (r))) = 3. This is because the degrees of vertices in T (r) are exactly 3 (the size of the portfolio of each team is 3) and the degrees of vertices in P (T (r)) are at most 3. Therefore, by König's theorem (König (1916), see also Diestel (2005), Proposition 5.3.1.), G(T (r)) admits an edge coloring by 3 colors. One color class corresponds to the assignment of problems to be presented by teams in one stage of the Fight.
If n is not divisible by 3, then we need one or two rooms with 4 teams. Now we only need to ensure that the set of portfolios contains a suitable set of 4 teams (or two disjoint quadruples of teams) that can be organized in the same room during the tournament, as the rest of teams can be dealt with according to the previous theorem. Notice that the assignment of problems to be presented in the three rounds in a 4-room containing the set of teams S again corresponds to a 3-coloring of graph G(S). Again, by König's theorem, this is ensured if ∆(G(S)) = 3. We will call a set of teams S ⊆ T with |S| = 4 fine if ∆(G(S)) = 3. Now we discuss the case of one 4-room only.
Theorem 2. A fine set of teams exists if and only if each problem p ∈ P is avoided by at least one team.
Proof. Let t 1 ∈ T be an arbitrary team and let P (t 1 ) = {p 1 , p 2 , p 3 }. Let team t 2 be any team that avoids problem p 1 . Now we distinguish three cases. If |P ({t 1 , t 2 })| = 6 then the quadruple t 1 , t 2 , t 3 , t 4 is fine for any two teams t 3 , t 4 . If |P ({t 1 , t 2 })| = 5, assume w.l.o.g. that P (t 1 ) ∩ P (t 2 ) = {p 2 }. Then choose any team t 3 that avoids problem p 2 and add an arbitrary team t 4 . Finally, if |P ({t 1 , t 2 })| = 4, then P (t 1 ) ∩ P (t 2 ) = {p 2 , p 3 }. To get a fine quadruple, choose any team t 3 that avoids p 2 . If t 3 happens to avoid p 3 too, choose t 4 arbitrarily, otherwise choose t 4 that avoids problem p 3 . The other direction is straightforward: each problem adjacent to any of the four teams in the fine set S is avoided by at least one of the teams in S, because ∆(G(S)) = 3. All other problems are avoided by all teams in S.
Finally, we turn to the case of two 4-rooms. A necessary and sufficient condition for the existence of two disjoint fine sets of teams follows from Corollary 4.2. of Keszegh (2019). To be able to formulate this assertion, let us call a set Π of n portfolios special if it has the following structure: there are n − 3 portfolios of the form {p i , p j , p k } for some i, j, k ∈ [m] and the remaining 3 portfolios are of the form {p i , q 1 , q 2 }, {p j , q 3 , q 4 }, and {p k , q 5 , q 6 }, where q u / ∈ {p i , p j , p k } for each u ∈ [6]. A special set of portfolios is illustrated by Figure 2.
q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8 q 9 q 10 q 11 q 12 q 13 q 14 p i p j p k (i) each problem is avoided by at least two teams; (ii) Π is not special.
In regional tournaments, the organizers might decide to use more 4-rooms, however, we do not have a necessary and sufficient condition for the existence of a feasible schedule in this case. So we finish this section with an open problem in graph theory.
Problem 1. Given an integer k and a bipartite graph G = (U ∪ V, E) such that |U | ≥ 4k and deg(u) = 3 for each u ∈ U . What is a necessary and sufficient condition for the existence of at least k disjoint subsets U 1 , U 2 , . . . , U k of U such that |U i | = 4 and ∆(G(U i )) ≤ 3 for each i ∈ [k]?

Order fair solutions
Order fairness requires that no team takes up the same ordering position in any two of its Fights. In the case of 3-rooms only, this means that each team will present one problem as the first Reporter in the Fight, one as the second Reporter, and the third problem as the third Reporter. This corresponds to roles A, B, and C from Section 2. We now prove that order fairness is not a stricter criterion than feasibility.
Theorem 4. Each feasible schedule can be transformed into an order fair schedule in polynomial time.

Proof.
A feasible schedule is given by the assignments P, R, and O. Our task is, based on the pair P We propose a simple algorithm to construct an edge coloring respecting our conditions. In the first step, we calculate a matching M D covering all vertices f ∈ F with deg(f ) = 4. Such a matching is guaranteed to exist, because any vertex set of 4-Fights fulfills the Hall-criterion (Hall, 1935). We know color D, and remove these edges from the edge set A. Notice that the maximum degree in the remainder of H is 3, and each f ∈ F now has deg(f ) = 3. By König's theorem, an edge coloring with 3 colors exists in this graph, and it can be found efficiently, by iteratively coloring all edges of a matching covering all vertices in F with a fixed color (König, 1916). This coloring defines the roles A, B, and C so that each Fight will have exactly one team in each of these three roles.
This algorithm computes a maximum matching for each of the four roles. Computing such a matching is of computational complexity O( |T ∪ F ||A|) (Hopcroft & Karp, 1973). Since the graph is of bounded degree, there are at most as many Fights as teams, and there is a constant number of matchings to be calculated, the computational complexity reduces to O(|T | 1.5 ).
We now demonstrate our algorithm on the Example from Table 3, which contains a fair, but not order fair schedule for the real data from the tournament Bratislava 2018. Figure 3 depicts the bipartite graph H(P, R) built to this fair schedule, and

Integer program for a fair schedule
In this section we present two families of integer linear programs to find fair schedules. Model 1 could be described as a problem-based variant. It is more straightforward, but it leads to programs with larger size that are also more time consuming to solve. Therefore we developed Model 2, a more compact version based on portfolios, which is presented in Section 5.2.

Model 1
We assume that the teams' portfolios are given by matrix C where its element c iℓ = 1 if problem p ℓ ∈ P (t i ), otherwise c iℓ = 0. Let us introduce binary variables with the following interpretation.  A Fight is uniquely defined by the pair of indices j and k. A feasible schedule is defined by the following system of equations and inequalities: x ijkℓ ≤ c iℓ for each i, j, k, ℓ x ijkℓ = 4 for each j and for each r k ∈ R 4 (7) n i=1 x ijkℓ ≤ 1 for each j, each k, and for each ℓ Let us argue that system (3)-(8) ensures that its solution corresponds to a feasible schedule.
(3): Each team presents only problems from its portfolio.
(4): Each team presents all the problems from its portfolio.
(5): Each team presents in each round exactly one problem.
(6) and (7): In each round and in each room r k , the number of presented problems is equal to size(r k ).
(8): In each round and each room, each problem is presented at most once.
We remark that constraint (3) could be omitted if constraint (4) were simply changed to be an equality.
However, we opted to keep the two separate constraints, because (3) immediately sets a large set of our variables to zero, which can reduce the computation time.
Let us now recall the fairness condition from Definition 5. A feasible schedule is fair if the following holds: If team t α is in some round in a room with team t i who presents problem p ℓ then p ℓ / ∈ P (t α ).
This can be expressed by the following inequality: x αjkw + c αℓ ≤ 2 for each k, ℓ and each pair i = α Let us see how (9) ensures fairness. Assume that team t i presents problem p ℓ in the Fight that takes place in room r k in round j. This means that x ijkℓ = 1. Team t α is assigned to the same Fight if and only if it presents some problem in room r k in round j; this holds if and only if the second term on the left-hand-side of inequality (9) is equal to 1. Thus, this inequality implies c αℓ = 0, i.e., problem p ℓ is not in the portfolio of team t α . This discussion implies the following assertion. Since in weakly fair schedules a team is not allowed a to see a presentation of a problem in its portfolio except in the last round, we immediately have the following assertion.
Theorem 6. Weakly fair schedules for IYPT correspond to the solutions of the integer linear program consisting of the feasibility constraints (3)-(8) and the fairness constraint (9) formulated for the first two rounds j = 1, 2.
Let us now consider the strong fairness condition. Recall that a feasible schedule is strongly fair if no team t deals with a problem p more than once during the tournament. To formulate this condition, we introduce another set of non-negative variables: Inequalities (10) for each j ∈ [3] and each k ∈ [s] ensure that y ijkℓ ≥ 1 if team t i can see problem p ℓ during its presentation in round j in room r k : To see this, notice that the first sum on the right-hand side is equal to 1 if team t i presents some problem in round j in room r k , which is equivalent to team t i being in this room in the respective round, otherwise it is equal to 0. The second sum is equal to 1 if problem p ℓ is presented in round j in room r k by some team t α , otherwise it is equal to 0. The inequality ensuring strong fairness is: 3 j=1 s k=1 y ijkℓ ≤ 1 for each i and each ℓ.
Theorem 7. Strongly fair schedules for IYPT correspond to solutions of the integer linear program consisting of the feasibility constraints (3)-(8) and strong fairness constraints (10) and (11).
We prove in Observation 2 that the ILP formulation of strong fairness implies the ILP formulation of fairness.
Proof. Let us assume that there exist two teams t i , t α , round j, room r k and problem p ℓ that violate inequality (9), i.e., the three terms are equal to 1: x αjkℓ = 1 and m w=1 x ijkw = 1 and c iℓ = 1.
Then variable y ijkℓ ≥ 1, as the two sums on the right-hand side are equal to 1: x βjkℓ − 1.
Further, as c iℓ = 1, inequality (4) implies that there exist j ′ ∈ [3] and k ′ ∈ [s] such that x ij ′ k ′ ℓ = 1 and this in turn implies y ij ′ k ′ ℓ ≥ 1, because in the inequality x βj ′ k ′ ℓ − 1 the two sums on the right-hand side are both equal to 1. Thus inequality (10) for team t i and problem p ℓ is violated. This means that if a feasible schedule does not fulfill inequality (9) then it cannot fulfill inequalities (10) and (11) at the same time.
The non-cooperativeness condition can be ensured easily.
Notice that Model 1 is not designed to capture the roles A, B, C, D in a Fight, and thus, order fairness cannot be described in it. By adding a fifth index representing the roles to each variable x ijkℓ , we could incorporate them into the model, but this would increase the number of variables and also require adding more inequalities to ensure the correct interpretation and so lead to increased computation times.
However, as our algorithm from Section 4.2 translates any feasible schedule into an order fair schedule, enforcing order fairness directly in the ILP model would be superfluous.

Model 2
Now we assume that the set of portfolios Π is given in the form of triples, where P (t i ) = (p i 1 , p i 2 , p i 3 ) denotes the three problems in the portfolio of team t i . We denote by ℓ(i, q) the index of the problem that is in the q th position in the portfolio of team t i . Further, we construct for each ℓ ∈ [m] the list T (ℓ) of pairs (i, q) such that problem p ℓ is the q th problem in the portfolio of team t i , i.e., Let us introduce binary variables with the following interpretation.
x ijkq =    1 if team t i presents the q th problem from its portfolio in round j in room r k 0 otherwise.
A feasible schedule is defined by the following system of equations and inequalities: 3 j=1 s k=1 x ijkq = 1 for each team t i and for each q ∈ [3] (13) s k=1 3 q=1 x ijkq = 1 for each team t i and for each round j (14) 3 q=1 x ijkq = 3 for each round j and for each room 3 q=1 x ijkq = 4 for each round j and for each room r k ∈ R 4 (16) (i,q)∈T (ℓ) x ijkq ≤ 1 for each round j, each room r k and for each problem p ℓ (17) Solutions of system (13)-(17) correspond to feasible schedules, because these equations and inequalities mean the following.
(13): Each team presents each problem from its portfolio exactly once.
(14): Each team presents in each round exactly one problem.
(15) and (16): In each round and in each room r k the number of presented problems is equal to size(r k ).
(17): In each round and each room each problem is presented at most once.
Our fairness condition is analogous to inequality (9), the only difference being that now we do not need to sum over all problems, just over the problems in the portfolios of teams. Hence inequality (9) is replaced by inequality (18): x αjkw + c αℓ(i,q) ≤ 2 for each k ∈ [s], each q ∈ [3], and each pair i = α.
Theorem 9. Fair schedules for IYPT correspond to the solutions of the integer linear program consisting of the feasibility constraints (13)-(17) and the fairness constraint (18) formulated for each round j ∈ [3].
For weakly fair schedules inequality (18) is required only for j = 1, 2.
For strong fairness, we still need variables y ijkℓ for i ∈ [n], j ∈ [3], k ∈ [s] and ℓ ∈ [m] with inequality (11), but inequality (10) is replaced by Similarly as in Model 1, it can be shown that the strong fairness constraints (11) and (19) imply the fairness constraint (18).
Theorem 10. Strongly fair schedules for IYPT correspond to the solutions of the integer linear program consisting of the feasibility constraints (13)- (17), and inequalities (19) and (11).
Theorem 11. A schedule is non-cooperative if the inequality i∈T λ 3 q=1 x ijkq ≤ 1.

Computations
We now present our computational work on real and generated data in Sections 6.1 and 6.2, respectively.

Real data
The organizers of the two regional tournaments of the IYPT in Slovakia-Bratislava and Košiceprovided us with the sets of portfolios for the years 2018 and 2019. They also showed us the schedules, prepared by them for these regional tournaments. (Let us mention here that all schedules used in reality were non-cooperative, but none of them was fair. We even encountered a team that had seen presentations on two of its problems before it presented them-see team Lions 2018 in Table 2.) We attempted to compute schedules that are non-cooperative and fair. In our simulations we used the open source solver lpsolve (Berkelaar et al., 2007), version 5.5 under Java wrapper library. We kept the default parameter settings for integer and mixed integer problems. The solver was running on a desktop computer with the processor Intel (R) Core (TM) i5-2500 3.3 GHz and 6 GB RAM.
Summaries of the computations with real data for Model 1 and Model 2 are given in Tables 5 and 6, respectively. Columns contain the number of teams, the number of 3-rooms and 4-rooms, the number of variables and constraints in the constructed ILP, the computation time in seconds, and the degree of fairness, respectively. In all cases, with the exception of the 15 applications from the regional tournament Košice 2018, we were able to obtain a non-cooperative fair schedule within seconds. The problematic case was due to using three 4-rooms and only one 3-room for 15 teams. We set the parameter timeout for 10 and 5 minutes in Model 1 and Model 2, respectively, and the solver was not able to find a fair schedule within this time limit. However, we found a non-cooperative weakly fair solution for this case, and also a non-cooperative fair solution if the 15 teams were scheduled to fill up five 3-rooms.
Notice that the size of the generated ILP for Model 2 was approximately six times smaller (in terms of numbers of variables as well as constraints) than that in Model 1, but the time savings were much higher. Therefore in the subsequent numerical experiments we used Model 2 only. We remark that for the strong fairness criterion, Model 2 did not reach any conclusion within time limit of 5 minutes for any of these real instances.

Randomly generated data
We randomly generated sets of portfolios that resemble the situations that typically occur in practice.
The structure of the generated samples was derived from the structure of portfolio sets in recent years and from our knowledge of the situation in Physics education and schools in the respective regions.
Teams for the competition are nominated by schools and we assume that a 'big school nominates between 2 and 4 teams whilst a 'small school nominates 1 or 2 teams. Higher numbers were less probable.
In more detail, we set the probabilities that a big school nominates 2, 3, and 4 teams at 0.5, 0.3, and 0.2, respectively. For small schools, the probability of nominating one team was 0.75 and that of nominating 2 teams 0.25. Further, we assumed that not all problems are equally popular. We estimated that in the set of 17 published problems there are 8 problems with low popularity, 6 problems with medium popularity and 3 problems with high popularity. We assumed that a team chooses a problem of low popularity with probability µ, a problem of medium popularity with probability 2µ and a problem of high popularity with probability 4µ.
We generated 50 samples for region Bratislava and another 50 samples for region Košice. We assumed that in region Bratislava there are 3 big schools and 3 small schools, whilst in region Košice there are 2 big schools and 6 small schools. The number of teams n in the generated samples was between 9 and 15 for Bratislava and it was between 10 and 16 for Košice.
The results of computations of non-cooperative weakly fair, fair, and strongly fair schedules are summarized in Tables 7 and 8. The column labelled undecided shows the number and ratio of instances for which the solver stopped after 5 minutes due to the prescribed time-out without any result. Computation times are summarized separately for feasible and infeasible instances. Notice that we performed the computations of fair and strongly fair schedules even for instances where we already knew that a schedule fulfilling a weaker form of fairness does not exist so as to obtain a comparison of computation times.   The computations depicted in Tables 7 and 8 correspond to the choice of room sizes that follow the international rules. This means that 4-rooms are only used when necessary, hence the number of 4-rooms is 0, 1 or 2. However, sometimes the organizers of regional tournaments want to minimize the number of rooms used and prefer 4-rooms. A different composition of room sizes is possible in our case if n = 12, 15 or 16. The number of instances with such n among Bratislava-type data was 14 and among Košice-type data it was 21. Notice that for n = 12 and n = 16 a schedule that uses only 4-rooms is possible, for n = 15 one can use 3 rooms of size 4 and one 3-room. In this case chances of the existence of a fair schedule are much lower. For Bratislava region and non-cooperative weak fairness, 8 instances out of 14 were infeasible, for 3 of them the solver was not able to find an answer within 1 hour and only 3 instances admitted a weakly fair schedule; for one of them the answer was output after 19 minutes. The results for Košice region are given in Table 9. Notice that here we also used the time limit of 1 hour.  Table 9: Summary of computations with minimum number of rooms, randomly generated data, region Košice.

Conclusion
In this paper we studied the scheduling problem arising in the organization of regional competitions of the International Young Physicist Tournament. Based on considerations of organizers, we introduced novel fairness criteria for scheduling problems. To find fair schedules we proposed integer linear programs and applied them successfully to real portfolio sets from recent years and explored their behaviour on randomly generated data.
Our simulations revealed that if teams are allowed to choose their portfolios completely arbitrarily, then the chances of a non-cooperative fair schedule may be low. Let us therefore think about another approach. Suppose that instead of submitting a fixed portfolio, each team submits a preference ordering of the problems-perhaps it might even be allowed to label some problems as unacceptable. We seek a matching of teams to triples of problems, which enables a fair schedule, and is in a sense optimal. Several optimality criteria can be thought of, for example minimizing the position of the least preferred problem in the final portfolio of each team, or minimizing the weighted sum of ranks of assigned problems in the portfolio.
Notice that besides the graph-theoretical Problem 1 that we formulated in Section 4.1 we leave the theoretical complexity of the existence of a fair schedule open. Practically, in some cases it is easy to see why a fair schedule does not exist, e.g., if the portfolios are too similar to each other. The next theoretical step could be deriving some easily verifiable combinatorial certificate for unsolvable fair schedule instances.
We hope to have opened a new perspective on student competition scheduling with our work. Our ILP model seems to be useful for the preparation of fair schedules of regional tournaments that are consistent with the IYPT rules of at least four countries: Austria, Germany, Slovakia, and Switzerland. Furthermore, other competition schedules could potentially be automatized as well. A good starting point here is the analogous version of IYPT in mathematics, the International Tournament of Young Mathematicians.
By applying an ILP approach to the rules at The World Universities Debating Championship or other debating tournaments we could also potentially determine fair schedules for debate rooms.