An official website of the United States government
We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent’s own history of play and requires no foreknowledge of the firms’ preferences.Our algorithms are constructed by splitting up the statistical problem of learning one’s preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur a regret which grows at most logarithmically in the time horizon. However, we note that in the worst case, it may grow exponentially in the size of the market.
more »
« less
Capacity Modification in the Stable Matching Problem
We study the problem of capacity modification in the many-to-one stable matching of workers and firms. Our goal is to systematically study how the set of stable matchings changes when some seats are added to or removed from the firms. We make three main contributions: First, we examine whether firms and workers can improve or worsen upon changing the capacities under worker-proposing and firm-proposing deferred acceptance algorithms. Second, we study the computational problem of adding or removing seats to either match a fixed worker-firm pair in some stable matching or make a fixed matching stable with respect to the modified problem. We develop polynomial-time algorithms for these problems when only the overall change in the firms’ capacities is restricted, and show NP-hardness when there are additional constraints for individual firms. Lastly, we compare capacity modification with the classical model of preference manipulation by firms and identify scenarios under which one mode of manipulation outperforms the other. We find that a threshold on a given firm’s capacity, which we call its peak, crucially determines the effectiveness of different manipulation actions.
more »
« less
- Award ID(s):
- 1928930
- PAR ID:
- 10529360
- Publisher / Repository:
- International Foundation for Autonomous Agents and Multiagent Systems
- Date Published:
- Edition / Version:
- AAMAS '24
- ISBN:
- 979-8-4007-0486-4
- Page Range / eLocation ID:
- 697-705
- Format(s):
- Medium: X
- Location:
- Auckland, New Zealand
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract This article analyzes how patent-induced shocks to labor productivity propagate into worker compensation using a new linkage of U.S. patent applications to U.S. business and worker tax records. We infer the causal effects of patent allowances by comparing firms whose patent applications were initially allowed to those whose patent applications were initially rejected. To identify patents that are ex ante valuable, we extrapolate the excess stock return estimates of Kogan et al. (2017) to the full set of accepted and rejected patent applications based on predetermined firm and patent application characteristics. An initial allowance of an ex ante valuable patent generates substantial increases in firm productivity and worker compensation. By contrast, initial allowances of lower ex ante value patents yield no detectable effects on firm outcomes. Patent allowances lead firms to increase employment, but entry wages and workforce composition are insensitive to patent decisions. On average, workers capture roughly 30 cents of every dollar of patent-induced surplus in higher earnings. This share is roughly twice as high among workers present since the year of application. These earnings effects are concentrated among men and workers in the top half of the earnings distribution and are paired with corresponding improvements in worker retention among these groups. We interpret these earnings responses as reflecting the capture of economic rents by senior workers, who are most costly for innovative firms to replace.more » « less
-
Many studies use matched employer-employee data to estimate a statistical model of earnings determination with worker and firm fixed effects. Estimates based on this model have produced influential yet controversial conclusions. The objective of this paper is to assess the sensitivity of these conclusions to the biases that arise because of limited mobility of workers across firms. We use employer-employee data from the US and several European countries while taking advantage of both fixed-effects and random-effects methods for bias-correction. We find that limited mobility bias is severe and that bias-correction is important.more » « less
-
Abstract Global product platforms can reduce production costs through economies of scale and learning but may decrease revenues by restricting the ability to customize for each market. We model the global platforming problem as a Nash equilibrium among oligopolistic competing firms, each maximizing its profit across markets with respect to its pricing, design, and platforming decisions. We develop and compare two methods to identify Nash equilibria: (1) a sequential iterative optimization (SIO) algorithm, in which each firm solves a mixed-integer nonlinear programming problem globally, with firms iterating until convergence; and (2) a mathematical program with equilibrium constraints (MPEC) that solves the Karush Kuhn Tucker conditions for all firms simultaneously. The algorithms’ performance and results are compared in a case study of plug-in hybrid electric vehicles where firms choose optimal battery capacity and whether to platform or differentiate battery capacity across the US and Chinese markets. We examine a variety of scenarios for (1) learning rate and (2) consumer willingness to pay (WTP) for range in each market. For the case of two firms, both approaches find the Nash equilibrium in all scenarios. On average, the SIO approach solves 200 times faster than the MPEC approach, and the MPEC approach is more sensitive to the starting point. Results show that the optimum for each firm is to platform when learning rates are high or the difference between consumer willingness to pay for range in each market is relatively small. Otherwise, the PHEVs are differentiated with low-range for China and high-range for the US.more » « less
-
null (Ed.)Abstract We study a new kind of nonzero-sum stochastic differential game with mixed impulse/switching controls, motivated by strategic competition in commodity markets. A representative upstream firm produces a commodity that is used by a representative downstream firm to produce a final consumption good. Both firms can influence the price of the commodity. By shutting down or increasing generation capacities, the upstream firm influences the price with impulses. By switching (or not) to a substitute, the downstream firm influences the drift of the commodity price process. We study the resulting impulse-regime switching game between the two firms, focusing on explicit threshold-type equilibria. Remarkably, this class of games naturally gives rise to multiple potential Nash equilibria, which we obtain thanks to a verification-based approach. We exhibit three candidate types of equilibria depending on the ultimate number of switches by the downstream firm (zero, one or an infinite number of switches). We illustrate the diversification effect provided by vertical integration in the specific case of the crude oil market. Our analysis shows that the diversification gains strongly depend on the pass-through from the crude price to the gasoline price.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Proceeding:
- The DOI is not currently available.
