Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Explaining Black-Box Models Using Interpretable Surrogates Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Strategy-Proofness, Envy-Freeness and Pareto Efficiency in Online Fair Division with Additive Utilities

Authors : Martin Aleksandrov, Toby Walsh

Published in: PRICAI 2019: Trends in Artificial Intelligence

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider fair division problems where indivisible items arrive one by one in an online fashion and are allocated immediately to agents who have additive utilities over these items. Many existing offline mechanisms do not work in this online setting. In addition, many existing axiomatic results often do not transfer from the offline to the online setting. For this reason, we propose here three new online mechanisms, as well as consider the axiomatic properties of three previously proposed online mechanisms. In this paper, we use these mechanisms and characterize classes of online mechanisms that are strategy-proof, and return envy-free and Pareto efficient allocations, as well as combinations of these properties. Finally, we identify an important impossibility result.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Predictive Systems: The Game Rock-Paper-Scissors as an Example
next chapter Knowledge Enhanced Neural Networks
Literature
1.
Abdulkadiroglu, A., Sönmez, T.: Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3), 689–702 (1998)MathSciNetMATHCrossRef
2.
Aleksandrov, M., Aziz, H., Gaspers, S., Walsh, T.: Online fair division: analysing a food bank problem. In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires, Argentina, 25–31 July 2015, pp. 2540–2546 (2015)
3.
4.
Benade, G., Kazachkov, A.M., Procaccia, A.D., Psomas, C.A.: How to make envy vanish over time. In: Proceedings of the 2018 ACM Conference on Economics and Computation, EC 2018, pp. 593–610. ACM, New York (2018)
5.
6.
Brams, S.J., King, D.L.: Efficient fair division: help the worst off or avoid envy? Rat. Soc. 17(4), 387–421 (2005)CrossRef
7.
Chevaleyre, Y., Endriss, U., Estivie, S., Maudet, N.: Multiagent resource allocation in k-additive domains: preference representation and complexity. Ann. Oper. Res. 163(1), 49–62 (2008)MathSciNetMATHCrossRef
8.
Dickerson, J.P., Procaccia, A.D., Sandholm, T.: Dynamic matching via weighted myopia with application to kidney exchange. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (2012)
9.
Dickerson, J.P., Sandholm, T.: Futurematch: combining human value judgments and machine learning to match in dynamic environments. In: Proceedings of the Twenty-Ninth AAAI Conference, pp. 622–628 (2015)
10.
Freeman, R., Zahedi, S.M., Conitzer, V., Lee, B.C.: Dynamic proportional sharing: a game-theoretic approach. In: Proceedings of the ACM on Measurement and Analysis of Computing Systems - SIGMETRICS, vol. 2, no. 1, pp. 3:1–3:36, April 2018
11.
12.
13.
Lian, J.W., Mattei, N., Noble, R., Walsh, T.: The conference paper assignment problem: using order weighted averages to assign indivisible goods. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), New Orleans, Louisiana, USA, 2–7 February 2018, pp. 1138–1145 (2018)
14.
15.
16.
17.
18.
19.
Metadata
Title
Strategy-Proofness, Envy-Freeness and Pareto Efficiency in Online Fair Division with Additive Utilities
Authors
Martin Aleksandrov
Toby Walsh
Copyright Year
2019
Book
PRICAI 2019: Trends in Artificial Intelligence

Print ISBN: 978-3-030-29907-1

Electronic ISBN: 978-3-030-29908-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-29908-8_42

Premium Partner

    Image Credits