Arrow Research search

Author name cluster

Taiki Todo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers
2 author rows

Possible papers

30

ECAI Conference 2025 Conference Paper

Average Rules for Facility Location Games with Voluntary Participation

  • Shota Miyamoto
  • Taiki Todo
  • Makoto Yokoo

This paper studies social choice under single-peaked preferences, where voters’ participation is voluntary. We say a social choice function satisfies participation if, for any voter, participating by reporting her true preference is weakly better than not participating. For each of two classes of parameterized social choice functions, namely ordered weighted average (OWA) methods and weighted average (WA) methods, we give a necessary and sufficient condition on the parameters to satisfy participation. We also give further discussions on OWAs and WAs, including the necessary and sufficient condition to satisfy a weaker notion of participation called non-obvious abstention (NOA), and the relationship with other properties.

Details

ECAI Conference 2024 Conference Paper

Analyzing Incentives and Fairness in Ordered Weighted Average for Facility Location Games

  • Kento Yoshida
  • Kei Kimura
  • Taiki Todo
  • Makoto Yokoo

Facility location games provide an abstract model of mechanism design. In such games, a mechanism takes a profile of n single-peaked preferences over an interval as an input and determines the location of a facility on the interval. In this paper, we restrict our attention to distance-based single-peaked preferences and focus on a well-known class of parameterized mechanisms called ordered weighted average methods, which is proposed by Yager [38] and contains several practical implementations such as the standard average and the Olympic average. We comprehensively analyze their performance in terms of both incentives and fairness. More specifically, we provide necessary and sufficient conditions on their parameters to achieve strategy-proofness, non-obvious manipulability, individual fair share, and proportional fairness, respectively.

Details

JAAMAS Journal 2022 Journal Article

Manipulation-resistant false-name-proof facility location mechanisms for complex graphs

  • Ilan Nehama
  • Taiki Todo
  • Makoto Yokoo

Abstract In many real-life scenarios, a group of agents needs to agree on a common action, e. g. , on a location for a public facility, while there is some consistency between their preferences, e. g. , all preferences are derived from a common metric space. The facility location problem models such scenarios and it is a well-studied problem in social choice. We study mechanisms for facility location on unweighted undirected graphs that are resistant to manipulations ( strategy-proof, abstention-proof, and false-name-proof ) by both individuals and coalitions on one hand and anonymous and efficient ( Pareto-optimal ) on the other. We define a new family of graphs, \(ZV\) - line graphs, and show a general facility location mechanism for these graphs that satisfies all these desired properties. This mechanism can also be computed in polynomial time and it can equivalently be defined as the first Pareto-optimal location according to some predefined order. Our main result, the \(ZV\) -line graphs family and the mechanism we present for it, unifies all works in the literature of false-name-proof facility location on discrete graphs including the preliminary (unpublished) works we are aware of. In particular, we show mechanisms for all graphs of at most five vertices, discrete trees, bicliques, and clique tree graphs. Finally, we discuss some generalizations and limitations of our result for facility location problems on other structures: Weighted graphs, large discrete cycles, infinite graphs; and for facility location problems concerning infinite societies.

Details DOI

AAMAS Conference 2022 Conference Paper

Strategy-Proof House Allocation with Existing Tenants over Social Networks

  • Bo You
  • Ludwig Dierks
  • Taiki Todo
  • Minming Li
  • Makoto Yokoo

Mechanism design over social networks, whose goal is to incentivize agents to diffuse the information of a mechanism to their followers, as well as to report their true preferences, is one of the new trends in market design. In this paper, we reconsider the traditional house allocation problem with existing tenants from the perspective of mechanism design over social networks. Since our model is a generalization of the networked housing market investigated by Kawasaki et al. [9], no mechanism simultaneously satisfies strategy-proofness, individual rationality and Pareto efficiency for general social network structures. We therefore examine the cases where the social network has a tree structure. We first show that even for the restricted structure, a weaker welfare requirement called non-wastefulness is not achievable by any strategy-proof and individually rational mechanism. We then show that a non-trivial modification of You Request My House - I Get Your Turn mechanism (YRMH-IGYT) is individually rational, strategy-proof, and weakly non-wasteful. Furthermore, it chooses an allocation in the strict core for neighbors and satisfies weak group strategy-proofness.

PDF

IJCAI Conference 2022 Conference Paper

Two-Sided Matching over Social Networks

  • Sung-Ho Cho
  • Taiki Todo
  • Makoto Yokoo

A new paradigm of mechanism design, called mechanism design over social networks, investigates agents’ incentives to diffuse the information of mechanisms to their followers over social networks. In this paper we consider it for two-sided matching, where the agents on one side, say students, are distributed over social networks and thus are not fully observable to the mechanism designer, while the agents on the other side, say colleges, are known a priori. The main purpose of this paper is to clarify the existence of mechanisms that satisfy several properties that are classified into four criteria: incentive constraints, efficiency constraints, stability constraints, and fairness constraints. We proposed three mechanisms and showed that no mechanism is better than these mechanisms, i. e. , they are in the Pareto frontier according to the set of properties defined in this paper.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Fair Pairwise Exchange among Groups

  • Zhaohong Sun
  • Taiki Todo
  • Toby Walsh

We study the pairwise organ exchange problem among groups motivated by real-world applications and consider two types of group formulations. Each group represents either a certain type of patient-donor pairs who are compatible with the same set of organs, or a set of patient-donor pairs who reside in the same region. We address a natural research question, which asks how to match a maximum number of pairwise compatible patient-donor pairs in a fair and individually rational way. We first propose a natural fairness concept that is applicable to both types of group formulations and design a polynomial-time algorithm that checks whether a matching exists that satisfies optimality, individual rationality, and fairness. We also present several running time upper bounds for computing such matchings for different graph structures.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Mechanism Design for Housing Markets over Social Networks

  • Takehiro Kawasaki
  • Ryoji Wada
  • Taiki Todo
  • Makoto Yokoo

In this paper we investigate the effect of an underlying social network over agents in a well-known multi-agent resource allocation problem; the housing market. We first show that, when a housing market takes place over a social network with more than two agents and these agents have an option to avoid forwarding information about it to their followers, there does not exist an exchange mechanism that simultaneously satisfies strategy-proofness, Pareto efficiency, and individual rationality. It is also impossible to find a strategy-proof exchange mechanism that always chooses an outcome in a weakened core. These results highlight the difficulty of taking into account the agents’ incentive of information diffusion in the resource allocation. To overcome these negative results, we consider two different ways of restricting the problem; limiting the domain of preferences and the structure of social networks.

PDF

IJCAI Conference 2021 Conference Paper

New Algorithms for Japanese Residency Matching

  • Zhaohong Sun
  • Taiki Todo
  • Makoto Yokoo

We study the Japanese Residency Matching Program (JRMP) in which hospitals are partitioned into disjoint regions and both hospitals and regions are subject to quotas. To achieve a balanced distribution of doctors across regions, hard bounds are imposed by the government to limit the number of doctors who can be placed in each region. However, such hard bounds lead to inefficiency in terms of wasted vacant positions. In this paper, we propose two suitable algorithms to reduce waste with minimal modification to the current system and show that they are superior to the algorithm currently deployed in JRMP by comparing them theoretically and empirically.

PDF Details DOI

ECAI Conference 2020 Conference Paper

False-Name-Proof Facility Location on Discrete Structures

  • Taiki Todo
  • Nodoka Okada
  • Makoto Yokoo

We consider the problem of locating a single facility on a vertex in a given graph based on agents’ preferences, where the domain of the preferences is either single-peaked or single-dipped, depending on whether they want to access the facility (a public good) or be far from it (a public bad). Our main interest is the existence of deterministic social choice functions that are Pareto efficient and false-name-proof, i. e. , resistant to fake votes. We show that regardless of whether preferences are single-peaked or single-dipped, such a social choice function exists (i) for any tree graph, and (ii) for a cycle graph if and only if its length is less than six. We also show that when the preferences are single-peaked, such a social choice function exists for any ladder (i. e. , 2 × m grid) graph, and does not exist for any larger (hyper)grid.

Details

IJCAI Conference 2020 Conference Paper

Mechanism Design with Uncertainty

  • Taiki Todo

My research is summarized as mechanism design with uncertainty. Traditional mechanism design focuses on static environments where all the (possibly probabilistic) information about the agents are observable by the mechanism designer. In practice, however, it is possible that the set of participating agents and/or some of teheir actions are not observable a priori. We therefore focused on various kinds of uncertainty in mechanism design and developed/analyzed several market mechanisms that incentivise agents to behave in a sincere way.

PDF Details DOI

ECAI Conference 2020 Conference Paper

Split Manipulations in Cost Sharing of Minimum Cost Spanning Tree

  • Taiki Todo
  • Makoto Yokoo

This paper studies minimum cost spanning tree (MCST) problems, in which an agent can behave as multiple agents by adding fake accounts. Since such split manipulations may increase the cost of MCST, it is important to (i) design a cost allocation rule under which no agent has an incentive to split her accounts, and (ii) analyze the resistance of the existing cost allocation rules against split manipulations. We first show that there exists no cost allocation rule that is both efficient and split-proof under the general domain. We then focus on the MCST problems with monotonic weight functions and show that there exists a cost allocation rule that is efficient, core-selecting, and split-proof. We finally analyze the resistance of the Bird rule, one of the most studied cost allocation rules in the literature, against split manipulations from three different perspectives: the mixed price of anarchy, the computational difficulty of manipulation, and domain restrictions.

Details

AAAI Conference 2020 Conference Paper

Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network

  • Takehiro Kawasaki
  • Nathanael Barrot
  • Seiji Takanashi
  • Taiki Todo
  • Makoto Yokoo

Auctions via social network, pioneered by Li et al. (2017), have been attracting considerable attention in the literature of mechanism design for auctions. However, no known mechanism has satisfied strategy-proofness, non-deficit, nonwastefulness, and individual rationality for the multi-unit unit-demand auction, except for some naı̈ve ones. In this paper, we first propose a mechanism that satisfies all the above properties. We then make a comprehensive comparison with two naı̈ve mechanisms, showing that the proposed mechanism dominates them in social surplus, seller’s revenue, and incentive of buyers for truth-telling. We also analyze the characteristics of the social surplus and the revenue achieved by the proposed mechanism, including the constant approximability of the worst-case efficiency loss and the complexity of optimizing revenue from the seller’s perspective.

PDF Details

AAMAS Conference 2019 Conference Paper

Manipulations-resistant Facility Location Mechanisms for ZV-line Graphs

  • Ilan Nehama
  • Taiki Todo
  • Makoto Yokoo

In many real-life scenarios, a group of agents needs to agree on a common action, e. g. , on a location for a public facility, while there is some consistency between their preferences, e. g. , all preferences are derived from a common metric space. The facility location problem models such scenarios and it is a well-studied problem in social choice. We study mechanisms for facility location on unweighted undirected graphs, which are resistant to manipulations (strategy-proof, abstention-proof, and false-name-proof ) by both individuals and coalitions and are efficient (Pareto optimal). We define a family of graphs, ZV -line graphs, and show a general facility location mechanism for these graphs which satisfies all these desired properties. Our result unifies the few works in the literature of false-name-proof facility location on discrete graphs including the preliminary (unpublished) works we are aware of.

PDF

JAIR Journal 2018 Journal Article

A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences

  • Etsushi Fujita
  • Julien Lesca
  • Akihisa Sonoda
  • Taiki Todo
  • Makoto Yokoo

Core-selection is a crucial property of rules in the literature of resource allocation. It is also desirable, from the perspective of mechanism design, to address the incentive of agents to cheat by misreporting their preferences. This paper investigates the exchange problem where (i) each agent is initially endowed with (possibly multiple) indivisible goods, (ii) agents' preferences are assumed to be conditionally lexicographic, and (iii) side payments are prohibited. We propose an exchange rule called augmented top-trading-cycles (ATTC), based on the original TTC procedure. We first show that ATTC is core-selecting and runs in polynomial time with respect to the number of goods. We then show that finding a beneficial misreport under ATTC is NP-hard. We finally clarify relationship of misreporting with splitting and hiding, two different types of manipulations, under ATTC.

PDF Details DOI

AAAI Conference 2018 Conference Paper

Facility Location Games With Fractional Preferences

  • Chi Kit Ken Fong
  • Minming Li
  • Pinyan Lu
  • Taiki Todo
  • Makoto Yokoo

In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of minimizing total cost is at least Ω(n 1 3 ). Hence, we use the utility function to analyze the agents’ satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategyproof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1. 06. For the objective of maximizing the minimum utility, we give a lower-bound of 1. 5 and present a 2-approximation deterministic strategyproof mechanism where agents can misreport both the preference and location.

PDF Details

AAMAS Conference 2018 Conference Paper

Facility Location with Variable and Dynamic Populations

  • Yuho Wada
  • Tomohiro Ono
  • Taiki Todo
  • Makoto Yokoo

Facility location is a well-studied problem in social choice literature, where agents’ preferences are restricted to be single-peaked. When the number of agents is treated as a variable (e. g. , not observable a priori), a social choice function must be defined so that it can accept any possible number of preferences as input. Furthermore, there exist cases where multiple choices must be made continuously while agents dynamically arrive/leave. Under such variable and dynamic populations, a social choice function needs to give each agent an incentive to sincerely report her existence. In this paper we investigate facility location models with variable and dynamic populations. For a static, i. e. , one-shot, variable population model, we provide a necessary and sufficient condition for a social choice function to satisfy participation, as well as truthfulness, anonymity, and Pareto efficiency. The condition is given as a further restriction on the well-known median voter schemes. For a dynamic model, we first propose an online social choice function, which is optimal for the total sum of the distances between the choices in the previous and current periods, among any Pareto efficient functions. We then define a generalized class of online social choice functions and compare their performances both theoretically and experimentally.

PDF

IJCAI Conference 2018 Conference Paper

Service Exchange Problem

  • Julien Lesca
  • Taiki Todo

In this paper, we study the service exchange problem where each agent is willing to provide her service in order to receive in exchange the service of someone else. We assume that agent's preference depends both on the service that she receives and the person who receives her service. This framework is an extension of the housing market problem to preferences including a degree of externalities. We investigate the complexity of computing an individually rational and Pareto efficient allocation of services to agents for ordinal preferences, and the complexity of computing an allocation which maximizes either the utility sum or the utility of the least served agent for cardinal preferences.

PDF Details

AAAI Conference 2016 Conference Paper

False-Name-Proof Locations of Two Facilities: Economic and Algorithmic Approaches

  • Akihisa Sonoda
  • Taiki Todo
  • Makoto Yokoo

This paper considers a mechanism design problem for locating two identical facilities on an interval, in which an agent can pretend to be multiple agents. A mechanism selects a pair of locations on the interval according to the declared singlepeaked preferences of agents. An agent’s utility is determined by the location of the better one (typically the closer to her ideal point). This model can represent various application domains. For example, assume a company is going to release two models of its product line and performs a questionnaire survey in an online forum to determine their detailed specs. Typically, a customer will buy only one model, but she can answer multiple times by logging onto the forum under several email accounts. We first characterize possible outcomes of mechanisms that satisfy false-name-proofness, as well as some mild conditions. By extending the result, we completely characterize the class of false-name-proof mechanisms when locating two facilities on a circle. We then clarify the approximation ratios of the false-name-proof mechanisms on a line metric for the social and maximum costs.

PDF Details

AAMAS Conference 2016 Conference Paper

Manipulations in Two-Agent Sequential Allocation with Random Sequences

  • Yuto Tominaga
  • Taiki Todo
  • Makoto Yokoo

Sequential allocation is one of the most fundamental models for allocating indivisible items to agents in a decentralized manner, in which agents sequentially pick their favorite items among the remainder based on a pre-defined priority ordering of agents (a sequence). In recent years, algorithmic issues about agents’ manipulations have also been investigated, such as the computational complexity of verifying whether a given bundle of items is achievable and maximizing one’s utility under a given additive utility function. In this paper we consider a slightly modified model, where the selection process is divided into rounds, each agent obtains exactly one item in each round, and the sequence per round is determined uniformly at random. It is natural to expect that finding a profitable manipulation is difficult even for the case of two agents, since a manipulator must consider exponentially many possible sequences with respect to the number of rounds due to randomization. To our surprise, however, an optimal manipulation can be computed without any exploration for exponentially decaying utilities. Furthermore, for general additive utilities, although some exploration is required, it can still be done in polynomial time with respect to the number of rounds. CCS Concepts •Computing methodologies → Multi-agent systems; •Applied computing → Economics;

PDF

AAAI Conference 2015 Conference Paper

A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences

  • Etsushi Fujita
  • Julien Lesca
  • Akihisa Sonoda
  • Taiki Todo
  • Makoto Yokoo

Core-selection is a crucial property of social choice functions, or rules, in social choice literature. It is also desirable to address the incentive of agents to cheat by misreporting their preferences. This paper investigates an exchange problem where each agent may have multiple indivisible goods, agents’ preferences over sets of goods are assumed to be lexicographic, and side payments are not allowed. We propose an exchange rule called augmented top-trading-cycles (ATTC) procedure based on the original TTC procedure. We first show that the ATTC procedure is core-selecting. We then show that finding a beneficial misreport under the ATTC procedure is NP-hard. Under the ATTC procedure, we finally clarify the relationship between preference misreport and splitting, which is a different type of manipulation.

PDF Details

IJCAI Conference 2015 Conference Paper

Exchange of Indivisible Objects with Asymmetry

  • Zhaohong Sun
  • Hideaki Hata
  • Taiki Todo
  • Makoto Yokoo

In this paper we study the exchange of indivisible objects where agents’ possible preferences over the objects are strict and share a common structure among all of them, which represents a certain level of asymmetry among objects. A typical example of such an exchange model is a re-scheduling of tasks over several processors, since all task owners are naturally assumed to prefer that their tasks are assigned to fast processors rather than slow ones. We focus on designing exchange rules (a. k. a. mechanisms) that simultaneously satisfy strategyproofness, individual rationality, and Pareto efficiency. We first provide a general impossibility result for agents’ preferences that are determined in an additive manner, and then show an existence of such an exchange rule for further restricted lexicographic preferences. We finally find that for the restricted case, a previously known equivalence between the single-valuedness of the strict core and the existence of such an exchange rule does not carry over.

PDF Details

ECAI Conference 2014 Conference Paper

False-name-proof Combinatorial Auction Design via Single-minded Decomposition

  • Dengji Zhao
  • Siqi Luo
  • Taiki Todo
  • Makoto Yokoo

This paper proposes a new approach to building false-name-proof (FNP) combinatorial auctions from those that are FNP only with single-minded bidders, each of whom requires only one particular bundle. Under this approach, a general bidder is decomposed into a set of single-minded bidders, and after the decomposition the price and the allocation are determined by the FNP auctions for single-minded bidders. We first show that the auctions we get with the single-minded decomposition are FNP if those for single-minded bidders satisfy a condition called PIA. We then show that another condition, weaker than PIA, is necessary for the decomposition to build FNP auctions. To close the gap between the two conditions, we have found another sufficient condition weaker than PIA for the decomposition to produce strategy-proof mechanisms. Furthermore, we demonstrate that once we have PIA, the mechanisms created by the decomposition actually satisfy a stronger version of false-name-proofness, called false-name-proofness with withdrawal.

Details

AAAI Conference 2014 Conference Paper

Strategyproof Exchange with Multiple Private Endowments

  • Taiki Todo
  • Haixin Sun
  • Makoto Yokoo

We study a mechanism design problem for exchange economies where each agent is initially endowed with a set of indivisible goods and side payments are not allowed. We assume each agent can withhold some endowments, as well as misreport her preference. Under this assumption, strategyproofness requires that for each agent, reporting her true preference with revealing all her endowments is a dominant strategy, and thus implies individual rationality. Our objective in this paper is to analyze the effect of such private ownership in exchange economies with multiple endowments. As fundamental results, we first show that the revelation principle holds under a natural assumption and that strategyproofness and Pareto efficiency are incompatible even under the lexicographic preference domain. We then propose a class of exchange rules, each of which has a corresponding directed graph to prescribe possible trades, and provide necessary and sufficient conditions on the graph structure so that they satisfy strategyproofness.

PDF Details

AAAI Conference 2014 Conference Paper

Two Case Studies for Trading Multiple Indivisible Goods with Indifferences

  • Akihisa Sonoda
  • Etsushi Fujita
  • Taiki Todo
  • Makoto Yokoo

Individual rationality, Pareto efficiency, and strategyproofness are crucial properties of decision making functions, or mechanisms, in social choice literatures. In this paper we investigate mechanisms for exchange models where each agent is initially endowed with a set of goods and may have indifferences on distinct bundles of goods, and monetary transfers are not allowed. Sönmez (1999) showed that in such models, those three properties are not compatible in general. The impossibility, however, only holds under an assumption on preference domains. The main purpose of this paper is to discuss the compatibility of those three properties when the assumption does not hold. We first establish a preference domain called top-only preferences, which violates the assumption, and develop a class of exchange mechanisms that satisfy all those properties. Each mechanism in the class utilizes one instance of the mechanisms introduced by Saban and Sethuraman (2013). We also find a class of preference domains called m-chotomous preferences, where the assumption fails and these properties are incompatible.

PDF Details

AAMAS Conference 2012 Conference Paper

False-name-proofness in Online Mechanisms

  • Taiki Todo
  • Takayuki Mouri
  • Atsushi Iwasaki
  • Makoto Yokoo

In real electronic markets, each bidder arrives and departs over time. Thus, such a mechanism that must make decisions dynamically without knowledge of the future is called an \emph{online mechanism}. In an online mechanism, it is very unlikely that the mechanism designer knows the number of bidders beforehand or can verify the identity of all of them. Thus, a bidder can easily submit multiple bids (\emph{false-name bids}) using different identifiers (e. g. , different e-mail addresses). In this paper, we formalize false-name manipulations in online mechanisms and identify a simple property called (value, time, identifier)-monotonicity that characterizes the allocation rules of false-name-proof online auction mechanisms. To the best of our knowledge, this is the first work on false-name-proof online mechanisms. Furthermore, we develop a new false-name-proof online auction mechanism for $k$ identical items. When $k$=1, this mechanism corresponds to the optimal stopping rule of the secretary problem where the number of candidates is unknown. We show that the competitive ratio of this mechanism for efficiency is 4 and independent from $k$ by assuming that only the distribution of bidders' arrival times is known and that the bidders are impatient.

PDF

AAMAS Conference 2011 Conference Paper

False-name-proof Mechanism Design without Money

  • Taiki Todo
  • Atsushi Iwasaki
  • Makoto Yokoo

Mechanism design studies how to design mechanisms that result in good outcomes even when agents strategically report their preferences. In traditional settings, it is assumed that a mechanism can enforce payments to give an incentive for agents to act honestly. However, in many Internet application domains, introducing monetary transfers is impossible or undesirable. Also, in such highly anonymous settings as the Internet, declaring preferences dishonestly is not the only way to manipulate the mechanism. Often, it is possible for an agent to pretend to be multiple agents and submit multiple reports under different identifiers, e. g. , by creating different e-mail addresses. The effect of such false-name manipulations can be more serious in a mechanism without monetary transfers, since submitting multiple reports would have no risk. In this paper, we present a case study in false-name-proof mechanism design without money. In our basic setting, agents are located on a real line, and the mechanism must select the location of a public facility; the cost of an agent is its distance to the facility. This setting is called the facility location problem and can represent various situations where an agent's preference is single-peaked. First, we fully characterize the deterministic false-name-proof facility location mechanisms in this basic setting. By utilizing this characterization, we show the tight bounds of the approximation ratios for two objective functions: social cost and maximum cost. We then extend the results in two natural directions: a domain where a mechanism can be randomized and a domain where agents are located in a tree. Furthermore, we clarify the connections between false-name-proofness and other related properties.

PDF

IJCAI Conference 2011 Conference Paper

Generalizing Envy-Freeness toward Group of Agents

  • Taiki Todo
  • Runcong Li
  • Xuemei Hu
  • Takayuki Mouri
  • Atsushi Iwasaki
  • Makoto Yokoo

Envy-freeness is a well-known fairness concept for analyzing mechanisms. Its traditional definition requires that no individual envies another individual. However, an individual (or a group of agents) may envy another group, even if she (or they) does not envy another individual. In mechanisms with monetary transfer, such as combinatorial auctions, considering such fairness requirements, which are refinements of traditional envy-freeness, is meaningful and brings up a new interesting research direction in mechanism design. In this paper, we introduce two new concepts of fairness called envy-freeness of an individual toward a group, and envy-freeness of a group toward a group. They are natural extensions of traditional envy-freeness. We discuss combinatorial auction mechanisms that satisfy these concepts. First, we characterize such mechanisms by focusing on their allocation rules. Then we clarify the connections between these concepts and three other properties: the core, strategy-proofness, and false-name-proofness.

PDF Details DOI

AAMAS Conference 2010 Conference Paper

Characterization of False-name-proof Social Choice Mechanisms

  • Taiki Todo

Mechanism Design has been developed as a significant tool to model and analyze markets, economies, and societies in the real-world. On the Internet, however, we face some unexpected problems such as false-name manipulations, and traditional mechanism design does not work sufficiently. In this thesis, we will develop mechanism design into a more applicable theory for computer sciences and economics on the Internet. Specifically, we characterize social choice mechanisms that are robust against false-name manipulations.

PDF

AAMAS Conference 2010 Conference Paper

Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms

  • Atsushi Iwasaki
  • Vincent Conitzer
  • Yoshifusa Omori
  • Yuko Sakurai
  • Taiki Todo
  • Mingyu Guo
  • Makoto Yokoo

This paper analyzes the worst-case efficiency ratio of false-name-proofcombinatorial auction mechanisms. False-name-proofness generalizesstrategy-proofness, by assuming that a bidder can submit multiple bidsunder fictitious identifiers. Even the well-known Vickrey-Clarke-Grovesmechanism is not false-name-proof. It has previously been shown thatthere is no false-name-proof mechanism that always achieves a Paretoefficient allocation. Hence, if false-name bids are possible, we need to sacrifice efficiency to some extent. This leaves the natural question of how much surplusmust be sacrificed. To answer this question, this paper focuses on worst-case analysis. Specifically, we consider thefraction of the Pareto-efficient surplus that we obtain, and try tomaximize this fraction in the worst case, under the constraint offalse-name-proofness. As far as we are aware, this is the first attempt to examine theworst-case efficiency of false-name-proof mechanisms. We show that the worst-case efficiency ratio of any false-name-proofmechanism that satisfies some apparently minor assumptions is atmost $2/(m+1)$ for auctions with $m$ different goods. We also observe that the worst-case efficiency ratioof existing false-name-proof mechanisms is generally $1/m$ or 0. Finally, we propose a novel mechanism, called the adaptive reserve price mechanism, which is false-name-proof when all bidders are single-minded, and its worst-case efficiency ratio is $2/(m+1)$, i. e. , optimal.

PDF

AAMAS Conference 2009 Conference Paper

Characterizing False-name-proof Allocation Rules in Combinatorial Auctions

  • Taiki Todo
  • Atsushi Iwasaki
  • Makoto Yokoo
  • Yuko Sakurai

A combinatorial auction mechanism consists of an allocation rule that defines the allocation of goods for each agent, and a payment rule that defines the payment of each winner. There have been several studies on characterizing strategyproof allocation rules. In particular, a condition called weakmonotonicity has been identified as a full characterization of strategy-proof allocation rules. More specifically, for an allocation rule, there exists an appropriate payment rule so that the mechanism becomes strategy-proof if and only if it satisfies weak-monotonicity. In this paper, we identify a condition called sub-additivity which characterizes false-name-proof allocation rules. Falsename-proofness generalizes strategy-proofness, by assuming that a bidder can submit multiple bids under fictitious identifiers. As far as the authors are aware, this is the first attempt to characterize false-name-proof allocation rules. We can utilize this characterization for developing a new false-name-proof mechanism, since we can concentrate on designing an allocation rule. As long as the allocation rule satisfies weak-monotonicity and sub-additivity, there always exists an appropriate payment rule. Furthermore, by utilizing the sub-additivity condition, we can easily verify whether a mechanism is false-name-proof. To our surprise, we found that two mechanisms, which were believed to be false-nameproof, do not satisfy sub-additivity; they are not false-nameproof. As demonstrated in these examples, our characterization is quite useful for mechanism verification.

PDF
v2026.09.13