An official website of the United States government
We study zero-sum differential games with state constraints and one-sided information, where the informed player (Player 1) has a categorical payoff type unknown to the uninformed player (Player 2). The goal of Player 1 is to minimize his payoff without violating the constraints, while that of Player 2 is to either violate the state constraints, or otherwise, to maximize the payoff. One example of the game is a man-to-man matchup in football. Without state constraints, Cardaliaguet (2007) showed that the value of such a game exists and is convex to the common belief of players. Our theoretical contribution is an extension of this result to differential games with state constraints and the derivation of the primal and dual subdynamic principles necessary for computing the behavioral strategies. Compared with existing works on imperfect-information dynamic games that focus on scalability and generalization, our focus is instead on revealing the mechanism of belief manipulation behaviors resulted from information asymmetry and state constraints. We use a simplified football game to demonstrate the utility of this work, where we reveal player positions and belief states in which the attacker should (or should not) play specific random fake moves to take advantage of information asymmetry, and compute how the defender should respond.
more »
« less
Two for One & One for All: Two-Sided Manipulation in Matching Markets
Strategic behavior in two-sided matching markets has been traditionally studied in a one-sided manipulation setting where the agent who misreports is also the intended beneficiary. Our work investigates two-sided manipulation of the deferred acceptance algorithm where the misreporting agent and the manipulator (or beneficiary) are on different sides. Specifically, we generalize the recently proposed accomplice manipulation model (where a man misreports on behalf of a woman) along two complementary dimensions: (a) the two for one model, with a pair of misreporting agents (man and woman) and a single beneficiary (the misreporting woman), and (b) the one for all model, with one misreporting agent (man) and a coalition of beneficiaries (all women). Our main contribution is to develop polynomial-time algorithms for finding an optimal manipulation in both settings. We obtain these results despite the fact that an optimal one for all strategy fails to be inconspicuous, while it is unclear whether an optimal two for one strategy satisfies the inconspicuousness property. We also study the conditions under which stability of the resulting matching is preserved. Experimentally, we show that two-sided manipulations are more frequently available and offer better quality matches than their one-sided counterparts.
more »
« less
- PAR ID:
- 10353549
- Date Published:
- Journal Name:
- Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence Main Track.
- Page Range / eLocation ID:
- 321 to 327
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the distortion of one-sided and two-sided matching problems on the line. In the one-sided case, n agents need to be matched to n items, and each agent's cost in a matching is their distance from the item they were matched to. We propose an algorithm that is provided only with ordinal information regarding the agents' preferences (each agent's ranking of the items from most- to least-preferred) and returns a matching aiming to minimize the social cost with respect to the agents' true (cardinal) costs. We prove that our algorithm simultaneously achieves the best-possible approximation of 3 (known as distortion) with respect to a variety of social cost measures which include the utilitarian and egalitarian social cost. In the two-sided case, where the agents need be matched to n other agents and both sides report their ordinal preferences over each other, we show that it is always possible to compute an optimal matching. In fact, we show that this optimal matching can be achieved using even less information, and we provide bounds regarding the sufficient number of queries.more » « less
-
We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set of n agents needs to be matched to a set of n heterogeneous items. Each agent i has a value vij for each item j, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only the ordinal preferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. In this paper we achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the full cardinal preferences of the agents, i.e., all of the vij values. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest.more » « less
-
Unlike ordinal-utility matching markets, which are well-developed from the viewpoint of both theory and practice, recent insights from a computer science perspective have left cardinal-utility matching markets in a state of flux. The celebrated pricing-based mechanism for one-sided cardinal-utility matching markets due to Hylland and Zeckhauser [1979](HZ), which had long eluded efficient algorithms, was finally shown to be intractable; the problem of computing an approximate equilibrium is PPAD-complete (Vazirani and Yannakakis [2021], Chen et al. [2022]). This led us to ask the question: is there an alternative, polynomial time, mechanism for one-sided cardinal-utility matching markets which achieves the desirable properties of HZ, i.e. (ex-ante) envyfreeness (EF) and Pareto-optimality (PO)? We show that the problem of finding an EF+PO lottery in a one-sided cardinal-utility matching market is by itself already PPAD-complete. However, a (2 + ǫ)-approximately envy-free and (exactly) Pareto-optimal lottery can be found in polynomial time using the Nash-bargaining-based mechanism of Hosseini and Vazirani [2022]. Moreover, the mechanism is also (2+ǫ)-approximately incentive compatible. We also present several results on two-sided cardinal-utility matching markets, including non-existence of EF+PO lotteries as well as existence of justified-envy-free and weak Pareto-optimal lotteries.more » « less
-
Motivated by applications from gig economy and online marketplaces, we study a two-sided queueing system under joint pricing and matching controls. The queueing system is modeled by a bipartite graph, where the vertices represent customer or server types and the edges represent compatible customer-server pairs. We propose a threshold-based two-price policy and queue length-based maximum-weight matching policy and show that it achieves a near-optimal profit. We study the system under the large-scale regime, wherein the arrival rates are scaled up, and under the large-market regime, wherein both the arrival rates and numbers of customer and server types increase. We show that two-price policy is a primary driver for optimality in the large-scale regime. We demonstrate the advantage of maximum-weight matching with respect to the number of customer and server types. Concurrently, we show that the interplay of pricing and matching is crucial for optimality in the large-market regime.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.24963/ijcai.2022/46
