Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConditions for Stability in Strategic Matching
55
0
0.0
(
0
)
Added by
James Bailey
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the stability of matchings when individuals strategically submit preference information to a publicly known algorithm. Most pure Nash equilibria of the ensuing game yield a matching that is unstable with respect to the individuals sincere preferences. We introduce a well-supported minimal dishonesty constraint, and obtain conditions under which every pure Nash equilibrium yields a matching that is stable with respect to the sincere preferences. The conditions on the matching algorithm are to be either fully-randomized, or monotonic and independent of non-spouses (INS), an IIA-like property. These conditions are significant because they support the use of algorithms other than the Gale-Shapley (man-optimal) algorithm for kidney exchange and other applications. We prove that the Gale-Shapley algorithm always yields the woman-optimal matching when individuals are minimally dishonest. However, we give a negative answer to one of Gusfield and Irvings open questions: there is no monotonic INS or fully-randomized stable matching algorithm that is certain to yield the egalitarian-optimal matching when individuals are strategic and minimally dishonest. Finally, we show that these results extend to the student placement problem, where women are polyandrous but must be honest but do not extend to the admissions problem, where women are both polyandrous and strategic.
rate research
Read More
Strategic suppression of grades, as well as early offers and contracts, are well-known phenomena in the matching process where graduating students apply to jobs or further education. In this paper, we consider a game theoretic model of these phenomena introduced by Ostrovsky and Schwarz, and study the loss in social welfare resulting from strategic behavior of the schools, employers, and students. We model grading of students as a game where schools suppress grades in order to improve their students placements. We also consider the quality loss due to unraveling of the matching market, the strategic behavior of students and employers in offering early contracts with the goal to improve the quality. Our goal is to evaluate if strategic grading or unraveling of the market (or a combination of the two) can cause significant welfare loss compared to the optimal assignment of students to jobs. To measure welfare of the assignment, we assume that welfare resulting from a job -- student pair is a separable and monotone function of student ability and the quality of the jobs. Assuming uniform student quality distribution, we show that the quality loss from the above strategic manipulation is bounded by at most a factor of 2, and give improved bounds for some special cases of welfare functions.
In this paper we describe an approach to resolve strategic games in which players can assume different types along the game. Our goal is to infer which type the opponent is adopting at each moment so that we can increase the players odds. To achieve that we use Markov games combined with hidden Markov model. We discuss a hypothetical example of a tennis game whose solution can be applied to any game with similar characteristics.
It is known that there are uncoupled learning heuristics leading to Nash equilibrium in all finite games. Why should players use such learning heuristics and where could they come from? We show that there is no uncoupled learning heuristic leading to Nash equilibrium in all finite games that a player has an incentive to adopt, that would be evolutionary stable or that could learn itself. Rather, a player has an incentive to strategically teach such a learning opponent in order secure at least the Stackelberg leader payoff. The impossibility result remains intact when restricted to the classes of generic games, two-player games, potential games, games with strategic complements or 2x2 games, in which learning is known to be nice. More generally, it also applies to uncoupled learning heuristics leading to correlated equilibria, rationalizable outcomes, iterated admissible outcomes, or minimal curb sets. A possibility result restricted to strategically trivial games fails if some generic games outside this class are considered as well.
Using mobile robots for autonomous patrolling of environments to prevent intrusions is a topic of increasing practical relevance. One of the most challenging scientific issues is the problem of finding effective patrolling strategies that, at each time point, determine the next moves of the patrollers in order to maximize some objective function. In the very last years this problem has been addressed in a game theoretical fashion, explicitly considering the presence of an adversarial intruder. The general idea is that of modeling a patrolling situation as a game, played by the patrollers and the intruder, and of studying the equilibria of this game to derive effective patrolling strategies. In this paper we present a game theoretical formal framework for the determination of effective patrolling strategies that extends the previous proposals appeared in the literature, by considering environments with arbitrary topology and arbitrary preferences for the agents. The main original contributions of this paper are the formulation of the patrolling game for generic graph environments, an algorithm for finding a deterministic equilibrium strategy, which is a fixed path through the vertices of the graph, and an algorithm for finding a non-deterministic equilibrium strategy, which is a set of probabilities for moving between adjacent vertices of the graph. Both the algorithms are analytically studied and experimentally validated, to assess their properties and efficiency.
We study the dynamic pricing problem faced by a monopolistic retailer who sells a storable product to forward-looking consumers. In this framework, the two major pricing policies (or mechanisms) studied in the literature are the preannounced (commitment) pricing policy and the contingent (threat or history dependent) pricing policy. We analyse and compare these pricing policies in the setting where the good can be purchased along a finite time horizon in indivisible atomic quantities. First, we show that, given linear storage costs, the retailer can compute an optimal preannounced pricing policy in polynomial time by solving a dynamic program. Moreover, under such a policy, we show that consumers do not need to store units in order to anticipate price rises. Second, under the contingent pricing policy rather than the preannounced pricing mechanism, (i) prices could be lower, (ii) retailer revenues could be higher, and (iii) consumer surplus could be higher. This result is surprising, in that these three facts are in complete contrast to the case of a retailer selling divisible storable goods Dudine et al. (2006). Third, we quantify exactly how much more profitable a contingent policy could be with respect to a preannounced policy. Specifically, for a market with $N$ consumers, a contingent policy can produce a multiplicative factor of $Omega(log N)$ more revenues than a preannounced policy, and this bound is tight.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
