2025-07-17 | | Total: 9
This paper explores the economic interactions within modern crowdsourcing markets. In these markets, employers issue requests for tasks, platforms facilitate the recruitment of crowd workers, and workers complete tasks for monetary rewards. Recognizing that these roles serve distinct functions within the ecosystem, we introduce a three-party model that distinguishes among the principal (the requester), the intermediary (the platform), and the pool of agents (the workers). The principal, unable to directly engage with agents, relies on the intermediary to recruit and incentivize them. This interaction unfolds in two stages: first, the principal designs a profit-sharing contract with the intermediary; second, the intermediary implements a mechanism to select an agent to complete the delegated task. We analyze the proposed model as an extensive-form Stackelberg game. Our contributions are fourfold: (1) We fully characterize the subgame perfect equilibrium. In particular, we reduce the principal's contract design problem to a novel auction-theoretic formulation we term virtual value pricing, and reveals that linear contracts are optimal even when the task have multiple outcomes and agents' cost distributions are asymmetric. (2) To quantify the principal's utility loss from delegation and information asymmetry, we introduce the price of double marginalization (PoDM) and the classical price of anarchy (PoA), and derive tight or nearly tight bounds on both ratios under regular and monotone hazard rate (MHR) distributions. (3) We further examine these two ratios in a natural setting where the intermediary is restricted to anonymous pricing mechanisms, and show that similar qualitative insights continue to hold. (4) Finally, we extend our results on both ratios to a robust framework that accommodates scenarios in which the principal lacks precise information about the market size.
In this work, we examine a sequential setting of a cooperative game in which players arrive dynamically to form coalitions and complete tasks either together or individually, depending on the value created. Upon arrival, a new player as a decision maker faces two options: forming a new coalition or joining an existing one. We assume that players are greedy, i.e., they aim to maximize their rewards based on the information available at their arrival. The objective is to design an online value distribution policy that incentivizes players to form a coalition structure that maximizes social welfare. We focus on monotone and bounded cooperative games. Our main result establishes an upper bound of $\frac{3\mathsf{min}}{\mathsf{max}}$ on the competitive ratio for any irrevocable policy (i.e., one without redistribution), and proposes a policy that achieves a near-optimal competitive ratio of $\min\left\{\frac{1}{2}, \frac{3\mathsf{min}}{\mathsf{max}}\right\}$, where $\mathsf{min}$ and $\mathsf{max}$ denote the smallest and largest marginal contribution of any sub-coalition of players respectively. Finally, we also consider non-irrevocable policies, with alternative bounds only when the number of players is limited.
This study introduces the \emph{edge-based Shapley value}, a novel allocation rule within cooperative game theory, specifically tailored for networked systems, where value is generated through interactions represented by edges. Traditional allocation rules, such as the Shapley and Myerson values, evaluate player contributions based on node-level characteristics, or connected components. However, these approaches often fail to adequately capture the functional role of edges, which are crucial in systems such as supply chains and digital platforms, where interactions, rather than individual agents, are the primary drivers of value. Our edge-based Shapley value shifts the characteristic function from node sets to edge sets, thereby enabling a more granular and context-sensitive evaluation of the contributions. We establish its theoretical foundations, demonstrate its relationship to classical allocation rules, and show that it retains key properties such as fairness and symmetry. To illustrate its applicability, we present two use cases: content platform networks and supply chain logistics (SCL). In both cases, our method produces intuitive and structurally consistent allocations, particularly in scenarios with overlapping routes, exclusive contracts or cost-sensitive paths. This framework offers a new perspective on value attribution in cooperative settings with complex interaction structures and provides practical tools for analyzing real-world economic and logistical networks.
Federated learning (FL) enables collaborative model training across decentralized clients while preserving data privacy. However, its open-participation nature exposes it to data-poisoning attacks, in which malicious actors submit corrupted model updates to degrade the global model. Existing defenses are often reactive, relying on statistical aggregation rules that can be computationally expensive and that typically assume an honest majority. This paper introduces a proactive, economic defense: a lightweight Bayesian incentive mechanism that makes malicious behavior economically irrational. Each training round is modeled as a Bayesian game of incomplete information in which the server, acting as the principal, uses a small, private validation dataset to verify update quality before issuing payments. The design satisfies Individual Rationality (IR) for benevolent clients, ensuring their participation is profitable, and Incentive Compatibility (IC), making poisoning an economically dominated strategy. Extensive experiments on non-IID partitions of MNIST and FashionMNIST demonstrate robustness: with 50% label-flipping adversaries on MNIST, the mechanism maintains 96.7% accuracy, only 0.3 percentage points lower than in a scenario with 30% label-flipping adversaries. This outcome is 51.7 percentage points better than standard FedAvg, which collapses under the same 50% attack. The mechanism is computationally light, budget-bounded, and readily integrates into existing FL frameworks, offering a practical route to economically robust and sustainable FL ecosystems.
We consider the algorithmic challenge that is faced by blockchains that have multidimensional block constraints and serve quasi-patient bidders. We provide online approximation algorithms for this problem, thus solving open problems left by [Babaioff and Nisan, EC 2025].
We show that if the ground set of a matroid can be partitioned into $k\ge 2$ bases, then for any given subset $S$ of the ground set, there is a partition into $k$ bases such that the sizes of the intersections of the bases with $S$ may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabó (Electron.~J.~Comb.~2011) in the affirmative. We also investigate equitable splittings of two disjoint sets $S_1$ and $S_2$, and show that there is a partition into $k$ bases such that the sizes of the intersections with $S_1$ may differ by at most one and the sizes of the intersections with $S_2$ may differ by at most two; this is the best possible one can hope for arbitrary matroids. We also derive applications of this result into matroid constrained fair division problems. We show that there exists a matroid-constrained fair division that is envy-free up to 1 item if the valuations are identical and tri-valued additive. We also show that for bi-valued additive valuations, there exists a matroid-constrained allocation that provides everyone their maximin share.
In many applications, decision-makers must choose between multiple predictive models that may all be miscalibrated. Which model (i.e., predictor) is more "useful" in downstream decision tasks? To answer this, our first contribution introduces the notion of the informativeness gap between any two predictors, defined as the maximum normalized payoff advantage one predictor offers over the other across all decision-making tasks. Our framework strictly generalizes several existing notions: it subsumes U-Calibration [KLST-23] and Calibration Decision Loss [HW-24], which compare a miscalibrated predictor to its calibrated counterpart, and it recovers Blackwell informativeness [Bla-51, Bla-53] as a special case when both predictors are perfectly calibrated. Our second contribution is a dual characterization of the informativeness gap, which gives rise to a natural informativeness measure that can be viewed as a relaxed variant of the earth mover's distance (EMD) between two prediction distributions. We show that this measure satisfies natural desiderata: it is complete and sound, and it can be estimated sample-efficiently in the prediction-only access setting. Along the way, we also obtain novel combinatorial structural results when applying this measure to perfectly calibrated predictors.
The donation game is a well-established framework for studying the emergence and evolution of cooperation in multi-agent systems. The cooperative behavior can be influenced by the environmental noise in partially observable settings and by the decision-making strategies of agents, which may incorporate not only reputation but also traits such as generosity and forgiveness. Traditional simulations often assume fully random interactions, where cooperation is tested between randomly selected agent pairs. In this paper, we investigate cooperation dynamics using the concept of Stephen Wolfram's one-dimensional binary cellular automata. This approach allows us to explore how cooperation evolves when interactions are limited to neighboring agents. We define binary cellular automata rules that conform to the donation game mechanics. Additionally, we introduce models of perceptual and action noise, along with a mutation matrix governing the probabilistic evolution of agent strategies. Our empirical results demonstrate that cooperation is significantly affected by agents' mobility and their spatial locality on the game board. These findings highlight the importance of distinguishing between entirely random multi-agent systems and those in which agents are more likely to interact with their nearest neighbors.
This article introduces a software package release for geometrically reasoning about the \textit{safety} desiderata of (complex) dynamical systems via level set methods. In emphasis, safety is analyzed with Hamilton-Jacobi equations. In scope, we provide implementations of numerical algorithms for the resolution of Hamilton-Jacobi-Isaacs equations: the spatial derivatives of the associated value function via upwinding, the Hamiltonian via Lax-Friedrichs schemes, and the integration of the Hamilton-Jacobi equation altogether via total variation diminishing Runge-Kutta schemes. Since computational speed and interoperability with other modern scientific computing libraries (typically written in the Python language) is of essence, we capitalize on modern computational frameworks such as \texttt{CUPY} and \texttt{NUMPY} and move heavy computations to GPU devices to aid parallelization and improve bring-up time in safety analysis. We hope that this package can aid users to quickly iterate on ideas and evaluate all possible safety desiderata of a system via geometrical simulation in modern engineering problems.