Dynamic Allocation of Public Goods with Approximate Core Equilibria

Chido Onyeze, David X. Lin, Siddhartha Banerjee, Éva Tardos · 2025

Read Dynamic Allocation of Public Goods with Approximate Core Equilibria by Chido Onyeze, David X. Lin, Siddhartha Banerjee, Éva Tardos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-04817.txt.

Introduction

Chido Onyeze leads four authors allocating shared public goods over time without money. Several shareable goods have limited availability, and agents arrive with values each period. Values are drawn from a possibly correlated distribution across agents.

A global limit, written as a submodular cost, caps which goods the principal can offer overall. The goal is high value for every group of agents, not just the total. Their mechanisms hand each agent an artificial currency budget sized to its group. Spending that currency across periods steers allocations toward outcomes close to core equilibria.

Catalog record

CREATORChido Onyeze, David X. Lin, Siddhartha Banerjee, Éva Tardos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE168 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-04817

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dynamic Allocation of Public Goods with Approximate Core Equilibria Thanks: Chido Onyeze, David X. Lin, and Siddhartha Banerjee were supported by NSF grant ECCS-1847393 and through a SPROUT Award from Cornell Engineering. Éva Tardos was supported in part by ONR MURI grant N000142412742. Chido Onyeze, David X. Lin, Siddhartha Banerjee, Éva Tardos Abstract We consider the problem of repeatedly allocating multiple shareable public goods that have limited availability in an online setting without the use of money. In our setting, agents have additive values, and the value each agent receives from getting access to the goods in each period is drawn i.i.d. from some joint distribution 𝒟 \mathcal{D} (that can be arbitrarily correlated between agents). The principal also has global constraints on the set of goods they can select over the horizon, which is represented via a submodular allocation-cost function. Our goal is to select the periods to allocate the good to ensure high value for each group of agents. We develop mechanisms for this problem using an artificial currency, where we give each agent a budget proportional to their (exogenous) fair share. The correlated value distribution makes this an especially challenging problem, as agents may attempt to free-ride by declaring low valuations for the good when they know other agents have high values—hoping those agents will bear a larger share of the cost of the resource. We offer a black-box reduction from monetary mechanisms for the allocation of a costly excludable public good. We focus on pacing strategies, the natural strategies when using AI agents, where agents report a scaled version of their value to the mechanism. Our main results show that when using a truthful monetary mechanism as our building block, the resulting online mechanism has a focal equilibrium in which each agent plays a pacing strategy whose outcome results in an allocation that is a ( ℋ n − 1 ) (\mathcal{H}_{n}-1) - approximation of the core , where ℋ n \mathcal{H}_{n} is the Harmonic number, and n n is the number of players. Remarkably, we are able to achieve an approximate core solution as a Nash outcome without explicit collaboration or coordination between the agents. With the agents’ values in incomparable units, comparing the Nash outcome to the core is a reasonable measure of both efficiency and fairness. 1 Introduction Consider a set of resources shared over multiple periods between a set of agents – for example, a scientific instrument like a telescope shared by several researchers. There is a large recent literature on mechanisms allocating such a resource to one user at-a-time, in a way that is both fair and efficient, and without using money (as is desirable for shared resources like scientific instruments). These works crucially assume that the resource in each period can benefit only one user. However many research groups may be interested in having access to telescope data. This brings us into the domain of public goods allocation , a cornerstone of microeconomics and the source of some of the most famous impossibility theorems in the field. When monetary transfers are allowed, allocating even a single public good raises challenges not present with private goods: users may be tempted to free ride , declaring low valuations in hope that others bear all costs. Given a resource of cost c and users with private values V_{i} for accessing it, the ‘first-best’ decision (i.e., with full information) is to allocate the resource if \sum_{i}V_{i}\geq c , and make users pay enough to cover the cost. However, it is known that due to free-riding, any mechanism can have arbitrarily bad welfare compared to this solution. The situation is improved when one can exclude some users (for example, by delaying the sharing of data to some set of agents); in this case, we know truthful monetary mechanisms (due to [ 26 ] for a single good, and [ 12 ] for multiple) that get the best possible approximation of the first-best welfare. In this work, we consider the problem of designing non-monetary mechanisms for the repeated allocation of excludable public goods. Section 2 provides a formal model, but at high level, and focusing first on the simpler setting of a single public good per round, our setting is as follows: Over a horizon of T periods, a principal is tasked with allocating (or not) a public good in each period among n agents. If the principal chooses to allocate the good in any period, they can further specify which subset of agents get access to the good. The principal is constrained to allocate in at most \alpha T periods (for some \alpha\leq 1 , for example, due to limited finance, or energy consumption constraints). Each agent i has private valuation V_{i}[t] for the good in period t . The values are drawn i.i.d. across periods t\in[T] from some joint distribution \mathcal{D} , that may be arbitrarily correlated between agents. An agent’s ex-post utility is the average of the total value she receives from periods in which she is given access to the good. More generally, we allow for multiple items to be allocated in each period, with the agent utilities and global allocation constraints depending both on the items allocated and the set of users who get access to the items in each period. To model heterogeneous influence of each agent in allocation decisions, we assume each agent i is associated with an exogenous share \alpha_{i} ; setting all \alpha_{i} equal means agents have equal influence. The goal of the principal is to select an allocation that satisfies global allocation constraints, and is both efficient (resulting in high ex-post utility for agents) and fair with respect to agents’ shares; however, it is not clear how one can quantify these notions in a public goods setting. Each individual agent is of course self-serving, and so some mechanism is required to incentivize them to reveal their preferences. With values coming from a possibly highly correlated distribution \mathcal{D} , free riding is a major concern. Finally, one would like the mechanism to be simple and practical, and detail-free (in particular, agnostic of \mathcal{D} ). Our work tackles these by combining two ideas: (approximate) core outcomes and pseudomarkets . The former gives a benchmark for quantifying allocation quality in terms of how well they satisfy any potential coalition of blocking agents. The latter lets us take a monetary mechanism \mathcal{M} for one-shot public goods allocation, and use it in a black-box way for repeated non-monetary allocation: We give each agent i a budget of \alpha_{i}T artificial credits and ask them to use this currency to participate in \mathcal{M} in each round to determine allocations. In this context, we study a class of simple value-scaling policies, where each agent i reports value V_{i}[t]/\beta_{i} in period t for some chosen \beta_{i} ; these have attracted particular recent interest, as one can think of them as the outcome of using auto-bidders, with \beta_{i} being optimized to help agents optimally use their budgets. Our main result shows that value-scaling policies admit a Nash equilibrium which results in a strong core approximation : when using monetary mechanism \mathcal{M} , we show the resulting core approximation factor equals the Dead-Weight Loss (i.e., the difference between

Read the complete text