OPTIMIZATION METHOD, OPTIMIZATION APPARATUS AND PROGRAM

Abstract

An optimization method according to one embodiment which is executed by a computer, the method including: an input procedure of inputting an acceptance probability function indicating a probability that each participant participating in a crowdsourcing market will accept a price, and a matching value indicating a value when each resource in the crowdsourcing market is allocated to each participant; a formulation procedure of formulating a first optimization problem for determining an optimal price that maximizes a profit of a provider of the crowdsourcing market using the acceptance probability function and the matching value; and an optimization procedure of calculating the optimal price by solving the first optimization problem according to a feature of the acceptance probability function.

Claims

1. An optimization method executed by a computer including a memory and a processor, the optimization method comprising: receiving as input an acceptance probability function indicating a probability that each participant participating in a crowdsourcing market accepts a price, and a matching value indicating a value when each resource in the crowdsourcing market is allocated to each participant; formulating a first optimization problem for determining an optimal price that maximizes a profit of a provider of the crowdsourcing market using the acceptance probability function and the matching value; and calculating the optimal price by solving the first optimization problem according to a feature of the acceptance probability function.

2. The optimization method according to claim 1, wherein in the optimization procedure, the optimal price is calculated by transforming the first optimization problem into a second optimization problem using an approximate value of an objective function of the first optimization problem and solving the second optimization problem.

3. The optimization method according to claim 2, wherein an optimal solution of the second optimization problem is a solution in which a degree of approximation of 3 is guaranteed for an optimal solution of the first optimization problem.

4. The optimization method according to claim 2, wherein denoting an index representing each of the participants as i, a variable representing the price as x, and an acceptance probability function of the participant i as Si(x), in the optimization procedure, when the acceptance probability function Si(x) is represented by a linear function with upper and lower limits, the optimal price is calculated by transforming the second optimization problem into a minimum convex secondary cost flow problem and solving the minimum convex secondary cost flow problem, and when the acceptance probability function Si(x) is bijective and each function represented by 1−Si(x) is a Monotone hazard rate function, the optimal price is calculated by transforming the second optimization problem into a minimum convex cost flow problem and solving the minimum convex cost flow problem.

5. The optimization method according to claim 4, wherein in the optimization procedure, when the acceptance probability function Si(x) is not represented by a linear function with upper and lower limits and the acceptance probability function Si(x) is not bijective or each function represented by 1−Si(x) is not a Monotone hazard rate function, the optimal price is calculated by solving the second optimization problem using a heuristic solution including Bayesian optimization and simulated annealing.

6. An optimization apparatus comprising: a memory; and a processor configured to receive as input an acceptance probability function indicating a probability that each participant participating in a crowdsourcing market will accept a price, and a matching value indicating a value when each resource in the crowdsourcing market is allocated to each participant; formulate a first optimization problem for determining an optimal price that maximizes a profit of a provider of the crowdsourcing market using the acceptance probability function and the matching value; and calculate the optimal price by solving the first optimization problem according to a feature of the acceptance probability function.

7. A non-transitory computer-readable recording medium having computer-readable instructions stored thereon, which when executed, cause a computer to execute the optimization method according to claim 1.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0014] FIG. 1 is a diagram illustrating an example of a value when allocating a resource to a participant.

[0015] FIG. 2 is a diagram illustrating an example of a minimum convex secondary cost flow problem.

[0016] FIG. 3 is a diagram illustrating an example of a minimum convex cost flow problem.

[0017] FIG. 4 is a diagram illustrating an example of a functional configuration of a price optimization apparatus according to the present embodiment.

[0018] FIG. 5 is a flowchart illustrating an example of a flow of price optimization processing according to the present embodiment.

[0019] FIG. 6 is a flowchart illustrating an example of a flow of solution calculation processing of optimization problems according to the present embodiment.

[0020] FIG. 7 is a diagram illustrating an example of a hardware configuration of the price optimization apparatus according to the present embodiment.

DESCRIPTION OF EMBODIMENTS

[0021] Hereinafter, one embodiment of the present invention will be described. In the present embodiment, a crowdsourcing market is assumed that provides a service in a process in which (a) in a situation where a certain number of tasks or workers exist, (b) a service provider determines a price of the corresponding worker or task, and (c) the task or worker is allocated to an object to which the price has been accepted, and a price optimization apparatus 10 will be described that is capable of calculating an optimal price in consideration of a matching value and a supply and demand balance in this crowdsourcing market.

Theoretical Configuration of Present Embodiment

[0022] A theoretical configuration when calculating the optimal price in consideration of the matching value and the supply and demand balance by the price optimization apparatus 10 according to the present embodiment will be described.

[0023] <<Formulation of Problem of Maximizing Profit of Service Provider>>

[0024] It is assumed that there are two sides in the crowdsourcing market assumed in the present embodiment. A situation is considered where there is a limited number of resources on one side and participants on the other side participate in response to the price. For example, a crowdsourcing platform in which a translation task (participant) emerges in response to a fee set in a situation where a certain number of workers (resources) exist in the market, a taxi-hailing platform in which an orderer (participant) emerges in response to a fee set for each taxi driver while a certain number of taxi drivers (resources) are working in town, and the like correspond to the crowdsourcing market corresponding to the above situation.

[0025] In the present embodiment, it is assumed that the number of participants in the crowdsourcing market is n, and there are m limited resources. At this time, it is assumed that i=1, 2, . . . , n represents an index of each participant, and j=1, 2, . . . , m represents an index of each resource. Each participant i has an acceptance probability S.sub.i(x) for a price x. The acceptance probability S.sub.i(x) is a function representing the probability of accepting the price x when the price x is presented to the participant i, and the amount of demand is stochastically determined by the function. For example, in a crowdsourcing platform in which workers and tasks are resources and participants, respectively, or a taxi-hailing platform in which taxi drivers and orderers are resources and participants, respectively, the acceptance probability S.sub.i(x) is generally higher when the price x is lower, and the acceptance probability S.sub.i(x) is lower when the price x is higher.

[0026] In addition, there is a positive or negative value (that is, a matching value) in allocating a resource j to a participant i, which is represented by w.sub.ij∈R (where R is a set of all real numbers). Note that the value w.sub.ij is a continuous value indicating a degree or the like of compatibility of the participant i and the resource j, and examples thereof include a degree indicating how good the worker j is at the translation task i, a value indicating how far the current location of the taxi driver j is away from the current location of the orderer i, and the like. As an example, in a case of n=2 and m=3, a value w.sub.ij when allocating the resource j to the participant i is illustrated in FIG. 1. As illustrated in FIG. 1, there is a value w.sub.ij when allocating each resource j to each participant i.

[0027] In addition, a vector having a price p.sub.i∈R presented to each participant i as the i-th element is referred to as a price vector, and denoted as p∈R.sup.n. At this time, it is assumed that the service provider maximizes the profit by solving an optimization problem shown in Expression (1) below.

[00001]$\begin{array}{cc}\left[\mathrm{Math}.1\right]& \\ \begin{array}{cc}\underset{z}{\max }& \left(p_i+w_{\mathrm{ij}}\right).Math.z_{\mathrm{ij}}\\ s.t.& \underset{j}{.Math.}{z}_{\mathrm{ij}}\le a_1\left(i=1,2,.Math.,n\right)\\ & \underset{i}{.Math.}{z}_{ij}\le 1\left(j=1,2,.Math.,m\right)\\ & z_{\mathrm{ij}}\in \left\{0,1\right\}\left(i=1,2,.Math.,n,j=1,2,.Math.,m\right)\end{array}& \left(1\right)\end{array}$

[0028] where a∈{0, 1}.sup.n is a vector indicating acceptance or non-acceptance of each participant, and the i-th element is a.sub.i. If a.sub.i=1, it represents that the participant i accepts the price p.sub.i, or if a.sub.i=0, it represents that the participant i rejects the price p.sub.i. Furthermore, z.sub.ij represents whether or not to allocate the resource j to the participant i; if z.sub.ij=1, it represents that the allocation is performed, or if z.sub.ij=0, it represents that the allocation is not performed.

[0029] Since the price p.sub.i represents the amount of money (here, if negative, the amount paid to the participant i) that the service provider collects from the participant i, and w.sub.ij represents the value when the resource j is allocated to the participant i, (p.sub.i+w.sub.ij) in the objective function of the optimization problem shown in Expression (1) above represents the profit when the resource j is allocated to the participant i. Note that the case where the price p.sub.i is negative corresponds to, for example, a case where the participant side is a worker and the service provider pays the worker side a salary.

[0030] In addition, the first constraint condition is a constraint to allocate resources only to a participant who has accepted the price, and the second constraint condition is a constraint to allocate only one resource (that is, a constraint that prevents one resource from being allocated to a plurality of participants).

[0031] At this time, in the present embodiment, solving an optimization problem shown in Expression (2) below will be considered.

[00002]$$\begin{gathered} \begin{array}{cc}\left[\mathrm{Math}.2\right]& \\ \underset{p}{\max }{𝔼}_{a\sim \mathrm{Pr}\left(.Math.|p\right)}\left[f\left(p,a\right)\right] \\ s.t.p\in {ℝ}^n& \left(2\right)\end{array} \end{gathered}$$$\mathrm{where}$$\begin{array}{cc}\left[\mathrm{Math}.3\right]& \\ \mathrm{Pr}\left(a|p\right):=\underset{i=1}{\overset{n}{.Math.}}\left\{{S_i\left(p_i\right)}^{a_i}{\left(1-S_i\left(p_i\right)\right)}^{\left(1-a_i\right)}\right\}& \end{array}$

[0032] In addition, f(p, a) represents an optimal value of the optimization problem shown in Expression (1) under a and p, i.e., the profit of the service provider. That is, the optimization problem shown in Expression (2) above is a problem of obtaining p that maximizes the expected value (expected profit) of the profit f(p, a) when sampling a according to the probability Pr(.Math.|p). Note that the optimization problem shown in Expression (2) above includes the optimization problem formulated in Non Patent Literature 2 described above.

[0033] <<Solution of Optimization Problem Shown in Expression (2)>>

[0034] By solving the optimization problem shown in Expression (2) above, it is possible to calculate and determine an optimal price. Any optimization method may be used as long as an optimal solution or an approximate solution of the optimization problem shown in Expression (2) can be derived. For example, a solution may be obtained by a genetic algorithm, Bayesian optimization, or the like, or a newly proposed algorithm or the like may be used in the future.

[0035] However, since there is no conventional method capable of solving the optimization problem shown in Expression (2) above at high speed at present, an approximate solution is proposed below. Note that since the optimization problem shown in Expression (2) above includes the optimization problem formulated in Non Patent Literature 2 described above, the approximate solution proposed below can also be applied to the optimization problem formulated in Non Patent Literature 2.

[0036] The approximate solution proposed in the present embodiment branches into any of procedures 1-2a, 1-2b, and 1-2c according to the feature of the acceptance probability S.sub.i after completing a common procedure 1-1.

[0037] Procedure 1-1: Approximation of Objective Functions E.sub.a to Pr(.Math.|p) [f(p, a)]

[0038] In order to obtain an approximate value of the objective functions E.sub.a to Pr(.Math.|p) [f(p, a)] of the optimization problem shown in Expression (2) above, an optimization problem shown in Expression (3) below is considered.

[00003]$\begin{array}{cc}\left[\mathrm{Math}.4\right]& \\ \begin{array}{cc}\underset{z}{\max }& \left(p_i+w_{ij}\right).Math.z_{ij}\\ s.t.& \underset{j}{.Math.}{z}_{\mathrm{ij}}\le S_i\left(p_i\right)\left(i=1,2,.Math.,n\right)\\ & \underset{i}{.Math.}{z}_{ij}\le 1\left(j=1,2,.Math.,m\right)\\ & z_{ij}\in \left\{0,1\right\}\left(i=1,2,.Math.,n,j=1,2,.Math.,m\right)\end{array}& \left(3\right)\end{array}$

[0039] Denoting the optimal value for a specific p of the optimization problem shown in Expression (3) as follows:

{circumflex over (f)}(p)  [Math. 5]

[00004]$\begin{array}{cc}\left[\mathrm{Math}.6\right]& \\ \frac{1}{3}.Math.\hat{f}\left(p\right)\le {𝔼}_{a\sim \mathrm{Pr}\left(.Math.|p\right)}\left[f\left(p,a\right)\right]\le \hat{f}\left(p\right)& \end{array}$

[0040] is satisfied for any p. Note that hereinafter, in the text of the specification, the optimal value for a specific p of the optimization problem shown in Expression (3) above is denoted as “{circumflex over ( )}f(p)”.

[0041] In a case where {circumflex over ( )}f(p) is used as E.sub.a to Pr(.Math.|p) [f(p, a)], the optimization problem shown in Expression (2) above is formulated as in the following Expression (4):

[00005]$\begin{array}{cc}\left[\mathrm{Math}.7\right]& \\ \begin{array}{cc}\underset{p,z}{\max }& \left(p_i+w_{\mathrm{ij}}\right).Math.z_{\mathrm{ij}}\\ s.t.& \underset{j}{.Math.}{z}_{ij}\le S_1\left(p_i\right)\left(i=1,2,.Math.,n\right)\\ & \underset{j}{.Math.}{z}_{ij}\le 1\left(j=1,2,.Math.,m\right)\\ & 0\le z_{\mathrm{ij}}\le 1\left(i=1,2,.Math.,n,j=1,2,.Math.,m\right)\end{array}& \left(4\right)\end{array}$$\mathrm{For}\mathrm{any}p,$$\begin{array}{cc}\left[\mathrm{Math}.8\right]& \\ \frac{1}{3}.Math.\hat{f}\left(p\right)\le {𝔼}_{a\sim \mathrm{Pr}\left(.Math.|p\right)}\left[f\left(p,a\right)\right]\le \hat{f}\left(p\right)& \end{array}$

[0042] is satisfied. Therefore, it can be shown that an optimal solution p* obtained by solving the optimization problem shown in Expression (4) above is an approximate solution in which a degree of approximation of 3 is guaranteed for the optimization problem shown in Expression (2) above. That is, it can be shown that the ratio between the optimal solution of the optimization problem shown in Expression (4) above and the optimal solution of the optimization problem shown in Expression (2) above is 3 or less.

[0043] Therefore, in the following, it is considered to solve the optimization problem shown in Expression (4) above at high speed according to the feature of the acceptance probability S.sub.i to obtain an approximate solution.

[0044] Procedure 1-2a: Solution of Optimization Problem Shown in Expression (4) in a Case where the Acceptance Probability S.sub.i is Represented by a Linear Function with Upper and Lower Limits

[0045] It is assumed that the acceptance probability S.sub.i(x) is a continuous function that can be expressed as follows:

[00006]$\begin{array}{cc}\left[\mathrm{Math}.9\right]& \\ S_i\left(x\right)=\{\begin{array}{cc}{L}_i& \left(x>p_i^u\right)\\ -c_i.Math.x+d_i& \left(p_i^k\le x\le p_i^u\right)\\ 0& \left(x<p_i^u\right)\end{array}& \end{array}$

[0046] using certain L.sub.i, c.sub.i, d.sub.i, p.sub.i.sup.k, and p.sub.i.sup.u. Here, c.sub.i is positive. In addition, it is assumed that a vector having p.sub.i.sup.k as the i-th element is p.sup.k, and a vector having p.sub.i.sup.u as the i-th element is p.sup.u.

[0047] At this time, it can be shown that there is an optimal solution p* that satisfies p.sup.k≤p*≤p.sup.u, and in addition, satisfies the equality under the first constraint condition (that is, for i=1, 2, . . . , n, the constraint condition that the sum of z.sub.ij for all j is equal to or less than S.sub.i(p.sub.i)) for all i among the optimal solutions of the optimization problem shown in Expression (4) above. Therefore, the optimization problem shown in Expression (4) above is equivalent to the following optimization problem:

[00007]$\begin{array}{cc}\left[\mathrm{Math}.10\right]& \\ \begin{array}{cc}\underset{p,z}{\max }& \underset{i}{.Math.}\left(-\frac{1}{c_i}.{\left(\underset{j}{.Math.}{z}_{\mathrm{ij}}\right)}^2+\frac{d_i}{c_i}.Math.\underset{j}{.Math.}{z}_{\mathrm{ij}}\right)+\underset{\mathrm{ij}}{.Math.}{w}_{\mathrm{ij}}.Math.z_{\mathrm{ij}}\\ s.t.& \underset{j}{.Math.}{z}_{\mathrm{ij}}=-c_i.Math.p_i+d_i\left(i=1,2,.Math.,n\right)\\ & \underset{i}{.Math.}{z}_{\mathrm{ij}}\le 1\left(j=1,2,.Math.,m\right)\\ & 0\le z_{ij}\le 1\left(i=1,2,.Math.,n,j=1,2,.Math.,m\right)\\ & p^k\le p\le p^u\end{array}& \end{array}$

[0048] Here, p is deleted from the objective function by substituting the equation of the first constraint condition of the optimization problem shown in Expression (4) above.

[0049] At this time, new subscripts s and t are prepared. It is assumed that for all i, z.sub.si:=Σ.sub.jz.sub.ij, and for all j, z.sub.jt:=Σ.sub.iz.sub.ij. In addition, when z.sub.st is provided as a slack variable, the above optimization problem can be rewritten as the following Expression (5):

[00008]$\begin{array}{cc}\left[\mathrm{Math}.11\right]& \\ \begin{array}{cc}\underset{z}{\max }& \underset{i}{.Math.}\left(\frac{1}{c_i}.Math.z_{\mathrm{si}}^2-\frac{d_i}{c_i}{z}_{\mathrm{si}}\right)-\underset{\mathrm{ij}}{.Math.}{w}_{\mathrm{ij}}.Math.z_{\mathrm{ij}}\\ s.t.& \underset{i}{.Math.}{z}_{\mathrm{si}}+z_{\mathrm{st}}=n,\underset{j}{.Math.}{z}_{\mathrm{jt}}+z_{\mathrm{st}}=n\\ & z_{\mathrm{si}}-\underset{j}{.Math.}{z}_{\mathrm{ij}}=0\left(i=1,2,.Math.,n\right)\\ & \underset{i}{.Math.}{z}_{\mathrm{ij}}-z_{jt}=0\left(j=1,2,.Math.,m\right)\\ & 0\le z_{\mathrm{si}}\le L_i\left(i=1,2,.Math.,n\right)\\ & 0\le z_{jt}\le 1\left(j=1,2,.Math.,m\right)\\ & 0\le z_{\mathrm{ij}}\le 1\left(i=1,2,.Math.,n,j=1,2,.Math.,m\right)\\ & 0\le z_{st}\le n\end{array}& \left(5\right)\end{array}$

[0050] For the optimal solution z* of the optimization problem shown in Expression (5), assuming that

[00009]$\begin{array}{cc}\left[\mathrm{Math}.12\right]& \\ p_i^{*}:=-\frac{1}{c_i}.Math.z_{\mathrm{si}}+\frac{d_i}{c_i}& \end{array}$

[0051] it can be shown that (p*, z*) is the optimal solution of the optimization problem shown in Expression (4) above. Therefore, the solution can be obtained by solving the optimization problem shown in Expression (5) above.

[0052] Since the optimization problem shown in Expression (5) is a minimum convex secondary cost flow problem, it can be solved at high speed using an existing solution. Note that the minimum convex secondary cost flow problem can be illustrated as a flow diagram on a network, and as an example, the minimum convex secondary cost flow problem shown in Expression (5) above when n=2 and m=3 is illustrated in FIG. 2.

[0053] Procedure 1-2b: Solution of Optimization Problem Shown in Expression (4) in a Case where the Acceptance Probability S.sub.i is Bijective and 1−S.sub.i is a Monotone Hazard Rate Function

[0054] When the following assumption is satisfied for probability Q.sub.i(x):=1−S.sub.i(x), Q.sub.i(x) is called a Monotone hazard rate function for x.

[0055] Assumption:

[00010]$\begin{array}{cc}\left[\mathrm{Math}.13\right]& \\ \frac{Q_i^{\prime }\left(x\right)}{1-Q_i\left(x\right)}& \end{array}$

[0056] is monotonically non-increasing with respect to x. Note that Q.sub.i′(x) is a function (derivative) obtained by differentiating Q.sub.i(x) with respect to x.

[0057] The above assumption is a relatively weak assumption including that Q.sub.i is a normal distribution, a uniform distribution, a cumulative distribution function of an exponential distribution, or the like. Here, a case where the acceptance probability S.sub.i(x) is bijective and 1−S.sub.i(x) is a Monotone hazard rate function is considered.

[0058] First, since the first constraint condition of the optimization problem shown in Expression (4) above always satisfies the equality in a certain optimal solution p*,

p.sub.i:=S.sub.i.sup.−1(Σ.sub.jz.sub.ij)  [Math. 14]

[0059] the following optimization problem is considered with the above setting.

[00011]$\begin{array}{cc}\left[\mathrm{Math}.15\right]& \\ \begin{array}{cc}\underset{z}{\max }& \underset{i}{.Math.}{S}_i^{-1}\left(\underset{j}{.Math.}{z}_{\mathrm{ij}}\right)\underset{j}{.Math.}{z}_{\mathrm{ij}}+\underset{\mathrm{ij}}{.Math.}{w}_{\mathrm{ij}}.Math.z_{\mathrm{ij}}\\ s.t.& \underset{j}{.Math.}{z}_{\mathrm{ij}}\in X\left(i=1,2,.Math.,m\right)\\ & \underset{i}{.Math.}{z}_{\mathrm{ij}}\le 1\left(j=1,2,.Math.,m\right)\\ & 0\le z_{\mathrm{ij}}\le 1\left(i=1,2,.Math.,n,j=1,2,.Math.,m\right)\end{array}& \end{array}$

[0060] where X is a domain of the function S.sub.i.sup.−1. For the optimal solution z* of this optimization problem, with the following setting:

p*.sub.i:=S.sub.i.sup.−1(Σ.sub.jz*.sub.ij)  [Math. 16]

[0061] (p*, z*) is the optimal solution of the optimization problem shown in Expression (4) above.

[0062] At this time, new subscripts s and t are prepared. It is assumed that for all i, z.sub.si:=Σ.sub.jz.sub.ij, and for all j, z.sub.jt:=Σ.sub.iz.sub.ij. In addition, when z.sub.st is prepared as a slack variable, the above optimization problem can be rewritten as in the following Expression (6):

[00012]$\begin{array}{cc}\left[\mathrm{Math}.17\right]& \\ \begin{array}{cc}\underset{p,z}{\min }& \underset{i}{.Math.}-S_i^{-1}\left(z_{\mathrm{si}}\right).Math.z_{\mathrm{si}}-\underset{\mathrm{ij}}{.Math.}{w}_{\mathrm{ij}}.Math.z_{\mathrm{ij}}\\ s.t.& \underset{i}{.Math.}{z}_{\mathrm{si}}+z_{st}=n,\underset{j}{.Math.}{z}_{jt}+z_{st}=n\\ & z_{\mathrm{si}}-\underset{j}{.Math.}{z}_{\mathrm{ij}}=0\left(i=1,2,.Math.,n\right)\\ & \underset{i}{.Math.}{z}_{\mathrm{ij}}-z_{jt}=0\left(j=1,2,.Math.,m\right)\\ & z_{\mathrm{si}}\in X\left(i=1,2,.Math.,n\right)\\ & 0\le z_{jt}\le 1\left(j=1,2,.Math.,m\right)\\ & 0\le z_{\mathrm{ij}}\le 1\left(i=1,2,.Math.,n,j=1,2,.Math.,m\right)\\ & 0\le z_{st}\le n\end{array}& \left(6\right)\end{array}$

[0063] The optimization problem shown in Expression (6) is a capacity-constrained minimum cost flow problem. At this time, according to the above assumption, it can be shown that the objective function of the optimization problem shown in Expression (6) above is a convex function. Therefore, since the optimization problem shown in Expression (6) is a minimum convex cost flow problem, it can be solved at high speed using an existing solution. Note that the minimum convex cost flow problem can be illustrated as a flow diagram on a network, and as an example, the minimum convex cost flow problem shown in Expression (6) above when n=2 and m=3 is illustrated in FIG. 3.

[0064] Procedure 1-2c: Solution of Optimization Problem Shown in Expression (4) in a Case where the Acceptance Probability S.sub.i is Other

[0065] In a case where the acceptance probability S.sub.i is a general function that does not meet the conditions of 1-2a and 1-2b above, the optimization problem shown in Expression (4) above is a non-convex optimization problem. Therefore, by using a heuristic solution such as Bayesian optimization or simulated annealing, it is possible to obtain an optimal solution or an approximate solution of the optimization problem shown in Expression (4) above.

[0066] Note that, in the present embodiment, although a case where an optimal price for a participant is calculated in a crowdsourcing market that provides a service in the process of (a) to (c) described above has been described, the present invention is not limited thereto, and can be applied to any problem that can result in the optimization problem shown in Expression (2) above.

[0067] <Functional Configuration of Price Optimization Apparatus 10>

[0068] Next, a functional configuration of the price optimization apparatus 10 according to the present embodiment will be described with reference to FIG. 4. FIG. 4 is a diagram illustrating an example of a functional configuration of the price optimization apparatus 10 according to the present embodiment.

[0069] As illustrated in FIG. 4, the price optimization apparatus 10 according to the present embodiment includes an input unit 101, a formulation unit 102, an optimization unit 103, and an output unit 104.

[0070] The input unit 101 receives as input various parameters (the acceptance probability S.sub.i(x) and the value w.sub.ij when the resource j is allocated to the participant i) given to the price optimization apparatus 10. Note that the input unit 101 may input these various parameters from any input source. For example, the input unit 101 may receive as input these various parameters by reading them from an auxiliary storage device or the like; may receive as input these various parameters by receiving them from another device or the like connected via a communication network or the like; or may receive as input these various parameters by receiving an input operation of a user or the like.

[0071] The formulation unit 102 formulates an optimization problem shown in Expression (2) above using various parameters input by the input unit 101.

[0072] The optimization unit 103 calculates an approximate solution of the optimization problem shown in Expression (2) formulated by the formulation unit 102. At this time, the optimization unit 103 transforms the optimization problem shown in Expression (2) into the optimization problem shown in Expression (4), and then, calculates an approximate solution by any of the procedures 1-2a, 1-2b, and 1-2c according to the feature of the acceptance probability S.sub.i(x). Note that, as described above, the solution of the optimization problem shown in Expression (4) is an approximate solution in which the degree of approximation of 3 is guaranteed for the optimization problem shown in Expression (2).

[0073] The output unit 104 outputs the approximate solution (that is, the price vector p having the price p.sub.i for each participant i as an element) calculated by the optimization unit 103. Note that the output unit 104 may output the approximate solution to any output destination. For example, the output unit 104 may output (store) the approximate solution to an auxiliary storage device or the like; may output (transmit) the approximate solution to another device or the like connected via a communication network or the like; or may output (display) the approximate solution to a display device such as a display.

[0074] Note that, in the example illustrated in FIG. 4, a case where one price optimization apparatus 10 includes the respective functional units has been illustrated, but the present invention is not limited thereto, and a plurality of devices may include the respective functional units in a distributed manner. For example, there may be two devices of a formulation device and an optimization apparatus, the formulation device may include the formulation unit 102, and the optimization apparatus may include the optimization unit 103.

[0075] <Flow of Price Optimization Processing>

[0076] Next, a flow of price optimization processing executed by the price optimization apparatus 10 according to the present embodiment will be described with reference to FIG. 5. FIG. 5 is a flowchart illustrating an example of a flow of price optimization processing according to the present embodiment.

[0077] First, the input unit 101 receives as input various parameters (that is, the acceptance probability S.sub.i(x) and the value w.sub.ij when the resource j is allocated to the participant i) given to the price optimization apparatus 10 (step S101).

[0078] Next, the formulation unit 102 formulates the optimization problem shown in Expression (2) above using the various parameters input in step S101 above (step S102).

[0079] Next, the optimization unit 103 calculates an approximate solution (an approximate solution in which a degree of approximation of 3 is guaranteed for the optimal solution) of the optimization problem shown in Expression (2) formulated in step S102 above (step S103). Details of the processing flow in step S103 will be described later.

[0080] Then, the output unit 104 outputs the approximate solution (that is, the price vector p having the price p.sub.i for each participant i as an element) calculated in step S103 above (step S104).

[0081] Here, the flow of the processing of calculating the approximate solution of the optimization problem shown in Expression (2) in step S103 above will be described with reference to FIG. 6. FIG. 6 is a flowchart illustrating an example of a flow of solution calculation processing of optimization problems according to the present embodiment.

[0082] First, the optimization unit 103 transforms the optimization problem shown in Expression (2) formulated in step S102 above into the optimization problem shown in Expression (4) above (step S201). That is, the optimization unit 103 transforms the optimization problem shown in Expression (2) into the optimization problem shown in Expression (4) by the above procedure 1-1.

[0083] Next, the optimization unit 103 determines whether or not the acceptance probability S.sub.i(x) input in step S101 above is represented by a linear function with upper and lower limits (step S202).

[0084] If it is determined in step S202 above that the acceptance probability S.sub.i(x) is represented by a linear function with upper and lower limits (YES in step S202), the optimization unit 103 calculates a solution by the above procedure 1-2a (step S203). That is, the optimization unit 103 transforms the optimization problem shown in Expression (4) into the optimization problem shown in Expression (5), and then, calculates the optimal solution of the optimization problem shown in Expression (5) using an existing solution to the minimum convex secondary cost flow problem.

[0085] On the other hand, if it is not determined in step S202 above that the acceptance probability S.sub.i(x) is represented by a linear function with upper and lower limits (NO in step S202), the optimization unit 103 determines whether or not the acceptance probability S.sub.i(x) is bijective and 1−S.sub.i(x) is a Monotone hazard rate function (step S204).

[0086] If it is determined in step S204 above that the acceptance probability S.sub.i(x) is bijective and 1−S.sub.i(x) is a Monotone hazard rate function (YES in step S204), the optimization unit 103 calculates a solution by the above procedure 1-2b (step S205). That is, the optimization unit 103 transforms the optimization problem shown in Expression (4) into the optimization problem shown in Expression (6), and then, calculates the optimal solution of the optimization problem shown in Expression (6) using an existing solution to the minimum convex cost flow problem.

[0087] On the other hand, if it is not determined in step S204 above that the acceptance probability S.sub.i(x) is bijective and 1−S.sub.i(x) is a Monotone hazard rate function (NO in step S204), the optimization unit 103 calculates a solution by the above procedure 1-2c (step S206). That is, the optimization unit 103 calculates an optimal solution or an approximate solution of the optimization problem shown in Expression (4) using a heuristic solution such as Bayesian optimization or simulated annealing.

[0088] As described above, the price optimization apparatus 10 according to the present embodiment can calculate and determine the optimal price by formulating the optimization problem in consideration of the matching value and the supply and demand balance for the crowdsourcing market that provides a service in the process of (a) to (c) described above and then solving the optimization problem. Moreover, the finally-obtained price (that is, the solutions calculated in steps S203, S205, and S206 above) is guaranteed to have a degree of approximation of 3 with respect to the optimal solution of the optimization problem formulated in consideration of the matching value and the supply and demand balance. Accordingly, for example, in the crowdsourcing market, it is possible to stably determine the price in consideration of compatibility between each task and each worker and the supply and demand balance.

[0089] <Hardware Configuration>

[0090] Finally, a hardware configuration of the price optimization apparatus 10 according to the present embodiment will be described with reference to FIG. 7. FIG. 7 is a diagram illustrating an example of a hardware configuration of the price optimization apparatus 10 according to the present embodiment.

[0091] As illustrated in FIG. 7, the price optimization apparatus 10 according to the present embodiment is implemented by a general computer or a computer system, and includes an input device 201, a display device 202, an external I/F 203, a communication I/F 204, a processor 205, and a memory device 206. These components of hardware are communicably connected via a bus 207.

[0092] The input device 201 is, for example, a keyboard, a mouse, a touch panel, or the like. The display device 202 is, for example, a display or the like. Note that the price optimization apparatus 10 may not include at least one of the input device 201 and the display device 202.

[0093] The external I/F 203 is an interface with an external device such as a recording medium 203a. The price optimization apparatus 10 can perform read, write, and the like on the recording medium 203a via the external I/F 203. For example, one or more programs for implementing the respective functional units (the input unit 101, the formulation unit 102, the optimization unit 103, and the output unit 104) included in the price optimization apparatus 10 may be stored in the recording medium 203a. Note that the recording medium 203a is, for example, a compact disc (CD), a digital versatile disk (DVD), a secure digital memory card (SD memory card), a universal serial bus (USB) memory card, or the like.

[0094] The communication I/F 204 is an interface for connecting the price optimization apparatus 10 to a communication network. Note that one or more programs for implementing each functional unit included in the price optimization apparatus 10 may be acquired (downloaded) from a predetermined server device or the like via the communication I/F 204.

[0095] The processor 205 is, for example, an arithmetic/logic device of various types such as a central processing unit (CPU) and a graphics processing unit (GPU). Each functional unit included in the price optimization apparatus 10 is implemented, for example, by processing in which one or more programs stored in the memory device 206 are executed by the processor 205.

[0096] The memory device 206 is, for example, a storage device of various types such as a hard disk drive (HDD), a solid state drive (SSD), a random access memory (RAM), a read only memory (ROM), and a flash memory.

[0097] The price optimization apparatus 10 according to the present embodiment can implement the above-described price optimization processing by having the hardware configuration illustrated in FIG. 7. Note that the hardware configuration illustrated in FIG. 7 is an example, and the price optimization apparatus 10 may have another hardware configuration. For example, the price optimization apparatus 10 may include a plurality of processors 205 or a plurality of memory devices 206.

[0098] The present invention is not limited to the above-mentioned specifically disclosed embodiment, and various modifications and changes, combinations with known technique, and the like can be made without departing from the scope of the claims.

REFERENCE SIGNS LIST

[0099] 10 Price optimization apparatus [0100] 101 Input unit [0101] 102 Formulation unit [0102] 103 Optimization unit [0103] 104 Output unit [0104] 201 Input device [0105] 202 Display device [0106] 203 External I/F [0107] 203a Recording medium [0108] 204 Communication I/F [0109] 205 Processor [0110] 206 Memory device [0111] 207 Bus