## 1 Introduction  
Earth observation satellites capture a vast number of images of the Earth's surface every day. These images are delivered to end-users who have made observation requests for several purposes such as monitoring critical areas affected by natural disasters or crises, observing infrastructures, monitoring the environment, etc. The observation request process operates in the following manner. First, users submit their observation requests to the main mission center. The mission center then computes observation plans which are transmitted to the satellites when they overly a ground control station. Subsequently, each satellite captures the requested images and transmits the collected data when it passes over a ground reception station. The satellites we consider in this work are on low Earth orbit and complete around 16 orbits per day, which allows them to pass over several Earth areas at different times every day. In order to improve the capability to deliver images as early as possible after requests are formulated, one can rely on constellations of Earth observation satellites that are currently deployed. Constellations also offer the possibility for users to express more complex requests. An example of such a complex request is a _periodic request_, that consists in observing an area of interest at regularly spaced dates. Generally, the number of posted requests on a given time horizon is too large to satisfy them all. Therefore, the main mission center has to select which requests to perform for the upcoming time horizon, for instance using manually defined prioritization rules. As such a selection process does not offer guarantees for users with regards to the satisfaction of their requests, Earth observation satellite constellations' managers now propose a new observation paradigm, namely, _exclusivity orbit slots_ booking. Whenever usersbuy exclusive orbit slots of a satellite, they can exploit this satellite during the associated time windows using their own ground stations. This allows users to send observation plans to satellites and collect the observations realized during the orbit slots. In this respect, from the point of view of the operator of an Earth observation satellite constellation, we consider the following problem. The goal is to attribute ownership of some orbit portions to several clients. Each client has some points of interest (POIs) to acquire at some frequency, e.g., capture L'Aquila city every 2 h for 6 months. Since several satellites may capture the very same point on Earth around the requested observation times, several possible bundles of orbit slots are specified by each client, together with a preference for some bundles depending on the quality of the sequence of orbit slots, e.g., based on the POI viewing angle provided by each slot. Moreover, as several clients may be interested in very close POIs, several requested orbit slots may overlap. Each orbit slot in this category can be either allocated to a single client or divided between clients. These situations can be captured by the models we propose in this article. More precisely, we consider a problem of allocation of conflicting bundles of items constrained by item chaining (to allocate to each agent a chain of successive items). The chaining constraint is captured by using, for each agent, an edge-weighted directed acyclic graph (DAG) representing all the valid bundles (i.e., paths) of items for the agent, where the quality of a bundle is represented by additive edge weights. Then, conflicting bundles cannot be allocated at the same time and have to be handled so that each agent obtains one conflict-free path in its graph. Such a setting occurs in application domains such as network function virtualization (NFV), where users request allocating directed graphs of services into a shared networked infrastructure [1].