这是indexloc提供的服务，不要输入任何密码
Skip to main content
Springer Nature Link
Log in

When is Truthfully Allocating Chores No Harder Than Goods?

  • Conference paper
  • First Online:
Algorithmic Game Theory (SAGT 2025)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15953))

Included in the following conference series:

  • 118 Accesses

Abstract

We study the problem of fairly and efficiently allocating a set of items among strategic agents with additive valuations, where items are either all indivisible or all divisible. When items are goods, numerous positive and negative results are known regarding the fairness and efficiency guarantees achievable by truthful mechanisms, whereas our understanding of truthful mechanisms for chores remains considerably more limited. In this paper, we discover various connections between truthful good and chore allocations, greatly enhancing our understanding of the latter via tools from the former.

For indivisible chores with two agents, by leveraging the observation that a simple bundle-swapping operation transforms several properties for goods including truthfulness to the corresponding properties for chores, we characterize truthful mechanisms and derive tight guarantees of various fairness notions achieved by truthful mechanisms. Moreover, for homogeneous divisible chores, by generalizing the above transformation to an arbitrary number of agents, we characterize truthful mechanisms with two agents, show that every truthful mechanism with two agents admits an efficiency ratio of 0, and derive a large family of strictly truthful, envy-free (EF), and proportional mechanisms for an arbitrary number of agents. Finally, for indivisible chores with an arbitrary number of agents having bi-valued cost functions, we give an ex-ante truthful, ex-ante Pareto optimal, ex-ante EF, and ex-post envy-free up to one item mechanism, improving the best guarantees for bi-valued instances by prior works.

The full version of our paper is available on arXiv: https://arxiv.org/abs/2505.01629.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. 1.

    Consider the case with two agents and one item.

  2. 2.

    Restricted additive valuations constitute a strict superset of binary valuations and a strict subset of additive valuations.

  3. 3.

    Note that ex-ante PO implies ex-post fPO.

  4. 4.

    Here, we encode a utility function \(v_j\) by the vector \((v_j(o_1), \ldots , v_j(o_m)) \in [0, 1]^m\), and we say that a condition holds with respect to a utility function if it holds with respect to the corresponding vector in \([0, 1]^m\).

  5. 5.

    Mechanisms with an efficiency ratio better than 0.5 exist when allowing some items to remain unallocated [25, 27].

  6. 6.

    When \(q = 0\), the case of bi-valued cost functions are equivalent to that of binary cost functions, which has been thoroughly studied by prior work, e.g., [48].

  7. 7.

    We say that the cost functions are restricted additive if each item o is associated with an intrinsic value \(e_o\) such that \(c_i(o) \in \{0, e_o\}\) for every agent i.

References

  1. Amanatidis, G., et al.: Fair division of indivisible goods: recent progress and open questions. Artif. Intell. 322, 103965 (2023). https://doi.org/10.1016/j.artint.2023.103965

    Article  MathSciNet  Google Scholar 

  2. Amanatidis, G., Birmpas, G., Christodoulou, G., Markakis, E.: Truthful allocation mechanisms without payments: characterization and implications on fairness. In: EC, pp. 545–562. ACM (2017)

    Google Scholar 

  3. Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Hollender, A., Voudouris, A.A.: Maximum Nash welfare and other stories about EFX. Theor. Comput. Sci. 863, 69–85 (2021)

    Article  MathSciNet  Google Scholar 

  4. Amanatidis, G., Birmpas, G., Fusco, F., Lazos, P., Leonardi, S., Reiffenhäuser, R.: Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness. In: Feldman, M., Fu, H., Talgam-Cohen, I. (eds.) WINE 2021. LNCS, vol. 13112, pp. 149–166. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-94676-0_9

    Chapter  Google Scholar 

  5. Amanatidis, G., Birmpas, G., Lazos, P., Leonardi, S., Reiffenhäuser, R.: Round-robin beyond additive agents: Existence and fairness of approximate equilibria. In: EC, pp. 67–87. ACM (2023)

    Google Scholar 

  6. Amanatidis, G., Birmpas, G., Markakis, E.: On truthful mechanisms for maximin share allocations. In: IJCAI, pp. 31–37. IJCAI/AAAI Press (2016)

    Google Scholar 

  7. Aziz, H.: Simultaneously achieving ex-ante and ex-post fairness. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds.) WINE 2020. LNCS, vol. 12495, pp. 341–355. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64946-3_24

    Chapter  Google Scholar 

  8. Aziz, H., Freeman, R., Shah, N., Vaish, R.: Best of both worlds: ex ante and ex post fairness in resource allocation. Oper. Res. (2023)

    Google Scholar 

  9. Aziz, H., Li, B., Wu, X.: Strategyproof and approximately maxmin fair share allocation of chores. In: IJCAI, pp. 60–66. ijcai.org (2019)

    Google Scholar 

  10. Aziz, H., Li, B., Wu, X.: Approximate and strategyproof maximin share allocation of chores with ordinal preferences. Math. Program. 203(1), 319–345 (2024)

    Article  MathSciNet  Google Scholar 

  11. Aziz, H., Ye, C.: Cake cutting algorithms for piecewise constant and piecewise uniform valuations. In: Liu, T.-Y., Qi, Q., Ye, Y. (eds.) WINE 2014. LNCS, vol. 8877, pp. 1–14. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13129-0_1

    Chapter  Google Scholar 

  12. Babaioff, M., Ezra, T., Feige, U.: Fair and truthful mechanisms for dichotomous valuations. In: AAAI, pp. 5119–5126. AAAI Press (2021)

    Google Scholar 

  13. Barman, S., Verma, P.: Truthful and fair mechanisms for matroid-rank valuations. In: AAAI, pp. 4801–4808. AAAI Press (2022)

    Google Scholar 

  14. Bei, X., Elkind, E., Segal-Halevi, E., Suksompong, W.: Dividing a graphical cake. SIAM J. Discret. Math. 39(1), 19–54 (2025)

    Article  MathSciNet  Google Scholar 

  15. Bei, X., Huzhang, G., Suksompong, W.: Truthful fair division without free disposal. Soc. Choice Welfare 55(3), 523–545 (2020). https://doi.org/10.1007/s00355-020-01256-0

    Article  MathSciNet  Google Scholar 

  16. Bei, X., Tao, B., Wu, J., Yang, M.: The incentive guarantees behind Nash welfare in divisible resources allocation. Artif. Intell. 104335 (2025)

    Google Scholar 

  17. Bezáková, I., Dani, V.: Allocating indivisible goods. SIGecom Exch. 5(3), 11–18 (2005)

    Article  Google Scholar 

  18. Brams, S.J., Jones, M.A., Klamler, C., et al.: Better ways to cut a cake. Not. AMS 53(11), 1314–1321 (2006)

    MathSciNet  Google Scholar 

  19. Bu, X., Song, J., Tao, B.: On existence of truthful fair cake cutting mechanisms. Artif. Intell. 319, 103904 (2023)

    Article  MathSciNet  Google Scholar 

  20. Bu, X., Tao, B.: Truthful and almost envy-free mechanism of allocating indivisible goods: the power of randomness. CoRR abs/2407.13634 (2024)

    Google Scholar 

  21. Budish, E.: The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Political Econ. 119(6), 1061–1103 (2011)

    Article  Google Scholar 

  22. Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. ACM Trans. Econ. Comput. 7(3), 12:1–12:32 (2019)

    Google Scholar 

  23. Chaudhury, B.R., Garg, J., McGlaughlin, P., Mehta, R.: Competitive equilibrium with chores: combinatorial algorithm and hardness. In: EC, pp. 1106–1107. ACM (2022)

    Google Scholar 

  24. Chen, Y., Lai, J.K., Parkes, D.C., Procaccia, A.D.: Truth, justice, and cake cutting. Games Econ. Behav. 77(1), 284–297 (2013)

    Article  MathSciNet  Google Scholar 

  25. Cheung, Y.K.: Better strategyproof mechanisms without payments or prior - an analytic approach. In: IJCAI, pp. 194–200. IJCAI/AAAI Press (2016)

    Google Scholar 

  26. Cole, R., Gkatzelis, V., Goel, G.: Mechanism design for fair division: allocating divisible items without payments. In: EC, pp. 251–268. ACM (2013)

    Google Scholar 

  27. Cole, R., Gkatzelis, V., Goel, G.: Positive results for mechanism design without money. In: AAMAS, pp. 1165–1166. IFAAMAS (2013)

    Google Scholar 

  28. Ebadian, S., Peters, D., Shah, N.: How to fairly allocate easy and difficult chores. In: AAMAS, pp. 372–380. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) (2022)

    Google Scholar 

  29. Foley, D.: Resource allocation and the public sector. Yale Economic Essays, pp. 45–98 (1967)

    Google Scholar 

  30. Freeman, R., Witkowski, J., Vaughan, J.W., Pennock, D.M.: An equivalence between fair division and wagering mechanisms. Manage. Sci. (2023)

    Google Scholar 

  31. Garg, J., Murhekar, A.: Computing fair and efficient allocations with few utility values. Theor. Comput. Sci. 962, 113932 (2023)

    Article  MathSciNet  Google Scholar 

  32. Garg, J., Murhekar, A., Qin, J.: Fair and efficient allocations of chores under bivalued preferences. In: AAAI, pp. 5043–5050. AAAI Press (2022)

    Google Scholar 

  33. Garg, J., Murhekar, A., Qin, J.: New algorithms for the fair and efficient allocation of indivisible chores. In: IJCAI, pp. 2710–2718. ijcai.org (2023)

    Google Scholar 

  34. Goko, H., et al.: A fair and truthful mechanism with limited subsidy. Games Econ. Behav. 144, 49–70 (2024)

    Article  MathSciNet  Google Scholar 

  35. Gourvès, L., Monnot, J., Tlilane, L.: Near fairness in matroids. In: ECAI. Frontiers in Artificial Intelligence and Applications, vol. 263, pp. 393–398. IOS Press (2014)

    Google Scholar 

  36. Guo, M., Conitzer, V.: Strategy-proof allocation of multiple items between two agents without payments or priors. In: AAMAS, pp. 881–888. IFAAMAS (2010)

    Google Scholar 

  37. Halpern, D., Procaccia, A.D., Psomas, A., Shah, N.: Fair division with binary valuations: one rule to rule them all. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds.) WINE 2020. LNCS, vol. 12495, pp. 370–383. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64946-3_26

    Chapter  Google Scholar 

  38. Han, L., Su, C., Tang, L., Zhang, H.: On strategy-proof allocation without payments or priors. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 182–193. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25510-6_16

    Chapter  Google Scholar 

  39. Hartman, E., Segal-Halevi, E., Tao, B.: It’s not all black and white: degree of truthfulness for risk-avoiding agents. CoRR abs/2502.18805 (2025)

    Google Scholar 

  40. Huang, H., Wang, Z., Wei, Z., Zhang, J.: Bounded incentives in manipulating the probabilistic serial rule. J. Comput. Syst. Sci. 140, 103491 (2024)

    Article  MathSciNet  Google Scholar 

  41. Li, B., Sun, A., Xing, S.: Bounding the incentive ratio of the probabilistic serial rule. In: AAMAS, pp. 1128–1136. IFAAMAS (2024)

    Google Scholar 

  42. Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: EC, pp. 125–131. ACM (2004)

    Google Scholar 

  43. Markakis, E., Psomas, C.-A.: On worst-case allocations in the presence of indivisible goods. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 278–289. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25510-6_24

    Chapter  Google Scholar 

  44. Ortega, J., Segal-Halevi, E.: Obvious manipulations in cake-cutting. Soc. Choice Welfare. 1–20 (2022)

    Google Scholar 

  45. Psomas, A., Verma, P.: Fair and efficient allocations without obvious manipulations. In: NeurIPS (2022)

    Google Scholar 

  46. Segal-Halevi, E.: Competitive equilibrium for almost all incomes: existence and fairness. Auton. Agent. Multi-Agent Syst. 34(1), 1–50 (2020). https://doi.org/10.1007/s10458-020-09444-z

    Article  Google Scholar 

  47. Steinhaus, H.: The problem of fair division. Econometrica 16, 101–104 (1948)

    Google Scholar 

  48. Sun, A., Chen, B.: Randomized strategyproof mechanisms with best of both worlds fairness and efficiency. Eur. J. Oper. Res. 324(3), 941–952 (2025)

    Article  MathSciNet  Google Scholar 

  49. Tao, B., Yang, M.: Fair and almost truthful mechanisms for additive valuations and beyond (2024). https://arxiv.org/abs/2306.15920

Download references

Acknowledgments

We would like to thank the anonymous reviewers for their detailed feedback and comments that helped significantly improve the exposition of this paper. Bo Li is partly funded by the Hong Kong SAR Research Grants Council (No. PolyU 15224823) and the Department of Science and Technology of Guangdong Province (No. 2023A1515010592). The research of Biaoshuai Tao is supported by the National Natural Science Foundation of China (No. 62472271) and the Key Laboratory of Interdisciplinary Research of Computation and Economics (Shanghai University of Finance and Economics), Ministry of Education. Xiaowei Wu is funded by the Science and Technology Development Fund (FDCT), Macau SAR (file no. 0147/2024/RIA2, 0014/2022/AFJ, 0085/2022/A, and 001/2024/SKL).

Author information

Authors and Affiliations

  1. The Hong Kong Polytechnic University, Hong Kong, China

    Bo Li & Fangxiao Wang

  2. Shanghai Jiao Tong University, Shanghai, China

    Biaoshuai Tao

  3. University of Macau, Macau, China

    Xiaowei Wu & Shengwei Zhou

  4. Stanford University, Stanford, CA, USA

    Mingwei Yang

Authors
  1. Bo Li
    View author publications

    Search author on:PubMed Google Scholar

  2. Biaoshuai Tao
    View author publications

    Search author on:PubMed Google Scholar

  3. Fangxiao Wang
    View author publications

    Search author on:PubMed Google Scholar

  4. Xiaowei Wu
    View author publications

    Search author on:PubMed Google Scholar

  5. Mingwei Yang
    View author publications

    Search author on:PubMed Google Scholar

  6. Shengwei Zhou
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Mingwei Yang .

Editor information

Editors and Affiliations

  1. University of Bath, Bath, UK

    Ron Lavi

  2. University of Bath, Bath, UK

    Jie Zhang

Rights and permissions

Reprints and permissions

Copyright information

© 2026 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Li, B., Tao, B., Wang, F., Wu, X., Yang, M., Zhou, S. (2026). When is Truthfully Allocating Chores No Harder Than Goods?. In: Lavi, R., Zhang, J. (eds) Algorithmic Game Theory. SAGT 2025. Lecture Notes in Computer Science, vol 15953. Springer, Cham. https://doi.org/10.1007/978-3-032-03639-1_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-032-03639-1_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-032-03638-4

  • Online ISBN: 978-3-032-03639-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Keywords

Publish with us

Policies and ethics