Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Autonomous Agents and Multi-Agent Systems
Erschienen in: Autonomous Agents and Multi-Agent Systems 6/2017

13.05.2017

On the hierarchical nature of partial preferences over lotteries

verfasst von: Luigi Sauro

Erschienen in: Autonomous Agents and Multi-Agent Systems | Ausgabe 6/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this work we consider preference relations that might not be total. Partial preferences may be helpful to represent those situations where, due to lack of information or vacillating desires, the decision maker would like to maintain different options “alive” and defer the final decision. In particular, we show that, when totality is relaxed, different axiomatizations of classical Decision Theory are no longer equivalent but form a hierarchy where some of them are more restrictive than others. We compare such axiomatizations with respect to theoretical aspects—such as their ability to propagate comparability/incomparability over lotteries and the induced topology—and to different preference elicitation methodologies that are applicable in concrete domains. We also provide a polynomial-time procedure based on the bipartite matching problem to determine whether one lottery is preferred to another.
Vorheriger Artikel Hybrid mission planning with coalition formation
Nächster Artikel Computational aspects of strategic behaviour in elections with top-truncated ballots

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
Together with Newell, he won the Turing Award in 1975 for his contributions on “artificial intelligence, the psychology of human cognition, and list processing” (http://​amturing.​acm.​org/​award_​winners/​simon_​1031467.​cfm).
 
2
In Greek mythology, Eteocles and Polynices, sons of Oedipus, contended for the city of Thebes and killed each other in battle.
 
3
A preorder is a reflexive and transitive relation, clearly Axiom 1 implies reflexivity.
 
4
To the best of our knowledge, such an extensive analysis of axioms’ interdependencies has not been shown elsewhere.
 
5
By “linearly closed” the authors means that the intersection of D with any line is a closed set. This in particular implies that D is closed.
 
6
We refer to [1] for a concrete application domain where a user/agent interface provides a set of statements \(\mathsf {S}\) over service-level agreements.
 
7
It is an open question whether Theorem 20 holds for \(\text {PDT}_{4/5}\).
 
8
Instantiating the relations \(=_c\) and \(<_c\) is not more complex than calculating the transitive closure of a relation, hence it can be done in \(O(\vert \mathcal {A} \vert ^3)\). Then, on the one hand, checking \(f\sim _c g\) means to verify that, for all equivalent classes \([a]]\) induced by \(=_c\), \(f([[a]])=g([[a]])\), which can be done in \(O(\vert \mathcal {A} \vert )\). On the other hand, checking \(f\prec _c g\) means to verify that \(f\twoheadrightarrow _c g\), by Theorem 6 this is essentially equivalent to a bipartite-matching problem that can be solved again in \(O(\vert \mathcal {A} \vert ^3)\) [47].
 
9
Here, \(\delta \) is interpreted as a constant function and hence \((Y + \delta )(\omega )=Y(\omega )+\delta \).
 
10
Note that this can happen even if the user’s statements are a total order of \(\mathcal {A} \). For example, consider the user’s statements \(a< b<c<d\). Two possible utilities are: \(u_1(a)=1\), \(u_1(b)=5\), \(u_1(c)=6\), \(u_1(d)=10\), and \(u_2(a)=1\), \(u_2(b)=4\), \(u_2(c)=5\), \(u_2(d)=10\). Then, given \(f=\frac{1}{2}[a]+\frac{1}{2}[d]\) and \(g=\frac{1}{2}[b]+\frac{1}{2}[c]\), it is immediate to see that \(f\cdot u_1< g\cdot u_1\) whereas \(f\cdot u_2> g\cdot u_2\).
 
Literatur
1.
Anisetti, M., Ardagna, C. A. Bonatti, P. A. Damiani, E., Faella, M., Galdi, C., & Sauro, L. (2014). E-auctions for multi-cloud service provisioning. In Proceedings of the IEEE international conference on services computing, SCC 2014, Anchorage, AK, USA. June 27–July 2, 2014.
2.
3.
Aumann, R. J. (1962). Utility Theory without the completeness axiom. Econometrica, 30(3), 445–462.CrossRefMATH
4.
Aydogan, R. & Yolum, P. (2010). Effective negotiation with partial preference information. In Proceedings of 9th international conference on autonomous agents and multiagent systems (AAMAS10), Toronto, Canada. May 10–14, 2010 (Vol. 1–3, pp. 1605–1606).
5.
Aydogan, R., & Yolum, P. (2012). Learning opponent’s preferences for effective negotiation: An approach based on concept learning. Autonomous Agents and Multi-agent Systems, 24(1), 104–140.CrossRef
6.
Bonatti, P. A., Faella, M., Galdi, C. & Sauro, L. (2011). Towards a mechanism for incentivating privacy. In Proceedings of the 16th European symposium on research in computer security (ESORICS11), Leuven, Belgium. September 12–14, 2011.
7.
Bonatti, P. A., Faella, M., Galdi, C. & Sauro, L. (2013). Auctions for partial heterogeneous preferences. In Proceedings of mathematical foundations of computer science 2013—38th international symposium (MFCS 2013), Klosterneuburg, Austria. August 26–30, 2013.
8.
Bonatti, P. A., Faella, M., Galdi, C., & Sauro, L. (2016).Generalized Agent-mediated Procurement Auctions. In Proceedings of the international conference on autonomous agents and multi-agent systems (AAMAS16), Singapore. May 09–13, 2016.
9.
Boutilier, C., Brafman, R. I., Domshlak, C., & Hoos, H. H. (2004). CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research, 21, 135–191.MathSciNetMATH
10.
Brafman, R. I., Domshlak, C., & Shimony, Solomon E. (2006). On graphical modeling of preference and importance. Journal of Artificial Intelligence Research, 25, 389–424.MathSciNetMATH
11.
Bridges, D. S. & Mehta, G. B. (1995). Representations of preferences orderings (1st edn). Series lecture notes in economics and mathematical systems (Vol. 422). Berlin: Springer.
12.
Cornelio, C., Grandi, U., Goldsmith, J., Mattei, N., Rossi, F. & Venable, K. B. (2015). Reasoning with PCP-nets in a multi-agent context. In Proceedings of the 2015 international conference on autonomous agents and multiagent systems (AAMAS15), Istanbul, Turkey (pp. 969–977). May 4–8, 2015.
13.
Drummond, J. & Boutilier, C. (2013). Elicitation and approximately stable matching with partial preferences. In Proceedings of the 23rd international joint conference on artificial intelligence (IJCAI13), Beijing, China. August 3–9, 2013.
14.
15.
Dubra, J., Maccheroni, F., & Ok, Efe A. (2004). Expected utility theory without the completeness axiom. Journal of Economic Theory, 115(1), 118–133.MathSciNetCrossRefMATH
16.
Eliaz, K., & Ok, E. A. (2006). Indifference or indeciveness? Choice-theoretic foundation ofs of incomplete preferences. Games and Economic Behaviour, 56, 61–86.CrossRefMATH
17.
Evren, O., & Ok, E. A. (2011). On the multi-utility representation of preference relations. Journal of Mathematical Economics, 47, 554–563.MathSciNetCrossRefMATH
18.
19.
Fishburn, P. C. (1976). On linear extention majority graphs on partial orders. Journal of Combinatorial Theory, 21, 65–70.CrossRefMATH
20.
Fishburn, P. C. (1982). The foundations of expected utility (1st edn). In G. Eberlein & W. Leinfellner (Eds.), Theory and decision library (Vol. 31). Dordrecht: Springer.
21.
Fishburn, P. C. (1999). Preference structures and their numerical representations. Theoretical Computer Science, 217, 359–383.MathSciNetCrossRefMATH
22.
Gilboa, I. (2009). Theory of decision under uncertainty. Cambridge: Cambridge University Press.CrossRefMATH
23.
Goldsmith, J., Lang, J., Truszczynski, M., & Wilson, N. (2008). The computational complexity of dominance and consistency in CP-nets. Journal of Artificial Intelligence Research, 33, 403–432.MathSciNetMATH
24.
Kadane, J. B., Schervish, M. J., & Seidenfeld, T. (1999). Rethinking the foundations of statistics. Cambridge: Cambridge University Press.CrossRefMATH
25.
Mandler, M. (2005). Incomplete preferences and rational intransitivity of choice. Games and Economic Behaviour, 50, 255–277.MathSciNetCrossRefMATH
26.
McCord, M. R., & Roy, B. (1996). Multicriteria methodology for decision aiding. Berlin: Springer.
27.
Myerson, R. B. (1997). Game theory: Analysis of conflict. Cambridge: Harvard University Press.MATH
28.
Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (2007). Algorithmic game theory. New York, NY: Cambridge University Press.CrossRefMATH
29.
30.
Ok, E. A., & Dubra, J. (2002). A model of procedural decision making in the presence of risk. International Economic Review, 43, 1053–1080.MathSciNetCrossRef
31.
32.
Pini, M. S., Rossi, F., Venable, K. B. & Walsh, T. (2007). Incompleteness and incomparability in preference aggregation. In Proceedings of 20th international joint conference on artificial intelligence (IJCAI07), Hyderabad, India (pp. 1464–1469). January 6–12.
33.
Pini, M. S., Rossi, F., Venable, K. B., & Walsh, T. (2011). Incompleteness and incomparability in preference aggregation: Complexity results. Artificial Intelligence, 175, 1272–1289.MathSciNetCrossRefMATH
34.
35.
Rockafellar, R. T. (1972). Convex analysis. Princeton: Princeton University Press.MATH
36.
Rossi, F., Brent Venable, K., & Walsh, T. (2008). Preferences in constraint satisfaction and optimization. AI Magazine, 29(4), 58–68.CrossRef
37.
Russell, W., & Hadar, J. (1969). Rules for ordering uncertain prospects. American Economic Review, 59, 25–34.
38.
Samuelson, P. A. (1938). A note on the pure theory of consumer’s behaviour. Economica, 5(17), 61–71.CrossRef
39.
Sauro, L. (2015). On the hierarchical nature of partial preferences. In Proceedings of the 18th international conference on principles and practice of multi-agent systems, PRIMA15, Bertinoro, Italy. October 26–30, 2015.
40.
Savage, L. J. (1954). The foundations of statistics. New York: Wiley.MATH
41.
Sen, A., & Majumdar, M. (1976). A note on representing partial orderings. Review of Economic Studies, 43(3), 543–545.CrossRefMATH
42.
43.
44.
45.
46.
van Neumann, J., & Morgenstern, O. (1944). Theory of games and economic behavior. Princeton: Princeton University Press.MATH
47.
Waissi, G. R. (1992). A new karzanov-type \(O(n^3)\) max-flow algorithm. Journal of Artificial Intelligence Research, 16((2), 65–72.MathSciNetMATH
48.
Walley, P. (1991). Statistical reasoning with imprecise probabilities. London: Chapman and Hall.CrossRefMATH
49.
Wilson, N. (2004). Extending CP-nets with stronger conditional preference statements. In Proceedings of the nineteenth national conference on artificial intelligence (AAAI04), San Jose, California. July 25–29, 2004.
50.
Xia, L., & Conitzer, V. (2011). Determining possible and necessary winners under common voting rules given partial orders. Journal of Artificial Intelligence Research, 41, 25–67.MathSciNetMATH
Metadaten
Titel
On the hierarchical nature of partial preferences over lotteries
verfasst von
Luigi Sauro
Publikationsdatum
13.05.2017
Verlag
Springer US
Erschienen in
Autonomous Agents and Multi-Agent Systems / Ausgabe 6/2017
Print ISSN: 1387-2532
Elektronische ISSN: 1573-7454
DOI
https://doi.org/10.1007/s10458-017-9368-6

Weitere Artikel der Ausgabe 6/2017

Autonomous Agents and Multi-Agent Systems 6/2017 Zur Ausgabe

OriginalPaper

Facility location with double-peaked preferences

OriginalPaper

Detection and resolution of normative conflicts in multi-agent systems: a literature survey

OriginalPaper

ACMICS: an agent communication model for interacting crowd simulation

OriginalPaper

Computational aspects of strategic behaviour in elections with top-truncated ballots

OriginalPaper

A multi-unit combinatorial auction based approach for decentralized multi-project scheduling

OriginalPaper

Towards Circular Economy implementation: an agent-based simulation approach for business model changes