This paper introduces state abstraction for two-player zero-sum Markov games (TZMGs) where the payoffs for the two players are determined by the state representing the environment and their respective actions, with state transitions following a Markov decision processes. For example, in games like soccer, the value of actions changes according to the state of play, we should describe them as Markov games. In TZMGs, the more the number of states becomes, the more difficult computing the equilibrium becomes. Therefore, we abstract the states of TZMGs and examine the performance. State abstraction reduces the number of states by treating multiple different states as a single state, and there is a substantial body of research on finding optimal policies for Markov decision processes using state abstraction. This study extends the state abstraction for MDPs to Markov games. In this case, the game with state abstraction may yield different equilibrium solutions from those of the ground game. To evaluate the equilibrium solutions of the game with state abstraction, we derived bounds on duality gap, which represents the distance from the equilibrium solutions of the ground game. Finally, we demonstrate our state abstraction with Markov Soccer, compute equilibrium policies, and examine the results.

This paper presents a payoff perturbation technique, introducing a strong convexity to players' payoff functions in games. This technique is specifically designed for first-order methods to achieve last-iterate convergence in games where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. Although perturbation is known to facilitate the convergence of learning algorithms, the magnitude of perturbation requires careful adjustment to ensure last-iterate convergence. Previous studies have proposed a scheme in which the magnitude is determined by the distance from a periodically re-initialized anchoring or reference strategy. Building upon this, we propose Gradient Ascent with Boosting Payoff Perturbation, which incorporates a novel perturbation into the underlying payoff function, maintaining the periodically re-initializing anchoring strategy scheme. This innovation empowers us to provide faster last-iterate convergence rates against the existing payoff perturbed algorithms, even in the presence of additive noise.

Cap-and-quota regulations are a commonly employed policy tool to address distributional disparities in matching markets. This paper develops a theoretical and empirical framework to evaluate the effectiveness of such regulations by integrating regional constraints into a transferable utility matching model. Using novel data from the Japan Residency Matching Program, we estimate participants' preferences and simulate counterfactual matching outcomes under various policy interventions. Simulation results reveal that cap-based regulations lead to significant efficiency losses, whereas a modest subsidy for each match in underserved regions achieves distributional constraints while improving social welfare.

This work addresses learning online fair division under uncertainty, where a central planner sequentially allocates items without precise knowledge of agents’ values or utilities. Departing from conventional online algorithms, the planner here relies on noisy, estimated values obtained after allocating items. We introduce wrapper algorithms utilizing dual averaging, enabling gradual learning of both the type distribution of arriving items and agents’ values through bandit feedback. This approach enables the algorithms to asymptotically achieve optimal Nash social welfare in linear Fisher markets with agents having additive utilities. We also empirically verify the performance of the proposed algorithms across synthetic and empirical datasets.

This paper proposes a payoff perturbation technique for the Mirror Descent (MD) algorithm in games where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. The optimistic family of learning algorithms, exemplified by optimistic MD, successfully achieves *last-iterate* convergence in scenarios devoid of noise, leading the dynamics to a Nash equilibrium. A recent re-emerging trend underscores the promise of the perturbation approach, where payoff functions are perturbed based on the distance from an anchoring, or *slingshot*, strategy. In response, we propose *Adaptively Perturbed MD* (APMD), which adjusts the magnitude of the perturbation by repeatedly updating the slingshot strategy at a predefined interval. This innovation empowers us to find a Nash equilibrium of the underlying game with guaranteed rates. Empirical demonstrations affirm that our algorithm exhibits significantly accelerated convergence.

This paper proposes Mutation-Driven Multiplicative Weights Update (M2WU) for learning an equilibrium in two-player zero-sum normal-form games and proves that it exhibits the last-iterate convergence property in both full and noisy feedback settings. In the former, players observe their exact gradient vectors of the utility functions. In the latter, they only observe the noisy gradient vectors. Even the celebrated Multiplicative Weights Update (MWU) and Optimistic MWU (OMWU) algorithms may not converge to a Nash equilibrium with noisy feedback. On the contrary, M2WU exhibits the last-iterate convergence to a stationary point near a Nash equilibrium in both feedback settings. We then prove that it converges to an exact Nash equilibrium by iteratively adapting the mutation term. We empirically confirm that M2WU outperforms MWU and OMWU in exploitability and convergence rates.

This paper considers the capacity expansion problem in two-sided matchings, where the policymaker is allowed to allocate some extra seats as well as the standard seats. In medical residency match, each hospital accepts a limited number of doctors. Such capacity constraints are typically given in advance. However, such exogenous constraints can compromise the welfare of the doctors; some popular hospitals inevitably dismiss some of their favorite doctors. Meanwhile, it is often the case that the hospitals are also benefited to accept a few extra doctors. To tackle the problem, we propose an anytime method that the upper confidence tree searches the space of capacity expansions, each of which has a resident-optimal stable assignment that the deferred acceptance method finds. Constructing a good search tree representation significantly boosts the performance of the proposed method. Our simulation shows that the proposed method identifies an almost optimal capacity expansion with a significantly smaller computational budget than exact methods based on mixed-integer programming.

In this study, we consider a variant of the Follow the Regularized Leader (FTRL) dynamics in two-player zero-sum games. FTRL is guaranteed to converge to a Nash equilibrium when time-averaging the strategies, while a lot of variants suffer from the issue of limit cycling behavior, i.e., lack the last-iterate convergence guarantee. To this end, we propose mutant FTRL (M-FTRL), an algorithm that introduces mutation for the perturbation of action probabilities. We then investigate the continuous-time dynamics of M-FTRL and provide the strong convergence guarantees toward stationary points that approximate Nash equilibria under full-information feedback. Furthermore, our simulation demonstrates that M-FTRL can enjoy faster convergence rates than FTRL and optimistic FTRL under full-information feedback and surprisingly exhibits clear convergence under bandit feedback.

This paper studies repeated games where two players play multiple duopolistic games simultaneously (multimarket contact). A key assumption is that each player receives a noisy and private signal about the other's actions (private monitoring or observation errors). There has been no game-theoretic support that multimarket contact facilitates collusion or not, in the sense that more collusive equilibria in terms of per-market profits exist than those under a benchmark case of one market. An equilibrium candidate under the benchmark case is belief-free strategies. We are the first to construct a non-trivial class of strategies that exhibits the effect of multimarket contact from the perspectives of simplicity and mild punishment. Strategies must be simple because firms in a cartel must coordinate each other with no communication. Punishment must be mild to an extent that it does not hurt even the minimum required profits in the cartel. We thus focus on two-state automaton strategies such that the players are cooperative in at least one market even when he or she punishes a traitor. Furthermore, we identify an additional condition (partial indifference), under which the collusive equilibrium yields the optimal payoff.

The discrete Fourier transform test is a randomness test included in NIST SP800-22. However, the variance of the test statistic is smaller than expected and the theoretical value of the variance is not known. Hitherto, the mechanism explaining why the former variance is smaller than expected has been qualitatively explained based on Parseval's theorem. In this paper, we explore this quantitatively and derive the variance using Parseval's theorem under particular assumptions. Numerical experiments are then used to show that this derived variance is robust.

This paper examines two-sided matching with budget constraints where one side (a firm or hospital) can make monetary transfers (offer wages) to the other (a worker or doctor). In a standard model, while multiple doctors can be matched to a single hospital, a hospital has a maximum quota; thus, the number of doctors assigned to a hospital cannot exceed a certain limit. In our model, in contrast, a hospital has a fixed budget; that is, the total amount of wages allocated by each hospital to doctors is constrained. With budget constraints, stable matchings may fail to exist and checking for the existence is hard. To deal with the nonexistence of stable matchings, we extend the "matching with contracts" model of Hatfield and Milgrom so that it deals with approximately stable matchings where each of the hospitals' utilities after deviation can increase by a factor up to a certain amount. We then propose two novel mechanisms that efficiently return a stable matching that exactly satisfies the budget constraints. Specifically, by sacrificing strategy-proofness, our first mechanism achieves the best possible bound. We also explore a special case on which a simple mechanism is strategy-proof for doctors, while maintaining the best possible bound of the general case.

This paper presents a new way of formalizing the coalition structure generation problem (CSG) so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG involves partitioning a set of agents into coalitions to maximize social surplus. Traditionally, the input of the CSG problem is a black-box function called a characteristic function, which takes a coalition as input and returns the value of the coalition. As a result, applying constraint optimization techniques to this problem has been infeasible. However, characteristic functions that appear in practice often can be represented concisely by a set of rules, rather than treating the function as a black box. Then we can solve the CSG problem more efficiently by directly applying constraint optimization techniques to this compact representation. We present new formalizations of the CSG problem by utilizing recently developed compact representation schemes for characteristic functions. We first characterize the complexity of CSG under these representation schemes. In this context, the complexity is driven more by the number of rules than by the number of agents. As an initial step toward developing efficient constraint optimization algorithms for solving the CSG problem, we also develop mixed integer programming formulations and show that an off-the-shelf optimization package can perform reasonably well.

A repeated game is a formal model for analyzing cooperation in long-term relationships, e.g., in the prisoner's dilemma. Although the case where each player observes her opponent's action with some observation errors (imperfect private monitoring) is difficult to analyze, a special type of an equilibrium called belief-free equilibrium is identified to make the analysis in private monitoring tractable. However, existing works using a belief-free equilibrium show that cooperative relations can be sustainable only in ideal situations. We deal with a generic problem that can model both the prisoner's dilemma and the team production problem. We examine a situation with an additional action that is dominated by another action. To our surprise, by adding this seemingly irrelevant action, players can achieve sustainable cooperative relations far beyond the ideal situations. More specifically, we identify a class of strategies called one-shot punishment strategy that can constitute a belief-free equilibrium in a wide range of parameters. Moreover, for a two-player case, the obtained welfare matches a theoretical upper bound.

This paper deals with two-sided matching with budget constraints where one side (firm or hospital) can make monetary transfers (offer wages) to the other (worker or doctor). In a standard model, while multiple doctors can be matched to a single hospital, a hospital has a maximum quota: the number of doctors assigned to a hospital cannot exceed a certain limit. In our model, a hospital instead has a fixed budget: the total amount of wages allocated by each hospital to doctors is constrained. With budget constraints, stable matchings may fail to exist and checking the existence is hard. To deal with the nonexistence of stable matchings, we extend the “matching with contracts” model by Hatfield and Milgrom, so that it handles near-feasible matchings that exceeds each budget of the hospitals by a certain amount. We then propose two novel mechanisms that efficiently return such a near-feasible matching that is stable with respect to the actual amount of wages allocated by each hospital. In particular, by sacrificing strategy-proofness, our second mechanism achieves the best possible bound.

School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., “financially-distressed” and “minority” types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Furthermore, we introduce an extended model that can handle both type-specific ceilings and floors and propose a extended mechanism DA-OT* to handle the extended model. Computer simulation results illustrate that DA-OT outperforms an artificial cap mechanism where we set a hard-bound for each type in each school. DA-OT* can achieve stability in the extended model without sacrificing students’ welfare.

This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i.e., a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare.

School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the balance on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., ``financially-distressed'' and ``minority'' types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus, we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model, and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Computer simulation results illustrate that the DA-OT outperforms an artificial cap mechanism, where the number of seats for each type is fixed.

In cognitive radio networks, one key feature of spectrum trading is its short term or, even, real time, since the spectrum availability, quality, and price keep changing over time. Therefore, a spectrum pricing policy should be dynamically optimal. In this work, we address the real-time optimal pricing problem for primary users. Based on differential game model, we analyze the optimal pricing strategy for QoS-aware dynamic networks in which the secondary users' number and primary users' QoS level keep changing over time. Nash equilibrium is derived and an optimal pricing and QoS setting policy is formulated. Since the Nash equilibrium of our differential game based model deals with optimal pricing in each time instance, the real-time optimal pricing characteristic can be realized.

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Coalition Structure generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a Coalition Structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, one might assume that the computational costs required in this approach would be too expensive, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve n-th power of 2 DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS with quality guarantees. More specifically, we develop an algorithm with parameter k that can find a CS whose social surplus is at least max(k/(w*+1), 2k/n) of the optimal CS, where w* is the tree width of a constraint graph. When k=1, the complexity of this algorithm is about the same as solving just one DCOP. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing an efficient CSG algorithm with quality guarantees.

We propose a keyword auction protocol called the GSP-ExR (GSP with an exclusive right) in which the number of advertisements displayed around search results can be dynamically adjusted. It is an extension of the generalized second-price (GSP) auction

We propose a keyword auction protocol called the Generalized Second Price with an Exclusive Right (GSP-ExR). In existing keyword auctions, the number of displayed advertisements is determined in advance. Thus, we consider adjusting the number of advertisements dynamically based on bids. In the GSP-ExR, the number of slots can be either 1 or K. When K slots are displayed, the protocol is identical to the GSP. If the value per click of the highest ranked bidder is large enough, then this bidder can exclusively display her advertisement by paying a premium. Thus, this pricing scheme is relatively simple and seller revenue is at least as good as the GSP. Also, in the GSP-ExR, the highest ranked bidder has no incentive to change the number of slots by over/under-bidding as long as she retains the top position.

Experimental system of IP/sup 2/ mobility management was designed and implemented in order to confirm feasibility of the protocol and identify its bottlenecks. The experimental system is based on a prototype implementation of IP/sup 2/ mobility management which runs on PC servers. Series of experiments were conducted in order to check validity of protocol sequence and impact of load status on system performance. From the feasibility tests results, it was confirmed that there was no fundamental error in IP/sup 2/ mobility management and it could interwork with other IP protocols. Throughout the bottleneck tests, degradation in performance due to limitation of the transport: mechanism was observed when the MN had relatively large number of active peers. Experimental results indicated that alternate mechanism to improve reliability of signalling messages was highly needed. From user-plane viewpoint, additional processing that is specific to IP/sup 2/ mobility management put negligible effect on the packet forwarding delay of the AR.

This paper presents a new ascending-price multi-unit auction protocol. As far as the authors are aware, this is the first protocol that has an open format, and in which sincere bidding is an equilibrium strategy, even if the marginal utilities of each agent can increase and agents can submit bids. As ever-increasing numbers of companies and consumers are trading on Internet auctions, a new type of cheating called false-name has been noticed. Specifically, there may be some agents with fictitious names such as multiple e-mail addresses. The VCG is not an open format, and truth-telling is no longer a dominant strategy if agents can submit bids and the marginal utilities of each agent can increase. The Iterative Reducing (IR) protocol with a sealed-bid format is robust against bids, although it requires the auctioneer to carefully pre-determine a reservation price for one unit. Open format protocols, such as the Ausubel auction, outperform sealed-bid format protocols in terms of the simplicity and privacy-preservation. These two advantages are said to encourage more agents to bid sincerely and to provide the seller with higher revenue. We extend the Ausubel auction to our proposed protocol which can handle the cases where the marginal utilities of each agent can increase. Moreover, it is robust against bids and does not require the auctioneer to set a reservation price. Our simulation result indicates that our protocol herein obtains a social surplus close to Pareto efficient and that it outperforms the IR with respect to the social surplus and the seller's revenue.

This paper presents a distributed adapter technology for OSS (operations support systems), which makes it possible to share data among a large number of multiple distributed AP (application processes) without the bottleneck of the system scalability and performance.

This paper proposes a new formulation for speech recognition/understanding systems. In which the posteriori probability of a speaker's message that the speaker intends to address given an observed acoustic sequence is maximized. This is an extension of the current criterion that maximizes the probability of a word sequence. Among the various possible representations, we employ a co-occurrence score of words measured by mutual information as the conditional probability of a word sequence occurring in a given message. The word sequence hypotheses obtained by bigram and trigram language models are rescored using the co-occurrence score. Experimental results show that the word accuracy is improved by this method. Topic-words which represent the content of a speech signal are then extracted from speech recognition results based on the significance score of each word. When five topic-words are extracted for each broadcast-news article, 82.8% of them are correct in average. This paper also proposes a verbalization-dependent language model which is useful for Japanese dictation systems.

In this paper, we report on language modeling and acoustic modeling studies for Japanese broadcast news speech recognition. We constructed a language model that reduces recognition errors by utilizing context-dependent readings of Japanese characters. We also introduced filled-pause modeling into the language model. To improve the model’s performance for a series of sentences spoken by one speaker, an on-line incremental speaker adaptation was combined with automatic detection of speaker changes. By incorporating all the above methods, we achieved a 25.1% reduction in word error rate over the baseline results. This paper also reports on our preliminary studies on topic extraction and summarization of broadcast-news speech.