Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFailure of Equilibrium Selection Methods for Multiple-Principal, Multiple-Agent Problems with Non-Rivalrous Goods: An Analysis of Data Markets
84
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The advent of machine learning tools has led to the rise of data markets. These data markets are characterized by multiple data purchasers interacting with a set of data sources. Data sources have more information about the quality of data than the data purchasers; additionally, data itself is a non-rivalrous good that can be shared with multiple parties at negligible marginal cost. In this paper, we study the multiple-principal, multiple-agent problem with non-rivalrous goods. Under the assumption that the principals payoff is quasilinear in the payments given to agents, we show that there is a fundamental degeneracy in the market of non-rivalrous goods. Specifically, for a general class of payment contracts, there will be an infinite set of generalized Nash equilibria. This multiplicity of equilibria also affects common refinements of equilibrium definitions intended to uniquely select an equilibrium: both variational equilibria and normalized equilibria will be non-unique in general. This implies that most existing equilibrium concepts cannot provide predictions on the outcomes of data markets emerging today. The results support the idea that modifications to payment contracts themselves are unlikely to yield a unique equilibrium, and either changes to the models of study or new equilibrium concepts will be required to determine unique equilibria in settings with multiple principals and a non-rivalrous good.
rate research
Read More
We prove an existence result for the principal-agent problem with adverse selection under general assumptions on preferences and allocation spaces. Instead of assuming that the allocation space is finite-dimensional or compact, we consider a more general coercivity condition which takes into account the principals cost and the agents preferences. Our existence proof is simple and flexible enough to adapt to partial participation models as well as to the case of type-dependent budget constraints.
The concept of leader--follower (or Stackelberg) equilibrium plays a central role in a number of real--world applications of game theory. While the case with a single follower has been thoroughly investigated, results with multiple followers are only sporadic and the problem of designing and evaluating computationally tractable equilibrium-finding algorithms is still largely open. In this work, we focus on the fundamental case where multiple followers play a Nash equilibrium once the leader has committed to a strategy---as we illustrate, the corresponding equilibrium finding problem can be easily shown to be $mathcal{FNP}$--hard and not in Poly--$mathcal{APX}$ unless $mathcal{P} = mathcal{NP}$ and therefore it is one among the hardest problems to solve and approximate. We propose nonconvex mathematical programming formulations and global optimization methods to find both exact and approximate equilibria, as well as a heuristic black box algorithm. All the methods and formulations that we introduce are thoroughly evaluated computationally.
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for a one-sided matching market -- called ADHZ in this paper -- has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the $epsilon$-approximate ADHZ model, and we give the following results. * Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. * A combinatorial polynomial-time algorithm for an $epsilon$-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. * An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. Since computing an equilibrium for HZ is likely to be highly intractable and because of the difficulty of extending HZ to more general utility functions, Hosseini and Vazirani proposed (a rich collection of) Nash-bargaining-based matching market models. For the dichotomous-utilities case of their model linear Arrow-Debreu Nash bargaining one-sided matching market (1LAD), we give a combinatorial, strongly polynomial-time algorithm and show that it admits a rational convex program.
Crowdsourcing markets have emerged as a popular platform for matching available workers with tasks to complete. The payment for a particular task is typically set by the tasks requester, and may be adjusted based on the quality of the completed work, for example, through the use of bonus payments. In this paper, we study the requesters problem of dynamically adjusting quality-contingent payments for tasks. We consider a multi-round version of the well-known principal-agent model, whereby in each round a worker makes a strategic choice of the effort level which is not directly observable by the requester. In particular, our formulation significantly generalizes the budget-free online task pricing problems studied in prior work. We treat this problem as a multi-armed bandit problem, with each arm representing a potential contract. To cope with the large (and in fact, infinite) number of arms, we propose a new algorithm, AgnosticZooming, which discretizes the contract space into a finite number of regions, effectively treating each region as a single arm. This discretization is adaptively refined, so that more promising regions of the contract space are eventually discretized more finely. We analyze this algorithm, showing that it achieves regret sublinear in the time horizon and substantially improves over non-adaptive discretization (which is the only competing approach in the literature). Our results advance the state of art on several different topics: the theory of crowdsourcing markets, principal-agent problems, multi-armed bandits, and dynamic pricing.
In evolutionary games the fitness of individuals is not constant but depends on the relative abundance of the various strategies in the population. Here we study general games among n strategies in populations of large but finite size. We explore stochastic evolutionary dynamics under weak selection, but for any mutation rate. We analyze the frequency dependent Moran process in well-mixed populations, but almost identical results are found for the Wright-Fisher and Pairwise Comparison processes. Surprisingly simple conditions specify whether a strategy is more abundant on average than 1/n, or than another strategy, in the mutation-selection equilibrium. We find one condition that holds for low mutation rate and another condition that holds for high mutation rate. A linear combination of these two conditions holds for any mutation rate. Our results allow a complete characterization of n*n games in the limit of weak selection.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
