Logique: résoudre des problèmes de partage équitable
Logique: résoudre des problèmes de partage équitable Objectif: partager une collection de façon équitable Matériel: 4 peluches ou poupées 8 bonbons (ou jetons qui représentent des bonbons) Consigne: « Voici des bonbons Il faut les partager avec les peluches Attention; il ne doit pas y avoir de jaloux
Le problème de partage équitable de ressources : modélisation
Le problème de partage équitable de ressources : modélisation et applications 1 Quelques applications concrètes du problème de partage 2 Les éléments d’un problème de partage La ressource Contraintes sur la ressource Préférences et expression compacte Le bien-être social Autres éléments 3 Problème de partage avec préférences
Partage équitable de biens indivisibles sous risque
Dans certains problèmes de partage équitable, la valeur des objets pour les agents peut être incertaine au moment où le partage est décidé Dans l’exemple du partage de la constellation de satellites, les conditions météorologiques sur la zone où l’observation doit avoir lieu sont in-certaines1 et peuvent dégrader l’utilité de
Numération: résoudre un problème de partage équitable
Numération: résoudre un problème de partage équitable Voici 3 pirates qui ont attaqué un bateau et ont des pièces d'or à se partager Chaque pirate doit en avoir autant que les autres (Vous pouvez donner des jetons ou des pièces à votre enfant pour représenter les pièces d'or et résoudre plusieurs fois le problème en changeant le
Analyse de sensibilité du problème du partage équitable
Analyse de sensibilit´e Le probleme du partage` ´equitable 2 Perturbation du profit d’un el´ ement quelconque´ Formulation du probleme perturb` ´e Resultats g´ en´ eraux´ D´etermination des limites de l’intervalle 3 Algorithme Une classe optimale unique Plusieurs classes optimales 4 Partie exp´erimentale Exemple Instances de la
Les situations de partage - Académie de Dijon
partir d'un problème de partage ou de groupement Remarque : Le travail de situation de partage est à envisager dès la grande section Idées directrices : Associer les problèmes de partage aux problèmes de groupement Vivre des situations pour donner du sens aux problèmes de partage Partager pour arriver à l’automatisation de la table
Résolution de problèmes Pistes pour les cycles 1 et 2
Exemple de situations de partage en CP/CE1 Situation du partage équitable de jetons dans des enveloppes (12 en 4; 21 en 3 ) : - réalisation effective par manipulation - procédure utilisant un dessin - réalisation à l ’aide de procédures mixtes : apparition de nombres et présence possible de jetons - procédure utilisant des nombres
SEQUENCE PEDAGOGIQUE GS : Le partage en parts égales
- essai de distribution par paquet de X éléments ( se souvenir de la donne choisie ) - estimer les cartes restantes pour effectuer la dernière donne - Comprendre pourquoi toutes les cartes ne pourront pas forcément être distribuées élimine le nombre de boutons correspondant 2 / jouer seul au jeu de la bataille Jeu des mosaïques
[PDF] Problème de pavés
[PDF] Probléme de physique
[PDF] Problème de Physique
[PDF] Problème de physique (mécanique classique)
[PDF] Problème de Physique 1ère S
[PDF] probleme de physique corrigé
[PDF] probleme de physique exercices
[PDF] problème de piscine
[PDF] probleme de piscine en forme de pavé
[PDF] Problème de placement de capitaux
[PDF] probleme de pliage de feuille
[PDF] problème de points sur ou en dehors du cercle
[PDF] Probleme de pourcentage
[PDF] problème de pourcentage
Le problème de partage équitable de ressources : modélisation et applications.
Sylvain Bouveret
Office National d"Études et de Recherches AérospatialesCentre National d"Études Spatiales
Institut de Recherche en Informatique de Toulouse
Responsables de thèse :
Jean-Michel LACHIVER, Jérôme LANG, Michel LEMAÎTRE.Séminaire I3 du laboratoire GREYC, Caen.
le 6 décembre 2005.IntroductionApplications Modélisation Préférences numériques Absence d"envie Travaux futurs
Qu"est-ce qu"un problème de partage?
Intuitivement, une ressource à partager entre plusieurs agents...2 / 55Problèmes de partage équitable de ressources
IntroductionApplications Modélisation Préférences numériques Absence d"envie Travaux futurs
Qu"est-ce qu"un problème de partage?
2 / 55Problèmes de partage équitable de ressources
IntroductionApplications Modélisation Préférences numériques Absence d"envie Travaux futurs
Une définition générique du problème de partage? Un problème de partagePest un problème d"optimisation ou de décision.Entrées:
nagents.Une ressource communelimitée.
Un langage commun d"expression des préférences et les préférences desnagents sur la ressource. Des contraintes sur les allocations possibles de la ressource.Un critère d"optimisation ou de décision.
Sortie:
Une allocation d"une partie de la ressource à chaque agent (parts) qui vérifie les contraintes et qui optimise ou vérifie le critère.3 / 55Problèmes de partage équitable de ressources
IntroductionApplications Modélisation Préférences numériques Absence d"envie Travaux futurs
L"équité dans les problèmes de partage
Spécificité des problèmes de partage faisant intervenir desagents humains: L"équitéen constitue un point central.
Objectif de la présentation:
présenter quelques applications concrètes du partage; introduire une modélisation du problème de partage, de l"expression des préférences, et du bien-être social; introduire deux instances particulières du problème de partage.4 / 55Problèmes de partage équitable de ressources
IntroductionApplicationsModélisation Préférences numériques Absence d"envie Travaux futurs
Le problème de partage équitable de
ressources : modélisation et applications.1Quelques applications concrètes du problème de partage
2Les éléments d"un problème de partage
La ressource
Contraintes sur la ressource
Préférences et expression compacte
Le bien-être social
Autres éléments
3Problème de partage avec préférences numériques
Le langage de représentation
La complexité
4La recherche de l"absence d"envie
Représentation logique du problème
Complexité
5 / 55Problèmes de partage équitable de ressources
IntroductionApplicationsModélisation Préférences numériques Absence d"envie Travaux futurs
Équité dans les réseaux informatiques
Réseaux informatiques: domaine très concerné par le partage [Denda et al. 2000]. la ressource à partager est l"accès au réseau (bande-passante); l"équité est une préoccupation centrale; les demandes des agents sont diverses selon les applications: temps réel, élastiques, ...; l"équité doit être mise en place à tous les niveaux, de la couche matérielle à la couche logicielle: traitement équitable des datagrammes, égalité du temps d"accès dans des programmes critiques comme les enchères en ligne, etc.6 / 55Problèmes de partage équitable de ressources
IntroductionApplicationsModélisation Préférences numériques Absence d"envie Travaux futurs
Équité dans le transport aérien
[Deschinkel 2001] Du fait de la très forte augmentation du trafic aérien ces dernières années, le partage des secteurs aériens et créneaux aéroportuaires devient critique: Ressource à partager: créneaux d"utilisation des aéroports et secteurs aériens. Agents: les différentes compagnies impliquées. Contraintes: normes de sécurité en vigueur / temps de parcours / routes empruntées par les avions.7 / 55Problèmes de partage équitable de ressources
IntroductionApplicationsModélisation Préférences numériques Absence d"envie Travaux futurs
Équité dans le transport aérien
[Deschinkel 2001] la demande excède la capacité des secteurs aériens? congestion; solution actuelle: retarder les avions au sol (inéquitableet engendrant des retards inacceptables); solutions envisagées: procédures d"optimisation avec un critère de coûts globaux (solution utilitariste), échanges d"information entre les compagnies et le contrôle aérien, conduisant naturellement à des solutions pluséquitables,
système de tarification modulable.7 / 55Problèmes de partage équitable de ressources
IntroductionApplicationsModélisation Préférences numériques Absence d"envie Travaux futurs
Une constellation de satellites
[Bouveret et al. 2005] Une constellation de satellites d"observation de la Terre co-financée par plusieurs pays (en raison de son coût).8 / 55Problèmes de partage équitable de ressources
IntroductionApplicationsModélisation Préférences numériques Absence d"envie Travaux futurs
Une constellation de satellites
[Bouveret et al. 2005] Une constellation de satellites d"observation de la Terre co-financée par plusieurs pays (en raison de son coût). Chaque agent (agences civiles et militaires de chaque pays) envoie des demandes d"images à prendre, simples ou complexes (stéréo, tri-stéréo...). Chaque jour, le Centre de Programmation sélectionne les demandes qui seront satisfaites le lendemain et allouées aux agents.L"exploitation doit être:
efficace?la constellation ne doit pas être sous-exploitée,équitable?chaque agent attend un " retour sur
investissement »en rapport avec sa contribution financière.8 / 55Problèmes de partage équitable de ressources
IntroductionApplicationsModélisation Préférences numériques Absence d"envie Travaux futurs
Une constellation de satellites (2)
Les agents: agences militaires et civiles de chaque pays. La ressource: l"exploitation du satellite (demandes d"images). L"expression des préférences: demandes pondérées et / ou niveaux de priorités. Contraintes: contraintes physiques (fenêtres temporelles, temps de transition, images particulières - stéréo, ... -, mémoire, énergie,...) Critère de qualité du partage: efficacité et équité.9 / 55Problèmes de partage équitable de ressources
IntroductionApplicationsModélisation Préférences numériques Absence d"envie Travaux futurs
Dans d"autres domaines...
Répartition de soins et de médicaments à des malades (guerre, catastrophe naturelle, ...); Gestion de ressources naturelles renouvelables (eau, ressources cynégétiques, bois, plantations, pâturages,...) [http://cormas.cirad.fr].10 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Le problème de partage équitable de
ressources : modélisation et applications.1Quelques applications concrètes du problème de partage
2Les éléments d"un problème de partage
La ressource
Contraintes sur la ressource
Préférences et expression compacte
Le bien-être social
Autres éléments
3Problème de partage avec préférences numériques
Le langage de représentation
La complexité
4La recherche de l"absence d"envie
Représentation logique du problème
Complexité
11 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Éléments d"un problème de partage
La ressource;
Les contraintes sur la ressource;
Les préférences des agents;
Le bien-être collectif;
Autres paramètres divers.
12 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Éléments d"un problème de partage
La ressource;
Les contraintes sur la ressource;
Les préférences des agents;
Le bien-être collectif;
Autres paramètres divers.
12 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Nature de la ressource
Divisibilité des ressources:
Ressource continue.?Découpage de gâteau, partage d"une somme d"argent, choix de l"emplacement d"un bien commun, partage de territoire... Ressource indivisible?Partage d"un ensemble d"objets entre plusieurs personnes, enchères, Pléiades... Ressource discrète (cas particulier de ressource indivisible) Ressource mixte?Partage de biens lors d"un héritage ou d"un divorce... Possibilité de compensations monétairesa posteriori? Partage de biens lors d"un héritage ou d"un divorce...13 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Nature de la ressource
Divisibilité des ressources:
Ressource continue.?Découpage de gâteau, partage d"une somme d"argent, choix de l"emplacement d"un bien commun, partage de territoire... Ressource indivisible?Partage d"un ensemble d"objets entre plusieurs personnes, enchères, Pléiades... Ressource discrète (cas particulier de ressource indivisible) Ressource mixte?Partage de biens lors d"un héritage ou d"un divorce... Possibilité de compensations monétairesa posteriori? Partage de biens lors d"un héritage ou d"un divorce...Partage
Partage-→π?2On.
13 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Éléments d"un problème de partage
La ressource;
Les contraintes sur la ressource;
Les préférences des agents;
Le bien-être collectif;
Autres paramètres divers.
14 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Contraintes sur la ressource
contraintes depréemptionentre objets?un objet ne peutêtre attribué qu"à une seule personne,
en générale présente lorsqu"il s"agit d"objets physiques, absente par exemple dans le cas d"objets virtuels (photographies numériques, licences d"utilisation de logiciels,...) contraintes d"exclusion?deux objets donnés ne peuvent être simultanément attribués, contraintes devolume?on ne peut attribuer plus d"un certain nombre, ou " volume »d"objets, contraintes de faisabilité physique, contraintes de dépendances quelconques entre agents.15 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Éléments d"un problème de partage
La ressource;
Les contraintes sur la ressource;
Les préférences des agents;
Le bien-être collectif;
Autres paramètres divers.
16 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Les préférences
Dans un problème de partage, chaque agent doit exprimer ses préférences sur l"ensemble des partages possibles. Hypothèse (préférences non exogènes):Chaque agent n"exprime ses préférences que sur les allocations qu"il reçoit (en particulier, il ne tient pas compte de ce qu"obtiennent les autres agents dans le partage). ensemble des alternatives = ensemble des parts possibles. pour l"agenti:X={πiallocation pour l"agenti}.17 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Comment exprimer une préférence?
Préférence: satisfaction absolue ou relative d"un individu face à diverses situations. préférences dichotomiques, préférences ordinales, préférences cardinales.18 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Comment exprimer une préférence?
Préférence: satisfaction absolue ou relative d"un individu face à diverses situations. préférences dichotomiques, préférences ordinales, préférences cardinales. un ensemble de " bonnes »parts,Structure de préférences dichotomique
Structure de préférences dichotomique surX:XG? X18 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs
Comment exprimer une préférence?
Préférence: satisfaction absolue ou relative d"un individu face à diverses situations. préférences dichotomiques, préférences ordinales, préférences cardinales. un ensemble de " bonnes »parts, un préordre sur l"ensemble des parts,Structure de préférences ordinale
Structure de préférences ordinale surX: préordre?surX.18 / 55Problèmes de partage équitable de ressources
Introduction ApplicationsModélisationPréférences numériques Absence d"envie Travaux futurs