Learning Fair Allocation of Indivisible Items from Limited Feedback

David Kempe; Evi Micha; Xinyu Liu

arxiv: 2606.31457 · v1 · pith:RJSZNGHRnew · submitted 2026-06-30 · 💻 cs.GT

Learning Fair Allocation of Indivisible Items from Limited Feedback

Xinyu Liu , David Kempe , Evi Micha This is my paper

Pith reviewed 2026-07-01 03:32 UTC · model grok-4.3

classification 💻 cs.GT

keywords fair allocationindivisible itemsEF1PROP1learning from feedbackadditive valuationspolytopeellipsoid method

0 comments

The pith

Algorithms find EF1 and PROP1 allocations for additive valuations over mixed items by refining a polytope of consistent valuations from violation feedback alone.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops methods for computing fair allocations of indivisible items when an algorithm has no initial information about agents' valuations and receives only feedback on fairness violations in proposed allocations. For additive valuations, even when items include both goods and chores, the approach guarantees an EF1 or PROP1 allocation in a number of rounds polynomial in the number of agents and items. The core technique maintains a polytope containing all valuation functions consistent with observed feedback and uses violations to cut the polytope via separating hyperplanes, emulating the ellipsoid method to identify a suitable allocation. A separate algorithm handles monotone valuations by restricting attention to allocations of a particular structural form whose existence is proven non-constructively. This setup allows the algorithm to converge without ever learning the full valuation functions.

Core claim

When the valuations are additive, then even for mixed items (goods and chores), an allocation satisfying EF1 or PROP1 can be found in polynomial time using the corresponding feedback. These results are instantiations of a more general framework which maintains a polytope of candidate valuations consistent with all past feedback. The algorithm repeatedly constructs putative valuations and uses them to propose allocations; the observed violations then define separating hyperplanes, allowing the algorithm to emulate the ellipsoid method. When the valuations are monotone, an algorithm finds an EF1 allocation in polynomially many iterations by restricting to allocations in which each agent obtain

What carries the argument

Polytope of candidate valuations consistent with past feedback, refined by separating hyperplanes from observed fairness violations to emulate the ellipsoid method.

If this is right

EF1 allocations for additive valuations of mixed items are computable in polynomial rounds from violation feedback.
PROP1 allocations for the same setting are also computable in polynomial rounds from violation feedback.
The polytope-refinement framework works even when feedback is chosen adversarially.
For monotone valuations an EF1 allocation of interval-plus-one-item form always exists and can be found in polynomially many iterations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same feedback-driven polytope technique could be applied to other fairness notions such as envy-freeness up to any item.
In practice this reduces the need for agents to reveal full preference information in repeated allocation settings.
One could test whether the number of rounds required in typical instances is much smaller than the worst-case polynomial bound.
The structural restriction used for monotone valuations might admit faster constructive proofs for other classes of valuations.

Load-bearing premise

Feedback on fairness violations can always be used to define separating hyperplanes that refine the polytope of consistent valuations until a fair allocation is identified.

What would settle it

An instance of additive valuations together with an adversarial sequence of violation feedback that forces the maintained polytope to exclude all valuations for which any proposed allocation satisfies EF1 or PROP1 after polynomially many rounds.

read the original abstract

We study a setting in which an algorithm must output a fair allocation of indivisible items while "learning on the job". More specifically, the algorithm is to output an allocation satisfying EF1, PROP1, or similar fairness notions; however, the algorithm initially has no information about the agents' valuations, and can only learn about them by (repeatedly) proposing an allocation, and obtaining feedback about a fairness violation in the allocation. Importantly, the observed fairness violation may be adversarially chosen. The algorithm's goal is to converge to a fair allocation in rounds polynomial in the number of agents and items, ideally with only polynomial computation. We prove two main results: first, when the valuations are additive, then even for mixed items (goods and chores), an allocation satisfying EF1 or PROP1 can be found in polynomial time using the corresponding feedback. These results are instantiations of a more general framework which maintains a polytope of candidate valuations consistent with all past feedback. The algorithm repeatedly constructs putative valuations and uses them to propose allocations; the observed violations then define separating hyperplanes, allowing the algorithm to emulate the ellipsoid method. When the valuations are monotone, we present an algorithm which is guaranteed to find an EF1 allocation in polynomially many iterations; however, its internal calculations are not guaranteed to be polynomial. The algorithm again maintains putative valuations, and only considers allocations in which each agent obtains an interval plus one additional item with respect to an arbitrary ordering of the items. We (non-constructively) prove that there always exist EF1 allocations of this form, allowing us to use a further generalization of the preceding ellipsoid-based ideas.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

New limited-feedback model for EF1/PROP1 via polytope cuts and ellipsoid emulation works for additive mixed items, but poly-time needs explicit valuation bounds to hold.

read the letter

The paper's main move is to let an algorithm propose allocations, receive an adversarial fairness violation report, and use that report as a separating hyperplane to shrink a polytope of candidate valuations until a fair allocation can be output. For additive valuations over goods and chores, this yields polynomial-time algorithms for EF1 and PROP1 by emulating the ellipsoid method on the maintained polytope. The monotone case adds a non-constructive existence proof that EF1 allocations exist in a restricted interval-plus-one form, which lets the same geometric idea apply even though the internal steps are not polynomial.

This is genuinely new in the fair-division literature: prior work on learning valuations usually assumes direct queries or full reports, not just violation signals. The reduction to convex geometry is clean and handles the mixed-item setting without extra machinery.

The soft spot is the polynomial bound. Standard ellipsoid analysis requires a known containing ball and target precision; without normalization on the valuations (unit L1 norm, bounded bits, etc.), the iteration count can depend on arbitrary scale factors and stop being polynomial in n and m. The abstract is silent on this, so the proofs need to supply it or the claim weakens. The monotone result is also weaker than it first appears because computation is not guaranteed polynomial.

The work is aimed at people already working on interactive or query-limited fair division. It deserves a serious referee to check the polytope update rules and the radius/precision arguments. I would send it to review rather than desk-reject.

Referee Report

1 major / 1 minor

Summary. The paper studies learning fair allocations of indivisible mixed items (goods and chores) from feedback on fairness violations, without prior knowledge of additive or monotone valuations. For additive valuations, it claims polynomial-time algorithms for EF1 and PROP1 allocations via a general framework that maintains a polytope of valuations consistent with feedback, constructs putative valuations to propose allocations, and uses violations as separating hyperplanes to emulate the ellipsoid method. For monotone valuations, it gives an algorithm with polynomially many iterations for EF1 (but not necessarily polynomial computation) by restricting to interval-plus-one allocations and proving their existence non-constructively.

Significance. If the central claims hold, the work is significant for integrating limited-feedback learning with fair division of indivisible items, offering a polytope-based framework that handles adversarial feedback and mixed valuations. The explicit polynomial-time results for the additive case (even with chores) and the non-constructive existence argument for the monotone case are strengths; the former instantiates a reusable ellipsoid-emulation technique that could apply more broadly if normalization issues are resolved.

major comments (1)

[Abstract and general framework] Abstract and general framework description: the polynomial-time claims for additive valuations rest on emulating the ellipsoid method over the maintained polytope, with iteration bound O(d² log(R/r)) where d = O(nm). However, no normalization (e.g., ||v_i||_1 = 1, max |v_ij| ≤ 1, or rational bit-length bounds on valuations) is stated in the model or framework. Without it, the initial containing ball radius R can be arbitrary, making the iteration count non-polynomial in the input size (n, m). This directly affects both the runtime guarantee and the claim that a sufficiently small polytope forces the center-derived allocation to be fair for the true valuation (as perturbation tolerance δ scales with valuation magnitude).

minor comments (1)

[Abstract] The distinction between polynomial iterations and polynomial computation is clearly stated for the monotone case but could be foreshadowed in the abstract to avoid reader confusion about the scope of the 'polynomial time' results.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying this important issue with the normalization assumptions underlying the polynomial-time claims. We address the comment below.

read point-by-point responses

Referee: [Abstract and general framework] Abstract and general framework description: the polynomial-time claims for additive valuations rest on emulating the ellipsoid method over the maintained polytope, with iteration bound O(d² log(R/r)) where d = O(nm). However, no normalization (e.g., ||v_i||_1 = 1, max |v_ij| ≤ 1, or rational bit-length bounds on valuations) is stated in the model or framework. Without it, the initial containing ball radius R can be arbitrary, making the iteration count non-polynomial in the input size (n, m). This directly affects both the runtime guarantee and the claim that a sufficiently small polytope forces the center-derived allocation to be fair for the true valuation (as perturbation tolerance δ scales with valuation magnitude).

Authors: We agree that the manuscript does not explicitly state normalization assumptions on the valuations, which is required for the ellipsoid-emulation argument to yield a polynomial iteration bound in the input size (n, m) and for the perturbation tolerance δ to be chosen appropriately. In the revised version we will add the modeling assumption that each valuation satisfies max_{i,j} |v_{i j}| ≤ 1. This is the natural normalization for mixed goods and chores (where valuations may be negative) and ensures that the initial containing ball has radius R = O(n m) that is polynomial in the input size. With this change the iteration bound O(d² log(R/r)) becomes polynomial, and the argument that a sufficiently small polytope implies the center-derived allocation is fair carries through by scaling δ relative to the normalization. We will also update the abstract, the general framework section, and the relevant theorems to reflect the assumption. revision: yes

Circularity Check

0 steps flagged

No circularity: standard ellipsoid method on feedback-defined polytope with independent separation oracle.

full rationale

The paper's core derivation maintains a polytope of valuations consistent with observed fairness-violation feedback and uses those violations to supply separating hyperplanes, thereby emulating the ellipsoid method to shrink the polytope until a center yields an EF1/PROP1 allocation for the unknown true valuation. This is a direct, non-circular application of the ellipsoid method (with a separation oracle supplied by the feedback model) to a convex feasibility problem whose feasible region is defined externally by the true valuations. No step equates the target fairness guarantee to a fitted parameter, renames a known result, or reduces the polynomial-time claim to a self-citation chain. The monotone-EF1 result similarly rests on a non-constructive existence argument plus the same ellipsoid framework rather than any definitional loop. The absence of explicit normalization bounds affects the concrete polynomial degree but does not create circularity in the derivation itself.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on domain assumptions about valuation classes and standard mathematical tools; no free parameters or invented entities are introduced.

axioms (2)

domain assumption Valuations are additive (value of a bundle equals sum of item values) or monotone (adding an item never decreases value)
Results are stated separately for each class; the monotone case further restricts candidate allocations to interval-plus-one forms.
standard math Feedback on a fairness violation supplies a valid separating hyperplane for the polytope of consistent valuations
Central to the ellipsoid-emulation argument in both additive and monotone cases.

pith-pipeline@v0.9.1-grok · 5833 in / 1278 out tokens · 49877 ms · 2026-07-01T03:32:58.611497+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

21 extracted references · 4 canonical work pages

[1]

Dana Angluin

Queries and Concept Learning.Machine Learning2 (1988), 319–342. Dana Angluin

1988
[2]

Pranjal Awasthi and Reza Bosagh Zadeh

Local Algorithms for Interactive Clustering.Journal of Machine Learning Research18 (2017), 1–35. Pranjal Awasthi and Reza Bosagh Zadeh

2017
[3]

Fair Allocation of Indivisible Goods and Chores. Proc. 21st Intl. Conf. on Autonomous Agents and Multiagent Systems36, 1 (2022), 3:1–3:21. https://doi.org/10.1007/s10458- 021-09547-9 Maria-Florina Balcan and Avrim Blum

work page doi:10.1007/s10458- 2022
[4]

36th Advances in Neural Information Processing Systems35 (2022), 3703–3715

Dynamic fair division with partial information.Proc. 36th Advances in Neural Information Processing Systems35 (2022), 3703–3715. Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker

2022
[5]

https://doi.org/10.1016/j.geb.2021.09.009 Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, and Biaoshuai Tao

Almost Envy-Free Allocations with Connected Bundles.Games and Economic Behavior 131 (2022), 197–221. https://doi.org/10.1016/j.geb.2021.09.009 Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, and Biaoshuai Tao

work page doi:10.1016/j.geb.2021.09.009 2022
[6]

Journal of Political Economy119, 6 (2011), 1061–1103

The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy119, 6 (2011), 1061–1103. https://doi.org/10.1086/664613 Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019a. Envy-Freeness up to Any Item with High Nash Welfare: The Virtue of Donating Items. InProc. 20th ACM Conf. on Economics and...

work page doi:10.1086/664613 2011
[7]

https://doi.org/10.1137/20M1321735 Maxime C

A Little Charity Guarantees Almost Envy-Freeness.SIAM Journal on Discrete Mathematics50, 4 (2021), 1336–1358. https://doi.org/10.1137/20M1321735 Maxime C. Cohen, Ilan Lobel, and Renato Paes Leme

work page doi:10.1137/20m1321735 2021
[8]

Vincent Conitzer, Rupert Freeman, and Nisarg Shah

Feature-Based Dynamic Pricing.Management Science66, 11 (2020), 4921–4943. Vincent Conitzer, Rupert Freeman, and Nisarg Shah

2020
[9]

Low communication protocols for fair allocation of indivisible goods. InProc. 26th ACM Conf. on Economics and Computation. 358–382. Martin Grötschel, László Lovász, and Alexander Schrijver. 1981.The Ellipsoid Method and Its Consequences in Combinatorial Optimization. Vol

1981
[10]

Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert E

A polynomial algorithm in linear programming.Soviet Mathematics Doklady20 (1979), 191–194. Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert E. Schapire

1979
[11]

Zihan Li, Pasin Manurangsi, Jonathan Scarlett, and Warut Suksompong

Contextual Search in the Presence of Adversarial Corruptions.Operations Research71, 4 (2023), 1120–1135. Zihan Li, Pasin Manurangsi, Jonathan Scarlett, and Warut Suksompong

2023
[12]

Ilan Lobel, Renato Paes Leme, and Adrian Vladu

Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm.Machine Learning2, 4 (1988), 285–318. Ilan Lobel, Renato Paes Leme, and Adrian Vladu

1988
[13]

Operations Research66, 5 (2018), 1346–1361

Multidimensional Binary Search for Contextual Decision-Making. Operations Research66, 5 (2018), 1346–1361. Evi Micha and Vasilis Varsamis

2018
[14]

Renato Paes Leme and Jon Schneider

Fairly allocating many goods with few queries.SIAM Journal on Discrete Mathematics35, 2 (2021), 788–813. Renato Paes Leme and Jon Schneider

2021
[15]

Comput.51, 4 (2022), 1096–1125

Contextual Search via Intrinsic Volumes.SIAM J. Comput.51, 4 (2022), 1096–1125. Benjamin Plaut and Tim Roughgarden

2022
[16]

Pannaga Shivaswamy and Thorsten Joachims

Almost envy-freeness with general valuations.SIAM Journal on Discrete Mathematics34, 2 (2020), 1039–1068. Pannaga Shivaswamy and Thorsten Joachims

2020
[17]

Walter Stromquist

Coactive learning.Journal of Artificial Intelligence Research53 (2015), 1–40. Walter Stromquist

2015
[18]

Francis E

How to cut a cake fairly.The American Mathematical Monthly87, 8 (1980), 640–644. Francis E. Su

1980
[19]

Rental harmony: Sperner’s lemma in fair division.The American Mathematical Monthly106, 10 (1999), 930–942. Aaron D. Tucker, Kianté Brantley, Adam Cahall, and Thorsten Joachims

1999
[20]

Correctness and termination follow by the same ellipsoid-based argument as for EF1 and PROP1

as a black box. Correctness and termination follow by the same ellipsoid-based argument as for EF1 and PROP1. Theorem 8.Under additive valuations in the goods setting, Algorithm 5 terminates after poly(𝑛, 𝑚) rounds of proposed allocations. Its total running time is pseudo-polynomial, dominated by the calls to the EFX-with-bounded-charity subroutine of Cha...

2021
[21]

Since 𝑝𝑡 is symmetric and unimodal (increasing up to the mode(s) and then decreasing), the quantity 𝑝𝑘 +𝑝 𝑘+1 is maximized when {𝑘, 𝑘+1 } is centered at the mode(s)

Write 𝑝𝑡 :=P[𝑋=𝑡]= 𝑠 𝑡 · 2−𝑠. Since 𝑝𝑡 is symmetric and unimodal (increasing up to the mode(s) and then decreasing), the quantity 𝑝𝑘 +𝑝 𝑘+1 is maximized when {𝑘, 𝑘+1 } is centered at the mode(s). Thus the maximum over𝑘equals 𝑀𝑠 :=max 𝑘 (𝑝𝑘 +𝑝 𝑘+1 )=    2𝑟 𝑟−1 + 2𝑟 𝑟 ·2 −2𝑟 , 𝑠=2𝑟, 2𝑟+1 𝑟 + 2𝑟+1 𝑟+1 ·2 − (2𝑟+1) , 𝑠=2𝑟+1. For the even case𝑠=2𝑟, note ...

2021

[1] [1]

Dana Angluin

Queries and Concept Learning.Machine Learning2 (1988), 319–342. Dana Angluin

1988

[2] [2]

Pranjal Awasthi and Reza Bosagh Zadeh

Local Algorithms for Interactive Clustering.Journal of Machine Learning Research18 (2017), 1–35. Pranjal Awasthi and Reza Bosagh Zadeh

2017

[3] [3]

Fair Allocation of Indivisible Goods and Chores. Proc. 21st Intl. Conf. on Autonomous Agents and Multiagent Systems36, 1 (2022), 3:1–3:21. https://doi.org/10.1007/s10458- 021-09547-9 Maria-Florina Balcan and Avrim Blum

work page doi:10.1007/s10458- 2022

[4] [4]

36th Advances in Neural Information Processing Systems35 (2022), 3703–3715

Dynamic fair division with partial information.Proc. 36th Advances in Neural Information Processing Systems35 (2022), 3703–3715. Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker

2022

[5] [5]

https://doi.org/10.1016/j.geb.2021.09.009 Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, and Biaoshuai Tao

Almost Envy-Free Allocations with Connected Bundles.Games and Economic Behavior 131 (2022), 197–221. https://doi.org/10.1016/j.geb.2021.09.009 Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, and Biaoshuai Tao

work page doi:10.1016/j.geb.2021.09.009 2022

[6] [6]

Journal of Political Economy119, 6 (2011), 1061–1103

The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy119, 6 (2011), 1061–1103. https://doi.org/10.1086/664613 Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019a. Envy-Freeness up to Any Item with High Nash Welfare: The Virtue of Donating Items. InProc. 20th ACM Conf. on Economics and...

work page doi:10.1086/664613 2011

[7] [7]

https://doi.org/10.1137/20M1321735 Maxime C

A Little Charity Guarantees Almost Envy-Freeness.SIAM Journal on Discrete Mathematics50, 4 (2021), 1336–1358. https://doi.org/10.1137/20M1321735 Maxime C. Cohen, Ilan Lobel, and Renato Paes Leme

work page doi:10.1137/20m1321735 2021

[8] [8]

Vincent Conitzer, Rupert Freeman, and Nisarg Shah

Feature-Based Dynamic Pricing.Management Science66, 11 (2020), 4921–4943. Vincent Conitzer, Rupert Freeman, and Nisarg Shah

2020

[9] [9]

Low communication protocols for fair allocation of indivisible goods. InProc. 26th ACM Conf. on Economics and Computation. 358–382. Martin Grötschel, László Lovász, and Alexander Schrijver. 1981.The Ellipsoid Method and Its Consequences in Combinatorial Optimization. Vol

1981

[10] [10]

Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert E

A polynomial algorithm in linear programming.Soviet Mathematics Doklady20 (1979), 191–194. Akshay Krishnamurthy, Thodoris Lykouris, Chara Podimata, and Robert E. Schapire

1979

[11] [11]

Zihan Li, Pasin Manurangsi, Jonathan Scarlett, and Warut Suksompong

Contextual Search in the Presence of Adversarial Corruptions.Operations Research71, 4 (2023), 1120–1135. Zihan Li, Pasin Manurangsi, Jonathan Scarlett, and Warut Suksompong

2023

[12] [12]

Ilan Lobel, Renato Paes Leme, and Adrian Vladu

Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm.Machine Learning2, 4 (1988), 285–318. Ilan Lobel, Renato Paes Leme, and Adrian Vladu

1988

[13] [13]

Operations Research66, 5 (2018), 1346–1361

Multidimensional Binary Search for Contextual Decision-Making. Operations Research66, 5 (2018), 1346–1361. Evi Micha and Vasilis Varsamis

2018

[14] [14]

Renato Paes Leme and Jon Schneider

Fairly allocating many goods with few queries.SIAM Journal on Discrete Mathematics35, 2 (2021), 788–813. Renato Paes Leme and Jon Schneider

2021

[15] [15]

Comput.51, 4 (2022), 1096–1125

Contextual Search via Intrinsic Volumes.SIAM J. Comput.51, 4 (2022), 1096–1125. Benjamin Plaut and Tim Roughgarden

2022

[16] [16]

Pannaga Shivaswamy and Thorsten Joachims

Almost envy-freeness with general valuations.SIAM Journal on Discrete Mathematics34, 2 (2020), 1039–1068. Pannaga Shivaswamy and Thorsten Joachims

2020

[17] [17]

Walter Stromquist

Coactive learning.Journal of Artificial Intelligence Research53 (2015), 1–40. Walter Stromquist

2015

[18] [18]

Francis E

How to cut a cake fairly.The American Mathematical Monthly87, 8 (1980), 640–644. Francis E. Su

1980

[19] [19]

Rental harmony: Sperner’s lemma in fair division.The American Mathematical Monthly106, 10 (1999), 930–942. Aaron D. Tucker, Kianté Brantley, Adam Cahall, and Thorsten Joachims

1999

[20] [20]

Correctness and termination follow by the same ellipsoid-based argument as for EF1 and PROP1

as a black box. Correctness and termination follow by the same ellipsoid-based argument as for EF1 and PROP1. Theorem 8.Under additive valuations in the goods setting, Algorithm 5 terminates after poly(𝑛, 𝑚) rounds of proposed allocations. Its total running time is pseudo-polynomial, dominated by the calls to the EFX-with-bounded-charity subroutine of Cha...

2021

[21] [21]

Since 𝑝𝑡 is symmetric and unimodal (increasing up to the mode(s) and then decreasing), the quantity 𝑝𝑘 +𝑝 𝑘+1 is maximized when {𝑘, 𝑘+1 } is centered at the mode(s)

Write 𝑝𝑡 :=P[𝑋=𝑡]= 𝑠 𝑡 · 2−𝑠. Since 𝑝𝑡 is symmetric and unimodal (increasing up to the mode(s) and then decreasing), the quantity 𝑝𝑘 +𝑝 𝑘+1 is maximized when {𝑘, 𝑘+1 } is centered at the mode(s). Thus the maximum over𝑘equals 𝑀𝑠 :=max 𝑘 (𝑝𝑘 +𝑝 𝑘+1 )=    2𝑟 𝑟−1 + 2𝑟 𝑟 ·2 −2𝑟 , 𝑠=2𝑟, 2𝑟+1 𝑟 + 2𝑟+1 𝑟+1 ·2 − (2𝑟+1) , 𝑠=2𝑟+1. For the even case𝑠=2𝑟, note ...

2021