Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies an online allocation setting where arriving items
are allocated among $n$ agents who are "promised" a prespecified
fraction of the items. The goal of the planner is to maximize the
agents' total valuation. As opposed to the standard setting, the
planner not only does not know the realized valuation at each period,
but also the distribution of the values (which are assumed to be iid
across agents and time). Furthermore, the agents are strategic and
misreport their values to affect future allocations. The paper
proposes an online-learning based allocation mechanism that is
approximately BIC and achieves sublinear regret (under truthful
reporting) against the optimal allocation policy that knows the
distribution.

strengths_and_weaknesses: The paper studies an important resource allocation problem inspired
from practical considerations, and proposes a mechanism to decrease
the informational requirements on the planner. If the common iid
distribution were known to the planner, the paper shows that the
problem reduces to an offline optimization problem related to an
optimal transport problem, whose solution is parametrized by the dual
variables $\lambda$. Thus, the online problem is reduced to learning
the optimal dual values $\lambda$ from the reports, while ensuring
that the reports remain truthful.

The main insight behind the mechanism is to use the reports of other
agents to detect if an agent is reporting truthfully, and if not, stop
the allocation. This uses the fact that the valuation distributions
are not only independent, but also identical, a major weakness of the
approach in terms of its applicability. This approach also bears
similarity to implementation theory (Caillaud & Roberts 2005, Maskin
1998), and the reader would be helped by connecting to this
literature.

To summarize, the paper proposes an interesting mechanism to overcome
the ignorance of the valuation distribution. However, this approach is
somewhat hampered by its reliance on the iid assumption. In
particular, the approach fails even if the valuation distribution is
independent but not identical. 


Terminology: The abstract as well as the introduction characterizes
the contribution as achieving near-optimal regret against the "optimal
offline allocation policy". This is somewhat imprecise, as the offline
policy can be construed as one that knows the instance (for instance,
in the definition of competitive ratio). However, the guarantees are
against the "offline policy" that knows the distribution but not the
realization. Perhaps a more explicit terminology might be useful.
questions: While the offline problem requires that the allocation satisfy the
promised fraction $p_i^*$ exactly, there is no specific constraint
placed on the online problem. In particular, while the algorithm
ensures that all but one agent's allocation is below the capacity
$p_i^* T$, is it possible to show that the allocations of all agents
are close to $p_i^*T$, given the regret bounds?
limitations: None
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies a repeated online allocation of a single type of good to agents who have the same but unknown valuation distribution for the good. Unlike the prior work, the paper assumes the agents are strategic and no monetary payments can be used to incentivize truthfulness.  The goal of the allocation is to maximize social welfare. The paper provides an algorithm that satisfies approximate Bayesian incentive compatibility (i.e. no single agent can deviate from truthfulness to gain much if the other agents are truthful) and also achieves no regret (the social welfare will approach the highest possible welfare as the number of allocation rounds goes to infinity).
strengths_and_weaknesses: -------------------------------------
Strengths:
-------------------------------------
-- The paper studies a novel allocation setting where strategic interactions are allowed by the agents but the allocator cannot use payments to incentivize truthfulness.

-- The exposition and presentation of the paper were excellent. The setting was clearly discussed. And the high-level ideas of the algorithms/proofs can be easily followed throughout the paper. 

-------------------------------------
Weaknesses:
-------------------------------------
-- The setting of the paper is rather strange. Unlike the traditional online learning setting, there is no immediate feedback to the allocator on the quality of the allocation at each round. Hence, I am not sure about the applicability of the results in any interesting domains.

-- The analysis does not seem to provide any interesting insights. The paper is interested in enforcing Bayesian incentive compatibility and the authors compare the reported bids of any specific user to the rest to check whether the user is untruthful (given that the users all have the same valuation distribution). This might be okay if to goal is to detect untruthfulness. But the mechanism simply stops if untruthfulness is detected. The analysis of the regret is only for the case that all agents are truthful. This also significantly weakens the guarantees provided by the paper. 
questions: -- Can the authors propose a motivating example to justify repeated strategic interactions where monetary compensation is not allowed to incentivize truthfulness? 

-- Can the authors provide more insight on how the offline optimal allocation is solved? Does this require new tools or the problem has been solved by prior work? Why the allocation is called "Greedy" in Definition 1?

-- The regret over all agents grow as $n\sqrt{nT}$. Is this standard? Are there any lower bounds?

-------------------------------------
Minor comments:
-------------------------------------
-- Please sort the numbers for the references (e.g., line 27) in the paper.

-- Change "Literature Review" to "Literature review" to be consistent with other section headers.

-- Is there any reason to have an upper bound of $\bar{x}$ for valuations instead of 1?
limitations: The discussion of the limitations is sufficient.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work considers an online allocation problem with learning and strategic agents. Previous works already studied this problem, but proposed BIC policies either using payments/transfers between the players and the central planner, or assuming that the planner knows beforehand the valuation distribution of the players. This work is thus the first to propose an approximate BIC policy, with sublinear regret, when neither of these conditions hold.

--------

After the discussion with the authors and reviewers, I decided to raise my score as I believe this paper to be well written and to deal with an interesting problem. As suggested in the discussion with the authors, I think that adding a rigorous result stating that a no regret BIC policy cannot be derived in the heterogeneous setting without further assumption.
strengths_and_weaknesses: I find this work interesting and overall well written. The considered problem is of interest, since the central planner might have very small leverages in real life situations when allocating resources to multiple agents.

The proposed algorithm is rather simple and natural. It mostly relies on the DKW concentration inequality.

As a main weakness, the proposed algorithm crucially relies on the fact that the players are homogeneous, ie have the same valuation distribution. The case of heterogeneous seems much harder as mentioned by the authors in the conclusion. Actually, I believe that some impossibility result can be shown for heterogeneous players when the player neither knows the players' distribution nor can use payments. Showing such a result would significantly support this work (and I believe it is not that hard).
For a similar reason, the main result claims that truthful bidding by the players is an approximate Nash equilibrium, but I would believe that drastically different strategies could also be approximate Nash equilibria (actually almost any strategy where the players report the same fake distribution).

A second concern I have: the current paper is lacking some theoretical guarantee on how the repartition of the items by the central planner respects the predetermined fraction p_i^*. Having some guarantee on the differences between p_i^* and \hat{p}_i would make the analysis of the policy complete in my opinion.
questions: My main questions to the authors are related to my concerns mentioned above:

1) Could you show some impossibility result on the heterogeneous case (without payment or distribution knowledge), or do you believe that a good BIC policy is possible in that case?
2) Can you show some guarantees on the respect of the predetermined fractions p_i^* ?

I also have some other questions:
3) The proposed policy is robust to the deviation of a single player. It even seems it could be extended to the possible deviation of a significant fraction of players (eg as in the Byzantine problem). It however might lead to considerable computational costs. Could you develop on this point?

----- Minor comments -----

4) After Definition 2, it could be great to relate the notion of Approximate-BIC to approximate-Nash equilibria
5) The algorithm works in epochs of doubling sizes. Why is it needed? It seems the same algorithm could work with constant epoch size 1 (eg anytime)?

limitations: No concern
review_title: null

Meta-review: metareview: Executive summary:

The authors study the repeated allocation of an identical good over T rounds to n strategic buyers in a "no monetary transfers" setting. The buyers have i.i.d. valuations drawn from an unknown distribution, and the algorithm must work with reported valuations. The goal is to maximize social welfare (= sum of valuations) under the constraint that each buyer receives a pre-specified fraction of the total number of goods. 

The main result is an algorithm for this problem that ensures two things: 

(a) approximate Bayesian incentive compatibility (approx-BIC) (Definition 2 and Theorem 1) and 

(b) low individual regret (Definition 3 and Theorem 2). 

The key idea of the algorithm (is to exploit the iid-ness of the problem) and detect misreports from the underlying CDF using Dvoretzky-Kiefer-Wolfowitz type bounds.

Discussion and recommendation:

After some initial set back on the problem motivation, the reviewers bought into the motivation for studying this online allocation problem "without monetary transfers" (adding examples such as the foodbank example might be good).  

There was some discussion around "assuming iid valuations" limiting the generality of the result, but there is in fact a history of papers that studies learning with strategic agents under this assumption (eg Kanoria and Nazerzadeh 2021).

The main difference of the current work is that it's working in a setting without money.

The idea behind the algorithm is maybe "the obvious think to do" - but of course it still requires some work to formally prove that it actually works. 

I think one thing that could strengthen the paper would be to add some discussion around the tightness/non-tightness of the approximate BIC and individual regret bounds.

Weak accept.
confidence: Less certain
Decision: Accept